A Multi-Level GA Search with Application to the Resource-Constrained Re-Entrant Flow Shop Scheduling Problem

Authors: Danping Lin, C.K.M. Lee

Abstract:

Re-entrant scheduling is an important search problem with many constraints in the flow shop. In the literature, a number of approaches have been investigated from exact methods to meta-heuristics. This paper presents a genetic algorithm that encodes the problem as multi-level chromosomes to reflect the dependent relationship of the re-entrant possibility and resource consumption. The novel encoding way conserves the intact information of the data and fastens the convergence to the near optimal solutions. To test the effectiveness of the method, it has been applied to the resource-constrained re-entrant flow shop scheduling problem. Computational results show that the proposed GA performs better than the simulated annealing algorithm in the measure of the makespan

Keywords: Resource-constrained, re-entrant, genetic algorithm (GA), multi-level encoding

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1076370

References:

[1] J. Holland, Adaptation in natural and artificial systems. . Michigan: Ann Arbor MI: University of Michigan Press, 1975.
[2] S. Graves, et al., "Scheduling of re-entrant flow shops," Journal of Operations Management, vol. 3, pp. 197-207, 1983.
[3] D. Lin and C. K. M. Lee, "A review of the research methodology for the re-entrant scheduling problem," International Journal of Production Research, vol. 49, pp. 2221-2242, 15 Apr, 2011 2010.
[4] E. Demirkol and R. Uzsoy, "Decomposition methods for re-entrant flow shops with sequence-dependent setup times," Journal of Scheduling, vol. 3, pp. 155-77, 2000.
[5] Y. Park, et al., "Performance analysis of re-entrant flow shop with single-job and batch machines using mean value analysis," Production Planning and Control, vol. 11, pp. 537-546, 2000.
[6] N. G. Odrey, et al., "Generalized Petri net modeling approach for the control of re-entrant flow semiconductor wafer fabrication," Robotics and Computer-Integrated Manufacturing, vol. 17, pp. 5-11, 2001.
[7] J. H. Pan and J. S. Chen, "Minimizing makespan in re-entrant permutation flow-shops," Journal of the Operational Research Society, vol. 54, pp. 642-53, 2003.
[8] E. H. Nielsen, "How does variability in input load relate to the probability of critically delayed delivery in a simple multipart re-entrant flow-line problem?," International Journal of Production Research, vol. 42, pp. 3383-3396, 2004.
[9] J.-S. Chen and J. C.-H. Pan, "Integer programming models for the re-entrant shop scheduling problems," Engineering Optimization, vol. 38, pp. 577-592, July 2006 2006.
[10] H. Haitham and W. Ruml, "Network flow modeling for flexible manufacturing systems with re-entrant lines," presented at the Proceedings of the 45th IEEE Conference on Decision and Control Piscataway, NJ, USA, 2006.
[11] S. W. Choi and Y. D. Kim, "Minimizing makespan on a two-machine re-entrant flowshop," Journal of the Operational Research Society, vol. 58, pp. 572-81, 2007.
[12] S. Jiang and L. Tang, "Lagrangian relaxation algorithms for re-entrant hybrid flowshop scheduling," presented at the 2008 International Conference on Information Management, Innovation Management and Industrial Engineering, Piscataway, NJ, USA, 2008.
[13] D. Yang, et al., "Multi-family scheduling in a two-machine reentrant flow shop with setups," European Journal of Operational Research, vol. 187, pp. 1160-1170, 2008.
[14] T. Kaihara, et al., "Proactive maintenance scheduling in a re-entrant flow shop using Lagrangian decomposition coordination method," CIRP Annals - Manufacturing Technology, vol. 59, pp. 453-456, 2010.
[15] B. Scholz-Reiter, et al., "Analysis of priority rule-based scheduling in dual-resource-constrained shop-floor scenarios," presented at the International Conference on Advances in Machine Learning and Systems Engineering, Berkeley, CA, United states, 2010.
[16] J. R. Perkins and P. R. Kumar, "Optimal control of pull manufacturing systems," IEEE Transactions on Automatic Control, vol. 40, pp. 2040-51, 1995.
[17] R. Cigolini, et al., "Implementing new dispatching rules at SGS-Thomson Microelectronics," Production Planning and Control, vol. 10, pp. 97-106, 1999.
[18] I. A. El-Khouly, et al., "Modelling and simulation of re-entrant flow shop scheduling: An applicationin semiconductor manufacturing," presented at the 2009 International Conference on Computers and Industrial Engineering, CIE 2009, Troyes, France, 2009.
[19] H. Hwang and J. U. Sun, "Production sequencing problem with re-entrant work flows and sequence dependent setup times," International Journal of Production Research, vol. 36, pp. 2435-2450, 1 September 1998 1998.
[20] J.-S. Chen, et al., "A hybrid genetic algorithm for the re-entrant flow-shop scheduling problem," Expert Systems with Applications, vol. 34, pp. 570-577, 2008.
[21] H. Rau and K.-H. Cho, "Genetic algorithm modeling for the inspection allocation in reentrant production systems," Expert Systems with Applications, vol. 36, pp. 11287-11295, 2009.
[22] C.-H. Liu, "A genetic algorithm based approach for scheduling of jobs containing multiple orders in a three-machine flowshop," International Journal of Production Research, vol. 48, pp. 4379-96, 2010.
[23] C. K. M. Lee and D. Lin, "Hybrid genetic algorithm for bi-objective flow shop scheduling problems with re-entrant jobs," presented at the IEEE International Conference on Industrial Engineering and Engineering Management, IEEM2010, Macao, China, 2010.
[24] M. Nawaz, et al., "A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem," Omega, vol. 11, pp. 91-95, 1983.
[25] R. L. Daniels, et al., "Flow shop scheduling with partial resource flexibility," Management Science, vol. 50, pp. 658-669, 2004.
[26] G. Neubert and M. M. Savino, "Flow shop operator scheduling through constraint satisfaction and constraint optimisation techniques," International Journal of Productivity and Quality Management, vol. 4, pp. 549-68, 2009.
[27] A. Janiak, "General flow-shop scheduling with resource constraints," International Journal of Production Research, vol. 26, pp. 1089-1103, 1988.
[28] T. C. E. Cheng and A. Janiak, "A permutation flow-shop scheduling problem with convex models of operation processing times," Annals of Operations Research, vol. 96, pp. 39-60, 2000.
[29] S.-S. Leu and S.-T. Hwang, "GA-based resource-constrained flow-shop scheduling model for mixed precast production," Automation in Construction, vol. 11, pp. 439-52, 2002.
[30] L.-Y. Tseng and S.-C. Chen, "Two-phase genetic local search algorithm for the multimode resource-constrained project scheduling problem," IEEE Transactions on Evolutionary Computation, vol. 13, pp. 848-857, 2009.
[31] H. R. Topcuoglu, et al., "Solving the register allocation problem for embedded systems using a hybrid evolutionary algorithm," IEEE Transactions on Evolutionary Computation, vol. 11, pp. 620-634, 2007.
[32] R. Zamani, "An Accelerating Two-Layer Anchor Search With Application to the Resource-Constrained Project Scheduling Problem," Evolutionary Computation, IEEE Transactions on, vol. 14, pp. 975-984, 2010.
[33] R. Kolisch and A. Sprecher, "PSPLIB-a project scheduling problem library," European Journal of Operational Research, vol. 96, pp. 205-16, 1997.