A Method for Flexible Job-Shop Scheduling using Genetic Algorithm

E. Morinaga; Y. Sakaguchi; H. Wakamatsu; E. Arai

E. Morinaga
Y. Sakaguchi
H. Wakamatsu
E. Arai

Abstract

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.

Downloads

Download data is not yet available.

References

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.