Dual Resource Constrained Flexible Job-Shop Scheduling with Lexicograph Objectives

Document Type : Research Paper

Authors

1 Assistant Professor, Department of Industrial Engineering, Faculty of Engineering, Qom University, Qom, Iran

2 M.A., Industrial Engineering, Faculty of Engineering, Qom University, Qom, Iran

Abstract

In this research, the dual resource constrained flexible job-shop scheduling problem (DRCFJSP) is considered. Compared to the flexible job-shop scheduling, there is a limited research on DRCFJSP. The flexible job-shop scheduling problem is an extension of the classical job-shop scheduling problem by allowing an operation to be assigned to one of a set of eligible machines during scheduling. Hence, solving DRCFJSP not only needs to determine the processing sequences on machines and assign each operation to a machine, but also needs to determine a worker among a set of skilled workers for processing operation on the selected machine. The problem in this study was investigated to minimize two objectives consisting of total weighted tardiness and maximum completion time. The lexicographic approach is applied to compare the solutions and select the optimum solution. The first objective function is total weighted tardiness. DRCFJSP is strongly NP-hard, so a hybrid artificial bee colony algorithm is proposed to solve medium and large instances. In order to evaluate the performance of the proposed algorithm, computational studies have been conducted and compared with the results of the GAMS software. The results show that proposed hybrid algorithm has an appropriate performance for solving the DRCFJSP.

Keywords

References

