A Method for Flexible Job-Shop Scheduling using Genetic Algorithm
This paper focused on solving a flexible job-shop scheduling problem. Because this problem is known as NP-hard, methods using meta-heuristics especially genetic algorithm (GA) have been actively proposed. Although it is possible to obtain solutions of large problems in a reasonable time by those methods, the quality of the solutions decreases as the scale of the problem increases. Hence, taking advantage of knowledge included in heuristic dispatching rules in the optimization by GA was proposed, and its effectiveness was proven. However, in this method, the two kinds of selection required in flexible job-shop production, machine selection and job selection, were carried out sequentially. Because this may result in insufficient search of the solution space, this paper provided a method using GA in which those two selections were performed at once. The method was applied to an example and it was shown that better solutions could be obtained.
S.C. Graves, “A review of production scheduling”, Operations Research, vol. 29, no. 4, pp. 646-675, 1981.
T.C.E. Cheng and M.C. Gupta, “Survey of scheduling research involving due date determination decisions”, European Journal of Operational Research, vol. 38, no. 2, pp. 156-166, 1989.
D. Lei, “Multi-objective production scheduling: A survey”, International Journal of Advanced Manufacturing Technology, vol. 43, no. 9-10, pp. 926-938, 2009.
J. Branke, S. Nguyen, C.W. Pickardt and M. Zhang, “Automated design of production scheduling heuristics: A review”, IEEE Transactions on Evolutionary Computation, vol. 20, no. 1, pp. 110-124, 2016.
C.H. Pan, “A study of integer programming formulations for scheduling problems”, International Journal of Systems Science, vol. 28, pp. 33-41, 1997.
S.S. Panwalker and W. Iskander, “A survey of scheduling rules”, Operations Research, vol. 25, pp. 45-61, 1977.
D.E. Akyol and D.M. Bayhan, “A review on evolution of production scheduling with neural networks”, Computers and Industrial Engineering, vol. 53, pp. 95-122, 2007.
K.S. Metaxiotis, D. Askounis and J. Psarras, “Expert systems in production planning and scheduling: a state-of-the-art survey”, vol. 13, pp. 252-260, 2002.
S.J. Noronha and V.V.S. Sarma, “Knowledge-based approaches for scheduling problems: a survey”, IEEE Transactions on Knowledge and Data Engineering, vol. 3, pp. 160-171, 1991.
G. Tuncel and M. Bayhan, “Applications of petri nets in production scheduling: a review”, International Journal of Manufacturing Technology, vol. 34, pp. 762-773, 2007
F. Pezzella, G. Morganti and G. A. Ciaschetti, “Genetic algorithm for the flexible job-shop scheduling problem”, Computers & Operations Research, vol. 35, pp. 3202-3212, 2008.
L. De Giovanni and F. Pezzella, “An improved genetic algorithm for the distributed and flexible job-shop scheduling problem”, European Journal of Operational Research, vol. 200, pp. 395-408, 2010.
B.A. Norman and J.C. Bean, “A genetic algorithm methodology for complex scheduling problems”, Naval Research Logistics, vol. 46, pp. 199-211, 1999.
G. Zhang, L. Gao and Y. Shi, “An effective genetic algorithm for the flexible job-shop scheduling problem”, Expert Systems with Applications, vol. 38, pp. 3563-3573, 2011.
N. Morad and A. Zalzala, “Genetic algorithms in integrated process planning and scheduling”, Journal of Intelligent Manufacturing, vol. 10, pp. 169-179, 1999.
P. Kaweegitbundit and T. Eguchi, “Flexible job shop scheduling using genetic algorithm and heuristic rules”, Journal of Advanced Mechanical Design, Systems, and Manufacturing, vol. 10, no. 1, pp. 1-18, 2015.
Authors who publish with this journal agree to the following terms:
- Authors transfer copyright to the publisher as part of a journal publishing agreement with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) after the manuscript is accepted, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).