A genetic algorithm embedded with a concise chromosome representation for distributed and flexible job-shop scheduling problems
Tóm tắt
This paper proposes a genetic algorithm
$$GA\_JS$$
for solving distributed and flexible job-shop scheduling (DFJS) problems. A DFJS problem involves three scheduling decisions: (1) job-to-cell assignment, (2) operation-sequencing, and (3) operation-to-machine assignment. Therefore, solving a DFJS problem is essentially a 3-dimensional solution space search problem; each dimension represents a type of decision. The
$$GA\_JS$$
algorithm is developed by proposing a new and concise chromosome representation
$${\varvec{S}}_{{\varvec{JOB}}}$$
, which models a 3-dimensional scheduling solution by a 1-dimensional scheme (i.e., a sequence of all jobs to be scheduled). That is, the chromosome space is 1-dimensional (1D) and the solution space is 3-dimensional (3D). In
$$GA\_JS$$
, we develop a 1D-to-3D decoding method to convert a 1D chromosome into a 3D solution. In addition, given a 3D solution, we use a refinement method to improve the scheduling performance and subsequently use a 3D-to-1D encoding method to convert the refined 3D solution into a 1D chromosome. The 1D-to-3D decoding method is designed to obtain a “good” 3D solution which tends to be load-balanced. In contrast, the refinement and 3D-to-1D encoding methods of a 3D solution provides a novel way (rather than by genetic operators) to generate new chromosomes, which are herein called shadow chromosomes. Numerical experiments indicate that
$$GA\_JS$$
outperforms the IGA developed by De Giovanni and Pezzella (Eur J Oper Res 200:395–408, 2010), which is the up-to-date best-performing genetic algorithm in solving DFJS problems.
Tài liệu tham khảo
Baykasoǧlu, A. (2002). Linguistic-based meta-heuristic optimization model for flexible job shop scheduling. International Journal of Production Research, 40(17), 4523–4543.
Bożejko, W., Uchroński, M., & Wodecki, M. (2010). Parallel hybrid metaheuristics for the flexible job shop problem. Computers & Industrial Engineering, 59, 323–333.
Brandimarte, P. (1993). Routing and scheduling in a flexible job shop by tabu search. Annals of Operations Research, 41, 157–183.
Bruker, P., & Schlie, R. (1990). Job-shop scheduling with multi-purpose machines. Computing, 45, 369–375.
Chan, F. T. S., Chung, S. H., & Chan, P. L. Y. (2005). An adaptive genetic algorithm with dominated genes for distributed scheduling problems. Expert Systems with Applications, 29, 364–371.
Chan, F. T. S., Chung, S. H., & Chan, P. L. Y. (2006). Application of genetic algorithms with dominant genes in a distributed scheduling problem in flexible manufacturing systems. International Journal of Production Research, 44(3), 523–543.
Choi, I. C., & Choi, D. S. (2002). A local search algorithm for jobshop scheduling problems with alternative operations and sequence-dependent setups. Computers & Industrial Engineering, 42, 43–58.
Chou, Y. C., & Cheng, H. H. (2010). An autonomic mobile agent-based system for distributed job shop scheduling. IEEE/ASME international conference on mechatronics and embedded systems and applications (pp. 113–118).
Dauzère-Pérès, S., & Paulli, J. (1997). An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Annals of Operations Research, 70, 281–306.
De Giovanni, L., & Pezzella, F. (2010). An improved genetic algorithm for the distributed and flexible job-shop scheduling problem. European Journal of Operational Research, 200, 395–408.
Gao, J., Sun, L., & Gen, M. (2008). A hybrid genetic and variable neighborhood descent algorithm for flexible job shop scheduling problems. Computers & Operations Research, 35, 2892–2907.
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117–129.
Gen, M., & Cheng, R. (1997). Genetic algorithms and engineering design. New York: Wiley.
Gen, M., Cheng, R., & Lin, L. (2008). Network models and optimization: Multiobjective genetic algorithm approach. London: Springer.
González, M. A., Vela, C. R., & Varela, R. (2013). An efficient memetic algorithm for the flexible job shop with setup times. In: Proceedings of the 23th international conference on automated planning and scheduling (pp. 91–99).
Gutiérrez, C., & García-Magariño, I. (2011). Modular design of a hybrid genetic algorithm for a flexible job-shop scheduling problem. Knowledge-Based Systems, 24, 102–112.
Hmida, A. B., Haouari, M., Huguet, M. J., & Lopez, P. (2010). Discrepancy search for the flexible job shop scheduling problem. Computers & Operations Research, 37, 2192–2201.
Ho, N. B., & Tay, J. C. (2004). GENACE: An efficient cultural algorithm for solving the flexible job-shop problem. Proceedings of the IEEE congress on evolutionary computation (pp. 1759–1766).
Hurink, J., Jurisch, B., & Thole, M. (1994). Tabu search for the job-shop scheduling problem with multi-purpose machines. OR Spektrum, 15, 205–215.
Jia, H. Z., Nee, A. Y. C., Fuh, J. Y. H., & Zhang, Y. F. (2003). A modified genetic algorithm for distributed scheduling problems. Journal of Intelligent Manufacturing, 14, 351–362.
Jia, H. Z., Nee, A. Y. C., Fuh, J. Y. H., & Zhang, Y. F. (2007). Integration of genetic algorithm and Gantt chart for job shop scheduling in distributed manufacturing systems. Computer & Industrial Engineering, 53, 313–320.
Jia, S., & Hu, Z. H. (2014). Path-relinking tabu search for the multi-objective flexible job shop scheduling problem. Computers & Operations Research, 47, 11–26.
Jinyan, M., Chai, S. Y., & Youyi, W. (1995). FMS jobshop scheduling using lagrangian relaxation method. Proceedings of IEEE international conference on robotics and automation (pp. 490–495).
Kacem, I., Hammadi, S., & Borne, P. (2002a). Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Transactions on Systems, Man and Cybernetics, Part C: Applications and Reviews, 32(1), 1–13.
Kacem, I., Hammadi, S., & Borne, P. (2002b). Pareto-optimality approach for flexible job-shop scheduling problems: Hybridization of evolutionary algorithms and fuzzy logic. Mathematics and Computers in Simulation, 60, 245–276.
Kim, K.-H., & Egbelu, P. J. (1999). Scheduling in a production environment with multiple process plans per job. International Journal of Production Research, 37(12), 2725–2753.
Lin, L., & Gen, M. (2006). Node-based genetic algorithm for communication spanning tree problem. IEICE Transactions on Communications, E89–B(4), 1091–1098.
Mastrolilli, M., & Gambardella, L. M. (2000). Effective neighbourhood functions for the flexible job shop problem. Journal of Scheduling, 3, 3–20.
Pezzella, F., Morganti, G., & Ciaschetti, G. (2008). A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research, 35, 3202–3212.
Raidl, G. R., & Julstrom, B. A. (2003). Edge sets: an effective evolutionary coding of spanning trees. IEEE Transactions on Evolutionary Computation, 7(3), 225–239.
Tay, J. C., & Wibowo, D. (2004). An effective chromosome representation for evolving flexible job shop schedules. Genetic and Evolutionary Computation, 3103, 210–221.
Tung, L. F., Lin, L., & Nagi, R. (1999). Multi-objective scheduling for the hierarchical control of flexible manufacturing systems. The International Journal of Flexible Manufacturing Systems, 11, 379–409.
Xia, W., & Wu, Z. (2005). An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Computers & Industrial Engineering, 48, 409–425.
Xing, L. N., Chen, Y. W., Wang, P., Zhao, Q. S., & Xiong, J. (2010). A knowledge-based ant colony optimization for flexible job shop scheduling problems. Applied Soft Computing, 10, 888–896.
Yuan, Y., & Xu, H. (2013). An integrated search heuristic for large-scale flexible job shop scheduling problems. Computers & Operations Research, 40, 2864–2877.
Zhang, G., Gao, L., & Shi, Y. (2011). An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Systems with Applications, 38, 3563–3573.
Zhang, Y. X., Li, L., Wang, H., Zhao, Y. Y., Guo, X., & Meng, C. H. (2008). Approach to the distributed job shop scheduling based on multi-agent. In Proceedings of the IEEE international conference on automation and logistics (pp. 2031–2034).
Ziaee, M. (2014). A heuristic algorithm for the distributed and flexible job-shop scheduling problem. J Supercomput, 67, 69–83.