[1]    Yazdani, M., Zandieh, M., Tavakkoli-Moghaddam, R., & Jolai, F. (2015). Two meta-heuristic algorithms for the dual-resource constrained flexible job-shop scheduling problem. Scientia Iranica. Transaction E, Industrial Engineering, 22(3): 12-42.
[2]    Gao, L., & Pan, Q. K. (2016). A shuffled multi-swarm micro-migrating birds optimizer for a multi-resource-constrained flexible job shop scheduling problem. Information Sciences, 372: 655-676.
[3]    Gonzalez, T., & Sahni, S. (1978). Flow shop and job shop schedules: complexity and approximation. Operations research, 26(1): 36-52.
[4]    Du, J., & Leung, J.Y.T. (1990).  Minimizing Total Tardiness on One Machine Is NP-Hard. Mathematics of Operations Research, 15(3): 483-495.
[5]    Baker, K. R. (1974). Introduction to sequencing and scheduling. John Wiley & Sons.
[6]    Brucker, P., & Schlie, R. (1990). Job-shop scheduling with multi-purpose machines. Computing, 45(4): 369-375.
[7]    Shahsavari-Pour, N., & Ghasemishabankareh, B. (2013). A novel hybrid meta-heuristic algorithm for solving multi objective flexible job shop scheduling. Journal of Manufacturing Systems, 32(4): 771-780.
[8]    Sobeyko, O., & Mönch, L. (2016). Heuristic approaches for scheduling jobs in large-scale flexible job shops. Computers & Operations Research, 68: 97-109.
[9]    Rooyani, D., & Defersha, F. M. (2019). An Efficient Two-Stage Genetic Algorithm for Flexible Job-Shop Scheduling. IFAC PapersOnLine, 52(13): 2519–2524.
[10] Fakhrzad, M.B., & Alinezhad, E. (2013). Advanced planning and scheduling with a learning effect in the flexible job shop manufacturing system. Journal of Industrial Engineering Research in Production Systems, 1(1): 13-24.
[11] Nelson, R. T. (1967). Labor and machine limited production systems. Management Science, 13(9): 648-671.
[12] Jaber, M. Y., & Neumann, W. P. (2010). Modelling worker fatigue and recovery in dual-resource constrained systems. Computers & Industrial Engineering, 59(1): 75-84.
[13] Li, J., Sun, S., Huang, Y., & Wang, N. (2010, June). A hybrid algorithm for scheduling of dual-resource constrained job shop. Computing, Control and Industrial Engineering (CCIE), 2010 International Conference on, 1: 235-238.
[14] Lobo, B. J., Hodgson, T. J., King, R. E., Thoney, K. A., & Wilson, J. R. (2013). An effective lower bound on Lmax in a worker-constrained job shop. Computers & Operations Research, 40(1): 328-343.
[15] Lei, D., & Guo, X. (2014). Variable neighborhood search for dual-resource constrained flexible job shop scheduling. International Journal of Production Research, 52(9): 2519-2529.
[16] Liu, X. X., Liu, C. B., & Tao, Z. (2011). Research on Bi-Objective Scheduling of Dual-Resource Constrained Flexible Job Shop. Advanced Materials Research, 211: 1091-1095.
[17] Lang, M., & Li, H. (2011). Research on dual-resource multi-objective flexible job shop scheduling under uncertainty. 2nd International Conference on Artificial Intelligence, Management Science and Electronic Commerce (AIMSEC), Dengleng, China, 8-10 Aug. 2011, 1375-1378.
[18] Xianzhou, C., & Zhenhe, Y. (2011, March). An improved genetic algorithm for dual-resource constrained flexible job shop scheduling. Intelligent Computation Technology and Automation (ICICTA), 2011 International Conference on, 1: 42-45.
[19] Li, J.Q., Pan, S. Xie, S. Wang. (2011). A Hybrid Artificial Bee Colony Algorithm for Flexible Job Shop Scheduling Problems. International Journal of Computers, Communications & Control, 2: 286-296.
[20] Lian, Z., Jiao, B., & Gu, X. (2006). A similar particle swarm optimization algorithm for job-shop scheduling to minimize makespan. Applied mathematics and computation, 183(2): 1008-1017.
[21] Udaiyakumar, K. C., & Chandrasekaran, M. (2014). Application of firefly algorithm in job shop scheduling problem for minimization of makespan. Procedia Engineering, 97: 1798-1807.
[22] Yuan, Y., & Xu, H. (2013). An integrated search heuristic for large-scale flexible job shop scheduling problems. Computers & Operations Research, 40(12): 2864-2877.
[23] Pasandideh, S. H. R., Niaki, S. T. A., & Hajipour, V. (2013). A multi-objective facility location model with batch arrivals: two parameter-tuned meta-heuristic algorithms. Journal of Intelligent Manufacturing, 1-18.
[24] Bagheri, A., & Zandieh, M. (2011). Bi-criteria flexible job-shop scheduling with sequence-dependent setup times—variable neighborhood search approach. Journal of Manufacturing Systems, 30(1): 8-15.
[25] Huang, R. H., & Yu, T. H. (2017). An effective ant colony optimization algorithm for multi-objective job-shop scheduling with equal-size lot-splitting. Applied Soft Computing, 57, 642-656.
[26] Zheng, F., & Wang, Zh. (2019). Bi-objective Flexible Job Shop Scheduling with Operation Overlapping Costs. IFAC PapersOnLine, 52(13): 893–898.
[27] Farahani, R. Z., SteadieSeifi, M., & Asgari, N. (2010). Multiple criteria facility location problems: A survey. Applied Mathematical Modelling, 34(7): 1689-1709.
[28] Mandow, L., & de la Cruz, J. P. (2001). A heuristic search algorithm with lexicographic goals. Engineering Applications of Artificial Intelligence, 14(6): 751-762.
[29] Dhouib, E., Teghem, J., & Loukil, T. (2013). Lexicographic optimization of a permutation flow shop scheduling problem with time lag constraints. International Transactions in Operational Research, 20(2): 213-232.
[30] Sawik, T. (2007). A lexicographic approach to bi-objective scheduling of single-period orders in make-to-order manufacturing. European Journal of Operational Research, 180(3): 1060-1075.
[31] Palacios, J. J., González-Rodríguez, I., Vela, C. R., & Puente, J. (2015). Swarm lexicographic goal programming for fuzzy open shop scheduling. Journal of Intelligent Manufacturing, 26(6): 1201-1215.
[32] Li, X., Peng, Z., Du, B., Guo, J., Xu, W., Zhuang, K. (2017). Hybrid artificial bee colony algorithm with a rescheduling strategy for solving flexible job shop scheduling problems. Computers & Industrial Engineering, 113: 10-26.
[33] Gao, K.Z., Suganthan, P.N., Chua, T.J. Chong, C.S., Cai, T.X., Pan, Q.K. (2015). A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion. Expert Systems with Applications, 42 (21): 7652-7663.
[34] Li, J.Q., Pan, Q.K., Tasgetiren M.F. (2014). A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Applied Mathematical Modelling, 38(3): 1111-1132.
[35] Thammano, A., Phu-ang, A. (2013). A Hybrid Artificial Bee Colony Algorithm with Local Search for Flexible Job-Shop Scheduling Problem. Procedia Computer Science, 20: 96–101.
[36] Karaboga, D. (2005). An idea based on honey bee swarm for numerical optimization [J]. Technical Report TR06. Turkey: Computer Engineering Department, Erciyes University.
[37] Gao, J., Gen, M., Sun, L. (2006). Scheduling jobs and maintenance in flexible job shop with a hybrid genetic algorithm, Journal of Intelligent Manufacturing, 17(4): 493-507.
[38] Pezzella, F., Morganti, G., & Ciaschetti, G. (2008). A genetic algorithm for the flexible job-shop scheduling problem. Computers & Operations Research, 35(10): 3202-3212.
Journal of Industrial Engineering Research in Production Systems
Volume 8, Issue 17
March 2021
Pages 295-309

Files

Share

How to cite

Statistics