An Adaptive Hyper-Heuristics Genetic Algorithm for Stochastic Job Shop Scheduling Problem

Abstract:

Stochastic job - shop scheduling problem (SJSSP) is a kind of stochastic programming problem which transformed from job - shop scheduling problem (JSSP). The current methods to solve SJSSP ignored characteristics of SJSSP, which lead to large solution times and inefficient solution. Aiming at the problem,An adaptive Hyper-Heuristics genetic algorithms (AHHGA) is proposed combing with characteristics of SJSSP to solve SJSSP with the objective to minimize make span (minimize the expected value of make span). Four heuristics rules for SJSSP were designed. Portfolios of processing times of job can be seen as a scenario. The outer loop of the proposed algorithms is to determine heuristics rules on each scenario in scenario set.

• Periodical: Applied Mechanics and Materials (Volumes 556-562)
• Pages: 3956-3960
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.556-562.3956
• Online since: May 2014
• Authors: Hui Wang*
• Keywords: Genetic Algorithm (GA), Job-Shop Scheduling, Production Control, Production Management

References

[1] Gonca lves J F, de Mag alhaes Mendes J J, Resende MG C. A Hy brid Genetic Algo rithm for the Job Shop Scheduling Problem[ J] . European Journal of Operational Research, 2005, 167( 1) : 77-95.

DOI: 10.1016/j.ejor.2004.03.012

[2] WANG Wanliang, XU Xinli, ZH AO Yanw ei, et al . Job-shop scheduling method based on m odified immune algorithm [ J ] . Key Engineering Materials, 2006, 315/ 316: 4812485.

DOI: 10.4028/www.scientific.net/kem.315-316.481

[3] ColorniA, DorigoM, Maniezzo V. Distributed Optimization by AntColonies / / Proc of the 1 st European Conference on Artificial Life。Paris, France, 1992: 134 – 142.

[4] Deming Lei . Simplified multi-objective genetic algorithms for stochastic job shopscheduling Applied Soft Computing, Volume 11, Issue 8, December 2011, Pages 4991-4996.

DOI: 10.1016/j.asoc.2011.06.001

[5] Jinwei Gu, Xingsheng Gu, Manzhan Gu. A novel parallel quantum genetic algorithm forstochastic job-shop scheduling  Original Research ArticleJournal of Mathematical Analysis and Applications, Volume 355, Issue 1, 1 July 2009, Pages 63-81.

DOI: 10.1016/j.jmaa.2008.12.065

[6] Jinwei Gu, Manzhan Gu, Cuiwen Cao, Xingsheng Gu. A novel competitive co-evolutionary quantum genetic algorithm for stochastic job shop scheduling problem Computers & Operations Research, Volume 37, Issue 5, May 2010, Pages 927-937.

DOI: 10.1016/j.cor.2009.07.002

[7] Burke E K, Newall J. A multi-stage evolutionary algorithm for the timetabling problem[J]. IEEE Transactions on Evolutionary Computation, 1999, 3(1): 63-74.

DOI: 10.1109/4235.752921

[8] Burke E K, Kendall G, Soubeiga E. A tabu search hyperheuristic for timetabling and rostering[J]. Journal of Heuristics, 2003, 9(6): 451-470.

DOI: 10.1023/b:heur.0000012446.94732.b6

[9] Burke E K, McCollum B, Meisels A, et al. A graph-based hyperheuristic for educational timetabling problems [J]. European Journal of Operational Research, 2006, 176(1): 177-192.

DOI: 10.1016/j.ejor.2005.08.012