A Multi-Level GA Search with Application to the Resource-Constrained Re-Entrant Flow Shop Scheduling Problem
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
[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.
[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.
@article{"International Journal of Mechanical, Industrial and Aerospace Sciences:60027", author = "Danping Lin and C.K.M. Lee", title = "A Multi-Level GA Search with Application to the Resource-Constrained Re-Entrant Flow Shop Scheduling Problem", 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", volume = "6", number = "4", pages = "849-5", }
