• Previous Article
    Diagonally scaled memoryless quasi–Newton methods with application to compressed sensing
  • JIMO Home
  • This Issue
  • Next Article
    A new dynamic model to optimize the reliability of the series-parallel systems under warm standby components
January  2023, 19(1): 402-436. doi: 10.3934/jimo.2021190

Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints

Department of Industrial Engineering and Management, Mazandaran University of Science and Technology, Babol, Iran

* Corresponding author: Javad Rezaeian

Received  January 2021 Revised  September 2021 Published  January 2023 Early access  November 2021

In today's competitive world, scheduling problems are one of the most important and vital issues. In this study, a bi-objective unrelated parallel machine scheduling problem with worker allocation, sequence dependent setup times, precedence constraints, and machine eligibility is presented. The objective functions are to minimize the costs of tardiness and hiring workers. In order to formulate the proposed problem, a mixed-integer quadratic programming model is presented. A strategy called repair is also proposed to implement the precedence constraints. Because the problem is NP-hard, two metaheuristic algorithms, a multi-objective tabu search (MOTS) and a multi-objective simulated annealing (MOSA), are presented to tackle the problem. Furthermore, a hybrid metaheuristic algorithm is also developed. Finally, computational experiments are carried out to evaluate different test problems, and analysis of variance is done to compare the performance of the proposed algorithms. The results show that MOTS is doing better in terms of objective values and mean ideal distance (MID) metric, while the proposed hybrid algorithm outperforms in most cases, considering other employed comparison metrics.

Citation: Reza Alizadeh Foroutan, Javad Rezaeian, Milad Shafipour. Bi-objective unrelated parallel machines scheduling problem with worker allocation and sequence dependent setup times considering machine eligibility and precedence constraints. Journal of Industrial and Management Optimization, 2023, 19 (1) : 402-436. doi: 10.3934/jimo.2021190
References:
[1]

M. Afzalirad and J. Rezaeian, Resource-constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions, Computers & Industrial Engineering, 98 (2016), 40-52.  doi: 10.1016/j.cie.2016.05.020.

[2]

M. Afzalirad and M. Shafipour, Design of an efficient genetic algorithm for resource-constrained unrelated parallel machine scheduling problem with machine eligibility restrictions, Journal of Intelligent Manufacturing, 29 (2018), 423-437.  doi: 10.1007/s10845-015-1117-6.

[3]

O. A. Arik and M. D. Toksari, Multi-objective fuzzy parallel machine scheduling problems under fuzzy job deterioration and learning effects, International Journal of Production Research, 56 (2018), 2488-2505.  doi: 10.1080/00207543.2017.1388932.

[4]

A. Baykasoglu, Applying multiple objective tabu search to continuous optimization problems with a simple neighbourhood strategy, International Journal for Numerical Methods in Engineering, 65 (2006), 406-424.  doi: 10.1002/nme.1455.

[5]

T. ÇakarR. Köker and Y. Sari, Parallel robot scheduling to minimize mean tardiness with unequal release date and precedence constraints using a hybrid intelligent system, International Journal of Advanced Robotic Systems, 9 (2012), 252.  doi: 10.5772/54381.

[6]

C. L. Chen, Iterated hybrid metaheuristic algorithms for unrelated parallel machines problem with unequal ready times and sequence-dependent setup times, The International Journal of Advanced Manufacturing Technology, 60 (2012), 693-705.  doi: 10.1007/s00170-011-3623-9.

[7]

L. P. CotaF. G. GuimarãesR. G. RibeiroI. R. MeneghiniF. B. de OliveiraM. J. Souza and P. Siarry, An adaptive multi-objective algorithm based on decomposition and large neighborhood search for a green machine scheduling problem, Swarm and Evolutionary Computation, 51 (2019), 100601.  doi: 10.1016/j.swevo.2019.100601.

[8]

M. DhiflaouiH. E. Nouri and O. B. Driss, Dual-resource constraints in classical and flexible job shop problems: A state-of-the-art review, Procedia Computer Science, 126 (2018), 1507-1515.  doi: 10.1016/j.procs.2018.08.123.

[9]

E. C. H. Dorion, J. C. F. Guimarães, E. A. Severo, Z. C. Reis and P. M. Olea, Innovation and production management through a just in sequence strategy in a multinational brazilian metal-mechanic industry, 2014 IEEE International Conference on Management of Innovation and Technology, (2014), 54–60. doi: 10.1109/ICMIT.2014.6942400.

[10]

P. Engrand, A multi-objective optimization approach based on simulated annealing and its application to nuclear fuel management, 1998.

[11]

A. E. Ezugwu, O. J. Adeleke and S. Viriri, Symbiotic organisms search algorithm for the unrelated parallel machines scheduling with sequence-dependent setup times, PloS One, 13 (2018), e0200030. doi: 10.1371/journal.pone.0200030.

[12]

A. E. Ezugwu and F. Akutsah, An improved firefly algorithm for the unrelated parallel machines scheduling problem with sequence-dependent setup times, IEEE Access, 6 (2018), 54459-54478.  doi: 10.1109/ACCESS.2018.2872110.

[13]

C. M. Fonseca, L. Paquete and M. López-Ibánez, An improved dimension-sweep algorithm for the hypervolume indicator, 2006 IEEE International Conference on Evolutionary Computation, (2006), 1157–1163. doi: 10.1109/CEC.2006.1688440.

[14]

F. Glover, Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res., 13 (1986), 533-549.  doi: 10.1016/0305-0548(86)90048-1.

[15]

F. W. Glover and G. A. Kochenberger. (Eds.), Handbook of Metaheuristics, International Series in Operations Research & Management Science, 57. Kluwer Academic Publishers, Boston, MA, 2003.

[16]

G. GongR. ChiongQ. Deng and X. Gong, A hybrid artificial bee colony algorithm for flexible job shop scheduling with worker flexibility, International Journal of Production Research, 58 (2020), 4406-4420.  doi: 10.1080/00207543.2019.1653504.

[17]

G. GongR. ChiongQ. DengW. HanL. ZhangW. Lin and K. Li, Energy-efficient flexible flow shop scheduling with worker flexibility, Expert Systems with Applications, 141 (2020), 112902.  doi: 10.1016/j.eswa.2019.112902.

[18]

A. Hamzadayi and G. Yildiz, Modeling and solving static m identical parallel machines scheduling problem with a common server and sequence dependent setup times, Computers & Industrial Engineering, 106 (2017), 287-298.  doi: 10.1016/j.cie.2017.02.013.

[19]

M. P. Hansen, Tabu search for multiobjective optimization: MOTS, Proceedings of the 13th International Conference on Multiple Criteria Decision Making, (1997), 574–586.

[20]

O. Hurdies, Just in time (JIT) production: An effective approach to efficiency, Logistics & Supply Chain Review, 1 (2020), 32-39. 

[21]

B. Van Khanh and N. Van Hop, Genetic algorithm with initial sequence for parallel machines scheduling with sequence dependent setup times based on earliness-tardiness, Journal of Industrial and Production Engineering, 38 (2021), 18-28.  doi: 10.1080/21681015.2020.1829111.

[22]

J. G. KimS. Song and B. Jeong, Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times, International Journal of Production Research, 58 (2020), 1628-1643.  doi: 10.1080/00207543.2019.1672900.

[23]

S. KirkpatrickC. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680.  doi: 10.1126/science.220.4598.671.

[24]

D. LeiY. YuanJ. Cai and D. Bai, An imperialist competitive algorithm with memory for distributed unrelated parallel machines scheduling, International Journal of Production Research, 58 (2020), 597-614.  doi: 10.1080/00207543.2019.1598596.

[25]

H. M. Md, Lead time reduction and process cycle improvement of an ice-cream manufacturing factory in bangladesh by using value stream map and kanban board, Australian Journal Of Basic and Applied Sciences, (2016).

[26]

A. Munoz-VillamizarJ. SantosJ. Montoya-Torres and M. Alvaréz, Improving effectiveness of parallel machine scheduling with earliness and tardiness costs: A case study, International Journal of Industrial Engineering Computations, 10 (2019), 375-392.  doi: 10.5267/j.ijiec.2019.2.001.

[27]

J. RezaeianN. DerakhshanI. Mahdavi and R. A. Foroutan, Due date assignment and JIT scheduling problem in blocking hybrid flow shop robotic cells with multiple robots and batch delivery cost, International Journal of Industrial Mathematics, 13 (2021), 145-162. 

[28]

M. Savsar, Simulation analysis of a pull-push system for an electronic assembly line, International Journal of Production Economics, 51 (1997), 205-214.  doi: 10.1016/S0925-5273(97)00055-8.

[29]

G. Taguchi, Introduction to quality engineering: Designing quality into products and processes, No. 658.562 T3, (1986).

[30]

E. Vallada and R. Ruiz, A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times, European J. Oper. Res., 211 (2011), 612-622.  doi: 10.1016/j.ejor.2011.01.011.

[31]

B. Wang and H. Wang, Multiobjective order acceptance and scheduling on unrelated parallel machines with machine eligibility constraints, Math. Probl. Eng., 2018 (2018), 12pp. doi: 10.1155/2018/6024631.

[32]

I. L. WangY. C. Wang and C. W. Chen, Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics, Flexible Services and Manufacturing Journal, 25 (2013), 343-366.  doi: 10.1007/s10696-012-9150-7.

[33]

S. WangX. WangJ. YuS. Ma and M. Liu, Bi-objective identical parallel machine scheduling to minimize total energy consumption and makespan, Journal of Cleaner Production, 193 (2018), 424-440.  doi: 10.1016/j.jclepro.2018.05.056.

[34]

J. XuX. Xu and S. Q. Xie, Recent developments in Dual Resource Constrained (DRC) system research, European Journal of Operational Research, 215 (2011), 309-318.  doi: 10.1016/j.ejor.2011.03.004.

[35]

K. C. Ying and S. W. Lin, Unrelated parallel machine scheduling with sequence-and machine-dependent setup times and due date constraints, International Journal of Innovative Computing, 8 (2012), 3279-3297. 

[36]

A. ZhangX. Qi and G. Li, Machine scheduling with soft precedence constraints, European J. Oper. Res., 282 (2020), 491-505.  doi: 10.1016/j.ejor.2019.09.041.

[37]

J. R. Zeidi and S. MohammadHosseini, Scheduling unrelated parallel machines with sequence-dependent setup times, The International Journal of Advanced Manufacturing Technology, 81 (2015), 1487-1496.  doi: 10.1007/s00170-015-7215-y.

[38]

L. ZhangQ. DengG. Gong and W. Han, A new unrelated parallel machine scheduling problem with tool changes to minimise the total energy consumption, International Journal of Production Research, 58 (2020), 6826-6845.  doi: 10.1080/00207543.2019.1685708.

[39]

Z. Zhu and X. Zhou, An efficient evolutionary grey wolf optimizer for multi-objective flexible job shop scheduling problem with hierarchical job precedence constraints, Computers & Industrial Engineering, 140 (2020), 106280.  doi: 10.1016/j.cie.2020.106280.

show all references

References:
[1]

M. Afzalirad and J. Rezaeian, Resource-constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions, Computers & Industrial Engineering, 98 (2016), 40-52.  doi: 10.1016/j.cie.2016.05.020.

[2]

M. Afzalirad and M. Shafipour, Design of an efficient genetic algorithm for resource-constrained unrelated parallel machine scheduling problem with machine eligibility restrictions, Journal of Intelligent Manufacturing, 29 (2018), 423-437.  doi: 10.1007/s10845-015-1117-6.

[3]

O. A. Arik and M. D. Toksari, Multi-objective fuzzy parallel machine scheduling problems under fuzzy job deterioration and learning effects, International Journal of Production Research, 56 (2018), 2488-2505.  doi: 10.1080/00207543.2017.1388932.

[4]

A. Baykasoglu, Applying multiple objective tabu search to continuous optimization problems with a simple neighbourhood strategy, International Journal for Numerical Methods in Engineering, 65 (2006), 406-424.  doi: 10.1002/nme.1455.

[5]

T. ÇakarR. Köker and Y. Sari, Parallel robot scheduling to minimize mean tardiness with unequal release date and precedence constraints using a hybrid intelligent system, International Journal of Advanced Robotic Systems, 9 (2012), 252.  doi: 10.5772/54381.

[6]

C. L. Chen, Iterated hybrid metaheuristic algorithms for unrelated parallel machines problem with unequal ready times and sequence-dependent setup times, The International Journal of Advanced Manufacturing Technology, 60 (2012), 693-705.  doi: 10.1007/s00170-011-3623-9.

[7]

L. P. CotaF. G. GuimarãesR. G. RibeiroI. R. MeneghiniF. B. de OliveiraM. J. Souza and P. Siarry, An adaptive multi-objective algorithm based on decomposition and large neighborhood search for a green machine scheduling problem, Swarm and Evolutionary Computation, 51 (2019), 100601.  doi: 10.1016/j.swevo.2019.100601.

[8]

M. DhiflaouiH. E. Nouri and O. B. Driss, Dual-resource constraints in classical and flexible job shop problems: A state-of-the-art review, Procedia Computer Science, 126 (2018), 1507-1515.  doi: 10.1016/j.procs.2018.08.123.

[9]

E. C. H. Dorion, J. C. F. Guimarães, E. A. Severo, Z. C. Reis and P. M. Olea, Innovation and production management through a just in sequence strategy in a multinational brazilian metal-mechanic industry, 2014 IEEE International Conference on Management of Innovation and Technology, (2014), 54–60. doi: 10.1109/ICMIT.2014.6942400.

[10]

P. Engrand, A multi-objective optimization approach based on simulated annealing and its application to nuclear fuel management, 1998.

[11]

A. E. Ezugwu, O. J. Adeleke and S. Viriri, Symbiotic organisms search algorithm for the unrelated parallel machines scheduling with sequence-dependent setup times, PloS One, 13 (2018), e0200030. doi: 10.1371/journal.pone.0200030.

[12]

A. E. Ezugwu and F. Akutsah, An improved firefly algorithm for the unrelated parallel machines scheduling problem with sequence-dependent setup times, IEEE Access, 6 (2018), 54459-54478.  doi: 10.1109/ACCESS.2018.2872110.

[13]

C. M. Fonseca, L. Paquete and M. López-Ibánez, An improved dimension-sweep algorithm for the hypervolume indicator, 2006 IEEE International Conference on Evolutionary Computation, (2006), 1157–1163. doi: 10.1109/CEC.2006.1688440.

[14]

F. Glover, Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res., 13 (1986), 533-549.  doi: 10.1016/0305-0548(86)90048-1.

[15]

F. W. Glover and G. A. Kochenberger. (Eds.), Handbook of Metaheuristics, International Series in Operations Research & Management Science, 57. Kluwer Academic Publishers, Boston, MA, 2003.

[16]

G. GongR. ChiongQ. Deng and X. Gong, A hybrid artificial bee colony algorithm for flexible job shop scheduling with worker flexibility, International Journal of Production Research, 58 (2020), 4406-4420.  doi: 10.1080/00207543.2019.1653504.

[17]

G. GongR. ChiongQ. DengW. HanL. ZhangW. Lin and K. Li, Energy-efficient flexible flow shop scheduling with worker flexibility, Expert Systems with Applications, 141 (2020), 112902.  doi: 10.1016/j.eswa.2019.112902.

[18]

A. Hamzadayi and G. Yildiz, Modeling and solving static m identical parallel machines scheduling problem with a common server and sequence dependent setup times, Computers & Industrial Engineering, 106 (2017), 287-298.  doi: 10.1016/j.cie.2017.02.013.

[19]

M. P. Hansen, Tabu search for multiobjective optimization: MOTS, Proceedings of the 13th International Conference on Multiple Criteria Decision Making, (1997), 574–586.

[20]

O. Hurdies, Just in time (JIT) production: An effective approach to efficiency, Logistics & Supply Chain Review, 1 (2020), 32-39. 

[21]

B. Van Khanh and N. Van Hop, Genetic algorithm with initial sequence for parallel machines scheduling with sequence dependent setup times based on earliness-tardiness, Journal of Industrial and Production Engineering, 38 (2021), 18-28.  doi: 10.1080/21681015.2020.1829111.

[22]

J. G. KimS. Song and B. Jeong, Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times, International Journal of Production Research, 58 (2020), 1628-1643.  doi: 10.1080/00207543.2019.1672900.

[23]

S. KirkpatrickC. D. Gelatt and M. P. Vecchi, Optimization by simulated annealing, Science, 220 (1983), 671-680.  doi: 10.1126/science.220.4598.671.

[24]

D. LeiY. YuanJ. Cai and D. Bai, An imperialist competitive algorithm with memory for distributed unrelated parallel machines scheduling, International Journal of Production Research, 58 (2020), 597-614.  doi: 10.1080/00207543.2019.1598596.

[25]

H. M. Md, Lead time reduction and process cycle improvement of an ice-cream manufacturing factory in bangladesh by using value stream map and kanban board, Australian Journal Of Basic and Applied Sciences, (2016).

[26]

A. Munoz-VillamizarJ. SantosJ. Montoya-Torres and M. Alvaréz, Improving effectiveness of parallel machine scheduling with earliness and tardiness costs: A case study, International Journal of Industrial Engineering Computations, 10 (2019), 375-392.  doi: 10.5267/j.ijiec.2019.2.001.

[27]

J. RezaeianN. DerakhshanI. Mahdavi and R. A. Foroutan, Due date assignment and JIT scheduling problem in blocking hybrid flow shop robotic cells with multiple robots and batch delivery cost, International Journal of Industrial Mathematics, 13 (2021), 145-162. 

[28]

M. Savsar, Simulation analysis of a pull-push system for an electronic assembly line, International Journal of Production Economics, 51 (1997), 205-214.  doi: 10.1016/S0925-5273(97)00055-8.

[29]

G. Taguchi, Introduction to quality engineering: Designing quality into products and processes, No. 658.562 T3, (1986).

[30]

E. Vallada and R. Ruiz, A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times, European J. Oper. Res., 211 (2011), 612-622.  doi: 10.1016/j.ejor.2011.01.011.

[31]

B. Wang and H. Wang, Multiobjective order acceptance and scheduling on unrelated parallel machines with machine eligibility constraints, Math. Probl. Eng., 2018 (2018), 12pp. doi: 10.1155/2018/6024631.

[32]

I. L. WangY. C. Wang and C. W. Chen, Scheduling unrelated parallel machines in semiconductor manufacturing by problem reduction and local search heuristics, Flexible Services and Manufacturing Journal, 25 (2013), 343-366.  doi: 10.1007/s10696-012-9150-7.

[33]

S. WangX. WangJ. YuS. Ma and M. Liu, Bi-objective identical parallel machine scheduling to minimize total energy consumption and makespan, Journal of Cleaner Production, 193 (2018), 424-440.  doi: 10.1016/j.jclepro.2018.05.056.

[34]

J. XuX. Xu and S. Q. Xie, Recent developments in Dual Resource Constrained (DRC) system research, European Journal of Operational Research, 215 (2011), 309-318.  doi: 10.1016/j.ejor.2011.03.004.

[35]

K. C. Ying and S. W. Lin, Unrelated parallel machine scheduling with sequence-and machine-dependent setup times and due date constraints, International Journal of Innovative Computing, 8 (2012), 3279-3297. 

[36]

A. ZhangX. Qi and G. Li, Machine scheduling with soft precedence constraints, European J. Oper. Res., 282 (2020), 491-505.  doi: 10.1016/j.ejor.2019.09.041.

[37]

J. R. Zeidi and S. MohammadHosseini, Scheduling unrelated parallel machines with sequence-dependent setup times, The International Journal of Advanced Manufacturing Technology, 81 (2015), 1487-1496.  doi: 10.1007/s00170-015-7215-y.

[38]

L. ZhangQ. DengG. Gong and W. Han, A new unrelated parallel machine scheduling problem with tool changes to minimise the total energy consumption, International Journal of Production Research, 58 (2020), 6826-6845.  doi: 10.1080/00207543.2019.1685708.

[39]

Z. Zhu and X. Zhou, An efficient evolutionary grey wolf optimizer for multi-objective flexible job shop scheduling problem with hierarchical job precedence constraints, Computers & Industrial Engineering, 140 (2020), 106280.  doi: 10.1016/j.cie.2020.106280.

Figure 1.  Results of the test problem with $n = 8, m = 2$, and $w = 2$
Figure 2.  The results of validation of solutions quality
Figure 3.  The flowchart of the MOTS algorithm [4]
Figure 4.  Representation of a chromosome with $n = 10$, $m = 3$ and $k = 2$
Figure 5.  An example of the precedence constraints
Figure 6.  The implementation steps of the correcting algorithm
Figure 7.  The swap operator
Figure 8.  The reversion operator
Figure 9.  The workers relocation operator
Figure 10.  Pareto fronts of all three proposed metaheuristics, a medium test problem ($n = 20, m = 6, w = 5$)
Figure 11.  Pareto fronts of all three proposed metaheuristics, a large test problem ($n = 30, m = 10, w = 6$)
Figure 12.  Comparison of the hypervolume indicator for the problems of all sizes
Figure 13.  Hypervolumes comparison, a medium test problem $(n = 20, m = 6, w = 5)$
Figure 14.  Hypervolumes comparison, a large test problem $(n = 30, m = 10, w = 6)$
Figure 15.  Pareto fronts of MOTS in previous iterations
Figure 16.  Pareto fronts of MOSA in previous iterations
Figure 17.  Pareto fronts of hybrid algorithm in previous iterations
Figure 18.  The convergence curve of the proposed MOTS
Figure 19.  The convergence curve of the proposed MOSA
Figure 20.  The convergence curve of the proposed hybrid algorithm
Figure 21.  The last significant change in the Pareto front of the proposed hybrid algorithm
Table 1.  A comparison of some most recent studies existing in the literature
Constraints
Reference Unrelated Parallel machines Worker flexibility/ allocation Machine eligibility Sequence dependent setup times Precedence constraints Objective function(s) Solution approach(es)
Cota et al. [7] Yes No No Yes No Makespan; Total energy consumption ALNS, LA, MO-ALNS, MO-ALNS/D
Zhu and Zhou [39] No No No No Yes Makespan; Total workload; Maximum machine workload EMOGWO
Munoz-Villamizar et al. [26] No No No Yes No Makespan; Total earliness and tardiness; Cost minimization; Effectiveness optimization GAMS solver
Arık and Toksarı [3] No No No No No Total tardiness penalty cost; Earliness penalty cost; Cost of setting due dates A fuzzy local search algorithm
Gong et al. [17] No Yes No No No Makespan; Total worker cost; Green production indicator A hybrid evolutionary algorithm
Zhang et al. [36] No No No No Yes Total penalties; Makespan; Total completion time Approximation algorithms
Gong et al. [16] No Yes No No No Makespan A hybrid artificial bee colony
Wang et al. [33] No No No No No Total energy consumption; Makespan An augmented $ \varepsilon $-constraint; A heuristic method; NSGA-II
Zhang et al. [38] Yes No No No No Total energy consumption; Makespan A heuristic evolutionary algorithm
Lei et al. [24] Yes No No No No Makespan An imperialist competitive algorithm
Khanh Van and Van Hop [21] Yes No No Yes No Total weighted earliness and tardiness; Makespan A hybrid algorithm based on GA and ISETP
Kim et al. [22] No No No Yes Yes Total tardiness SA, GA
This paper Yes Yes Yes Yes Yes Cost of tardiness; Cost of hiring workers MOTS, MOSA, A hybrid evolutionary algorithm
Constraints
Reference Unrelated Parallel machines Worker flexibility/ allocation Machine eligibility Sequence dependent setup times Precedence constraints Objective function(s) Solution approach(es)
Cota et al. [7] Yes No No Yes No Makespan; Total energy consumption ALNS, LA, MO-ALNS, MO-ALNS/D
Zhu and Zhou [39] No No No No Yes Makespan; Total workload; Maximum machine workload EMOGWO
Munoz-Villamizar et al. [26] No No No Yes No Makespan; Total earliness and tardiness; Cost minimization; Effectiveness optimization GAMS solver
Arık and Toksarı [3] No No No No No Total tardiness penalty cost; Earliness penalty cost; Cost of setting due dates A fuzzy local search algorithm
Gong et al. [17] No Yes No No No Makespan; Total worker cost; Green production indicator A hybrid evolutionary algorithm
Zhang et al. [36] No No No No Yes Total penalties; Makespan; Total completion time Approximation algorithms
Gong et al. [16] No Yes No No No Makespan A hybrid artificial bee colony
Wang et al. [33] No No No No No Total energy consumption; Makespan An augmented $ \varepsilon $-constraint; A heuristic method; NSGA-II
Zhang et al. [38] Yes No No No No Total energy consumption; Makespan A heuristic evolutionary algorithm
Lei et al. [24] Yes No No No No Makespan An imperialist competitive algorithm
Khanh Van and Van Hop [21] Yes No No Yes No Total weighted earliness and tardiness; Makespan A hybrid algorithm based on GA and ISETP
Kim et al. [22] No No No Yes Yes Total tardiness SA, GA
This paper Yes Yes Yes Yes Yes Cost of tardiness; Cost of hiring workers MOTS, MOSA, A hybrid evolutionary algorithm
Table 2.  Processing time ($ T_{il} $) of the jobs
$ J_1 $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $ $ J_8 $
$ M_1 $ $ 0 $ $ 4 $ $ 2 $ $ 1 $ $ 5 $ $ 3 $ $ 5 $ $ 4 $
$ M_2 $ $ 0 $ $ 3 $ $ 5 $ $ 8 $ $ 2 $ $ 2 $ $ 6 $ $ 3 $
$ M_3 $ $ 0 $ $ 1 $ $ 5 $ $ 4 $ $ 4 $ $ 2 $ $ 3 $ $ 3 $
$ J_1 $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $ $ J_8 $
$ M_1 $ $ 0 $ $ 4 $ $ 2 $ $ 1 $ $ 5 $ $ 3 $ $ 5 $ $ 4 $
$ M_2 $ $ 0 $ $ 3 $ $ 5 $ $ 8 $ $ 2 $ $ 2 $ $ 6 $ $ 3 $
$ M_3 $ $ 0 $ $ 1 $ $ 5 $ $ 4 $ $ 4 $ $ 2 $ $ 3 $ $ 3 $
Table 3.  Delivery time and tardiness penalty of the jobs
$ J_1 $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $ $ J_8 $
$ D_j $ $ 10 $ $ 13 $ $ 8 $ $ 15 $ $ 6 $ $ 16 $ $ 14 $ $ 18 $
$ \beta_j $ $ 4 $ $ 3 $ $ 7 $ $ 5 $ $ 9 $ $ 8 $ $ 6 $ $ 2 $
$ J_1 $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $ $ J_8 $
$ D_j $ $ 10 $ $ 13 $ $ 8 $ $ 15 $ $ 6 $ $ 16 $ $ 14 $ $ 18 $
$ \beta_j $ $ 4 $ $ 3 $ $ 7 $ $ 5 $ $ 9 $ $ 8 $ $ 6 $ $ 2 $
Table 4.  Setup time for each machine
$ (j, l)\in A $ $ J_{l=1} $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $ $ J_8 $
$ J_{j=1} $ $ 3 $ $ 3 $ $ 1 $ $ 3 $ $ 3 $ $ 1 $ $ 3 $ $ 1 $
$ J_2 $ $ 3 $ $ 2 $ $ 3 $ $ 1 $ $ 3 $ $ 1 $ $ 3 $ $ 2 $
$ J_3 $ $ 3 $ $ 1 $ $ 1 $ $ 2 $ $ 3 $ $ 3 $ $ 2 $ $ 1 $
$ J_4 $ $ 3 $ $ 2 $ $ 2 $ $ 3 $ $ 3 $ $ 3 $ $ 1 $ $ 3 $
$ M_1 $ $ J_5 $ $ 2 $ $ 2 $ $ 1 $ $ 2 $ $ 3 $ $ 1 $ $ 1 $ $ 3 $
$ J_6 $ $ 1 $ $ 3 $ $ 1 $ $ 3 $ $ 1 $ $ 1 $ $ 2 $ $ 2 $
$ J_7 $ $ 2 $ $ 1 $ $ 2 $ $ 3 $ $ 2 $ $ 1 $ $ 1 $ $ 1 $
$ J_8 $ $ 2 $ $ 2 $ $ 1 $ $ 3 $ $ 2 $ $ 1 $ $ 2 $ $ 1 $
$ (j, l)\in A $ $ J_{l=1} $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $ $ J_8 $
$ J_1 $ $ 3 $ $ 2 $ $ 2 $ $ 1 $ $ 2 $ $ 2 $ $ 1 $ $ 3 $
$ J_2 $ $ 3 $ $ 2 $ $ 1 $ $ 1 $ $ 1 $ $ 2 $ $ 3 $ $ 2 $
$ J_3 $ $ 3 $ $ 2 $ $ 2 $ $ 2 $ $ 1 $ $ 3 $ $ 1 $ $ 3 $
$ J_4 $ $ 1 $ $ 1 $ $ 2 $ $ 2 $ $ 1 $ $ 2 $ $ 1 $ $ 3 $
$ M_2 $ $ J_5 $ $ 2 $ $ 1 $ $ 2 $ $ 1 $ $ 3 $ $ 1 $ $ 3 $ $ 1 $
$ J_6 $ $ 3 $ $ 3 $ $ 2 $ $ 2 $ $ 1 $ $ 3 $ $ 1 $ $ 2 $
$ J_7 $ $ 1 $ $ 1 $ $ 1 $ $ 2 $ $ 3 $ $ 3 $ $ 2 $ $ 3 $
$ J_8 $ $ 1 $ $ 3 $ $ 1 $ $ 2 $ $ 1 $ $ 3 $ $ 2 $ $ 3 $
$ (j, l)\in A $ $ J_{l=1} $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $ $ J_8 $
$ J_1 $ $ 1 $ $ 1 $ $ 3 $ $ 3 $ $ 1 $ $ 3 $ $ 2 $ $ 3 $
$ J_2 $ $ 3 $ $ 1 $ $ 1 $ $ 3 $ $ 3 $ $ 2 $ $ 1 $ $ 2 $
$ J_3 $ $ 1 $ $ 1 $ $ 3 $ $ 1 $ $ 2 $ $ 3 $ $ 1 $ $ 1 $
$ J_4 $ $ 3 $ $ 1 $ $ 2 $ $ 2 $ $ 3 $ $ 2 $ $ 2 $ $ 1 $
$ M_3 $ $ J_5 $ $ 1 $ $ 3 $ $ 1 $ $ 2 $ $ 2 $ $ 3 $ $ 2 $ $ 2 $
$ J_6 $ $ 1 $ $ 3 $ $ 1 $ $ 3 $ $ 1 $ $ 2 $ $ 3 $ $ 2 $
$ J_7 $ $ 1 $ $ 1 $ $ 3 $ $ 2 $ $ 2 $ $ 2 $ $ 1 $ $ 3 $
$ J_8 $ $ 1 $ $ 1 $ $ 2 $ $ 2 $ $ 3 $ $ 1 $ $ 3 $ $ 3 $
$ (j, l)\in A $ $ J_{l=1} $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $ $ J_8 $
$ J_{j=1} $ $ 3 $ $ 3 $ $ 1 $ $ 3 $ $ 3 $ $ 1 $ $ 3 $ $ 1 $
$ J_2 $ $ 3 $ $ 2 $ $ 3 $ $ 1 $ $ 3 $ $ 1 $ $ 3 $ $ 2 $
$ J_3 $ $ 3 $ $ 1 $ $ 1 $ $ 2 $ $ 3 $ $ 3 $ $ 2 $ $ 1 $
$ J_4 $ $ 3 $ $ 2 $ $ 2 $ $ 3 $ $ 3 $ $ 3 $ $ 1 $ $ 3 $
$ M_1 $ $ J_5 $ $ 2 $ $ 2 $ $ 1 $ $ 2 $ $ 3 $ $ 1 $ $ 1 $ $ 3 $
$ J_6 $ $ 1 $ $ 3 $ $ 1 $ $ 3 $ $ 1 $ $ 1 $ $ 2 $ $ 2 $
$ J_7 $ $ 2 $ $ 1 $ $ 2 $ $ 3 $ $ 2 $ $ 1 $ $ 1 $ $ 1 $
$ J_8 $ $ 2 $ $ 2 $ $ 1 $ $ 3 $ $ 2 $ $ 1 $ $ 2 $ $ 1 $
$ (j, l)\in A $ $ J_{l=1} $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $ $ J_8 $
$ J_1 $ $ 3 $ $ 2 $ $ 2 $ $ 1 $ $ 2 $ $ 2 $ $ 1 $ $ 3 $
$ J_2 $ $ 3 $ $ 2 $ $ 1 $ $ 1 $ $ 1 $ $ 2 $ $ 3 $ $ 2 $
$ J_3 $ $ 3 $ $ 2 $ $ 2 $ $ 2 $ $ 1 $ $ 3 $ $ 1 $ $ 3 $
$ J_4 $ $ 1 $ $ 1 $ $ 2 $ $ 2 $ $ 1 $ $ 2 $ $ 1 $ $ 3 $
$ M_2 $ $ J_5 $ $ 2 $ $ 1 $ $ 2 $ $ 1 $ $ 3 $ $ 1 $ $ 3 $ $ 1 $
$ J_6 $ $ 3 $ $ 3 $ $ 2 $ $ 2 $ $ 1 $ $ 3 $ $ 1 $ $ 2 $
$ J_7 $ $ 1 $ $ 1 $ $ 1 $ $ 2 $ $ 3 $ $ 3 $ $ 2 $ $ 3 $
$ J_8 $ $ 1 $ $ 3 $ $ 1 $ $ 2 $ $ 1 $ $ 3 $ $ 2 $ $ 3 $
$ (j, l)\in A $ $ J_{l=1} $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $ $ J_8 $
$ J_1 $ $ 1 $ $ 1 $ $ 3 $ $ 3 $ $ 1 $ $ 3 $ $ 2 $ $ 3 $
$ J_2 $ $ 3 $ $ 1 $ $ 1 $ $ 3 $ $ 3 $ $ 2 $ $ 1 $ $ 2 $
$ J_3 $ $ 1 $ $ 1 $ $ 3 $ $ 1 $ $ 2 $ $ 3 $ $ 1 $ $ 1 $
$ J_4 $ $ 3 $ $ 1 $ $ 2 $ $ 2 $ $ 3 $ $ 2 $ $ 2 $ $ 1 $
$ M_3 $ $ J_5 $ $ 1 $ $ 3 $ $ 1 $ $ 2 $ $ 2 $ $ 3 $ $ 2 $ $ 2 $
$ J_6 $ $ 1 $ $ 3 $ $ 1 $ $ 3 $ $ 1 $ $ 2 $ $ 3 $ $ 2 $
$ J_7 $ $ 1 $ $ 1 $ $ 3 $ $ 2 $ $ 2 $ $ 2 $ $ 1 $ $ 3 $
$ J_8 $ $ 1 $ $ 1 $ $ 2 $ $ 2 $ $ 3 $ $ 1 $ $ 3 $ $ 3 $
Table 5.  The availability of $ Y_{il} $s
$ J_1 $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $ $ J_8 $
$ M_1 $ $ \star $ $ \star $ $ \star $ $ \star $ $ \star $ $ \star $
$ M_2 $ $ \star $ $ \star $ $ \star $ $ \star $ $ \star $
$ M_3 $ $ \star $ $ \star $ $ \star $ $ \star $
$ J_1 $ $ J_2 $ $ J_3 $ $ J_4 $ $ J_5 $ $ J_6 $ $ J_7 $ $ J_8 $
$ M_1 $ $ \star $ $ \star $ $ \star $ $ \star $ $ \star $ $ \star $
$ M_2 $ $ \star $ $ \star $ $ \star $ $ \star $ $ \star $
$ M_3 $ $ \star $ $ \star $ $ \star $ $ \star $
Table 6.  Results of the first test problem
Job $ S_{ikjl} $ $ CS_l $ $ C_l $ $ T_{il} $ $ T_l $ $ X_{ikjl}=1 $
$ 1 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ X_{1213} $
$ 2 $ $ 1.2 $ $ 10 $ $ 14 $ $ 4 $ $ 1 $ $ X_{1228} $
$ 3 $ $ 1.2 $ $ 6 $ $ 8 $ $ 2 $ $ 0 $ $ X_{1232} $
$ 4 $ $ 2.4 $ $ 17 $ $ 25 $ $ 8 $ $ 10 $ $ X_{2217} $
$ 5 $ $ 1.2 $ $ 2 $ $ 6 $ $ 4 $ $ 0 $ $ X_{2274} $
$ 6 $ $ 3.6 $ $ 14 $ $ 16 $ $ 2 $ $ 0 $ $ X_{3215} $
$ 7 $ $ 1.2 $ $ 4 $ $ 14 $ $ 6 $ $ 0 $ $ X_{3256} $
$ 8 $ $ 2.4 $ $ 20 $ $ 24 $ $ 4 $ $ 6 $
$ F=0.6\star f_1+0.4\star f_2=39+448=487 $
Job $ S_{ikjl} $ $ CS_l $ $ C_l $ $ T_{il} $ $ T_l $ $ X_{ikjl}=1 $
$ 1 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ 0 $ $ X_{1213} $
$ 2 $ $ 1.2 $ $ 10 $ $ 14 $ $ 4 $ $ 1 $ $ X_{1228} $
$ 3 $ $ 1.2 $ $ 6 $ $ 8 $ $ 2 $ $ 0 $ $ X_{1232} $
$ 4 $ $ 2.4 $ $ 17 $ $ 25 $ $ 8 $ $ 10 $ $ X_{2217} $
$ 5 $ $ 1.2 $ $ 2 $ $ 6 $ $ 4 $ $ 0 $ $ X_{2274} $
$ 6 $ $ 3.6 $ $ 14 $ $ 16 $ $ 2 $ $ 0 $ $ X_{3215} $
$ 7 $ $ 1.2 $ $ 4 $ $ 14 $ $ 6 $ $ 0 $ $ X_{3256} $
$ 8 $ $ 2.4 $ $ 20 $ $ 24 $ $ 4 $ $ 6 $
$ F=0.6\star f_1+0.4\star f_2=39+448=487 $
Table 7.  Test problems used to validate the quality of solutions
Test Problem $ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 5 $ $ 6 $ $ 7 $ $ 8 $ $ 9 $ $ 10 $
$ (n, m, w) $ $ (4, 2, 2) $ $ (5, 3, 2) $ $ (5, 2, 2) $ $ (6, 3, 2) $ $ (6, 2, 2) $ $ (6, 2, 2) $ $ (7, 2, 2) $ $ (7, 2, 3) $ $ (7, 2, 3) $ $ (8, 2, 2) $
with constraints
without constraints
Test Problem $ 1 $ $ 2 $ $ 3 $ $ 4 $ $ 5 $ $ 6 $ $ 7 $ $ 8 $ $ 9 $ $ 10 $
$ (n, m, w) $ $ (4, 2, 2) $ $ (5, 3, 2) $ $ (5, 2, 2) $ $ (6, 3, 2) $ $ (6, 2, 2) $ $ (6, 2, 2) $ $ (7, 2, 2) $ $ (7, 2, 3) $ $ (7, 2, 3) $ $ (8, 2, 2) $
with constraints
without constraints
Table 8.  Input data for test problems
Parameter Generating function
Jobs processing time $ T_{il}\sim U[5\;\;15] $
Jobs delivery time $ D_j\sim [20\;\;40] $
Setup times $ S_{ijl}\sim [1\;\;7] $
Jobs tardiness penalties $ \beta_j\sim [1\;\;10] $
Worker's skill $ \pi_k\sim rand (0.5, 1.5) $
Parameter Generating function
Jobs processing time $ T_{il}\sim U[5\;\;15] $
Jobs delivery time $ D_j\sim [20\;\;40] $
Setup times $ S_{ijl}\sim [1\;\;7] $
Jobs tardiness penalties $ \beta_j\sim [1\;\;10] $
Worker's skill $ \pi_k\sim rand (0.5, 1.5) $
Table 9.  Levels of the controller parameters
Algorithm Parameter Levels
MOTS $ Tabu_{list} $ $ 2, \;4, \;6 $
$ N_{new} $ $ 10, \;20, \;40 $
$ max_{it} $ $ 30, \;50, \;70 $
MOSA $ max_{it} $ $ 100, \;200, \;300 $
$ Sub_{it} $ $ 20, \;25, \;30 $
$ T_0 $ $ 60, \;100, \;150 $
$ \alpha $ $ 0.93, \;0.95, \;0.99 $
Hybrid $ Tabu_{list} $ $ 2, \;4, \;5 $
$ max_{it} $ $ 70, \;150, \;200 $
$ Sub_{it} $ $ 20, \;25, \;30 $
$ T_0 $ $ 80, \;100, \;150 $
$ \alpha $ $ 0.93, \;0.95, \;0.99 $
Algorithm Parameter Levels
MOTS $ Tabu_{list} $ $ 2, \;4, \;6 $
$ N_{new} $ $ 10, \;20, \;40 $
$ max_{it} $ $ 30, \;50, \;70 $
MOSA $ max_{it} $ $ 100, \;200, \;300 $
$ Sub_{it} $ $ 20, \;25, \;30 $
$ T_0 $ $ 60, \;100, \;150 $
$ \alpha $ $ 0.93, \;0.95, \;0.99 $
Hybrid $ Tabu_{list} $ $ 2, \;4, \;5 $
$ max_{it} $ $ 70, \;150, \;200 $
$ Sub_{it} $ $ 20, \;25, \;30 $
$ T_0 $ $ 80, \;100, \;150 $
$ \alpha $ $ 0.93, \;0.95, \;0.99 $
Table 10.  Ranking of factors (based on $ SN $ ratios and mean of responses) and their best values for each algorithm
Algorithm Parameter Rank ($ S/N $ ratios) Rank (Means) Best value
MOTS $ Tabu_{list} $ $ 3 $ $ 3 $ $ 4 $
$ N_{new} $ $ 2 $ $ 2 $ $ 40 $
$ max_{it} $ $ 1 $ $ 1 $ $ 70 $
MOSA $ max_{it} $ $ 1 $ $ 1 $ $ 200 $
$ Sub_{it} $ $ 2 $ $ 2 $ $ 25 $
$ T_0 $ $ 4 $ $ 4 $ $ 100 $
$ \alpha $ $ 3 $ $ 3 $ $ 0.93 $
Hybrid $ Tabu_{list} $ $ 1 $ $ 2 $ $ 5 $
$ max_{it} $ $ 3 $ $ 1 $ $ 70 $
$ Sub_{it} $ $ 2 $ $ 3 $ $ 25 $
$ T_0 $ $ 4 $ $ 4 $ $ 150 $
$ \alpha $ $ 5 $ $ 5 $ $ 0.93 $
Algorithm Parameter Rank ($ S/N $ ratios) Rank (Means) Best value
MOTS $ Tabu_{list} $ $ 3 $ $ 3 $ $ 4 $
$ N_{new} $ $ 2 $ $ 2 $ $ 40 $
$ max_{it} $ $ 1 $ $ 1 $ $ 70 $
MOSA $ max_{it} $ $ 1 $ $ 1 $ $ 200 $
$ Sub_{it} $ $ 2 $ $ 2 $ $ 25 $
$ T_0 $ $ 4 $ $ 4 $ $ 100 $
$ \alpha $ $ 3 $ $ 3 $ $ 0.93 $
Hybrid $ Tabu_{list} $ $ 1 $ $ 2 $ $ 5 $
$ max_{it} $ $ 3 $ $ 1 $ $ 70 $
$ Sub_{it} $ $ 2 $ $ 3 $ $ 25 $
$ T_0 $ $ 4 $ $ 4 $ $ 150 $
$ \alpha $ $ 5 $ $ 5 $ $ 0.93 $
Table 11.  Computational results for the problems of all sizes: MOTS & MOSA
Problem $ (n, m, w) $ Obj. functions MOTS MOSA
P1* P2 P3 P4 P1 P2 P3
$ (8, 2, 2) $ f1 710 826 1661 1968
f2 4853 4769 4769 4769
$ (8, 3, 2) $ f1 856 898 1550
f2 3656 4418 4418
$ (10, 3, 2) $ f1 1063 1433
f2 3662 4880
$ (10, 3, 3) $ f1 731 4762
f2 3065 3438
$ (10, 4, 2) $ f1 983 1252 6937 6937
f2 5719 5314 2055 2229
$ (12, 3, 2) $ f1 1460 3990
f2 6532 5869
$ (12, 3, 3) $ f1 681 815 3837
f2 6358 5880 5557
$ (12, 4, 2) $ f1 1207 1233 5487
f2 6445 6184 5399
$ (15, 4, 3) $ f1 480 527 924 4346 4560
f2 10760 10542 10092 9807 9807
$ (15, 6, 3) $ f1 2156 2176 2196 2579 5527
f2 9484 9224 8963 8703 9475
$ (20, 4, 3) $ f1 6317 13816
f2 6943 9658
$ (20, 6, 5) $ f1 2894 3466 3719 11392 12469
f2 8410 7044 6702 9826 9826
$ (25, 4, 3) $ f1 12610 20565
f2 7749 12725
$ (25, 6, 5) $ f1 3715 16032 16037
f2 8823 11685 11685
$ (30, 8, 4) $ f1 4133 4560 19549 21010 22219
f2 14096 13584 15081 15081 15081
$ (30, 10, 6) $ f1 3190 3444 3961 23057 25436
f2 13499 12942 12632 14132 14132
$ (40, 10, 6) $ f1 8993 9944 38190 40236
f2 17455 17182 21838 21838
$ (40, 12, 8) $ f1 6334 6421 7055 44881 31799
f2 18491 18383 18187 19731 19731
$ (50, 12, 8) $ f1 13801 14655 73855 78444 80185
f2 19918 19450 19905 19905 19905
$ (50, 15, 10) $ f1 11484 13550 47375 51987 59331
f2 22310 21220 26906 26906 26906
$ P_z, (z = 1, 2, …, Z) $ denotes the $ z $th pareto solution.
Problem $ (n, m, w) $ Obj. functions MOTS MOSA
P1* P2 P3 P4 P1 P2 P3
$ (8, 2, 2) $ f1 710 826 1661 1968
f2 4853 4769 4769 4769
$ (8, 3, 2) $ f1 856 898 1550
f2 3656 4418 4418
$ (10, 3, 2) $ f1 1063 1433
f2 3662 4880
$ (10, 3, 3) $ f1 731 4762
f2 3065 3438
$ (10, 4, 2) $ f1 983 1252 6937 6937
f2 5719 5314 2055 2229
$ (12, 3, 2) $ f1 1460 3990
f2 6532 5869
$ (12, 3, 3) $ f1 681 815 3837
f2 6358 5880 5557
$ (12, 4, 2) $ f1 1207 1233 5487
f2 6445 6184 5399
$ (15, 4, 3) $ f1 480 527 924 4346 4560
f2 10760 10542 10092 9807 9807
$ (15, 6, 3) $ f1 2156 2176 2196 2579 5527
f2 9484 9224 8963 8703 9475
$ (20, 4, 3) $ f1 6317 13816
f2 6943 9658
$ (20, 6, 5) $ f1 2894 3466 3719 11392 12469
f2 8410 7044 6702 9826 9826
$ (25, 4, 3) $ f1 12610 20565
f2 7749 12725
$ (25, 6, 5) $ f1 3715 16032 16037
f2 8823 11685 11685
$ (30, 8, 4) $ f1 4133 4560 19549 21010 22219
f2 14096 13584 15081 15081 15081
$ (30, 10, 6) $ f1 3190 3444 3961 23057 25436
f2 13499 12942 12632 14132 14132
$ (40, 10, 6) $ f1 8993 9944 38190 40236
f2 17455 17182 21838 21838
$ (40, 12, 8) $ f1 6334 6421 7055 44881 31799
f2 18491 18383 18187 19731 19731
$ (50, 12, 8) $ f1 13801 14655 73855 78444 80185
f2 19918 19450 19905 19905 19905
$ (50, 15, 10) $ f1 11484 13550 47375 51987 59331
f2 22310 21220 26906 26906 26906
$ P_z, (z = 1, 2, …, Z) $ denotes the $ z $th pareto solution.
Table 12.  Computational results for the problems of all sizes: The proposed hybrid
Problem $ (n, m, w) $ Obj. functions Hybrid
P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11
$ (8, 2, 2) $ f1 1524 1553 1617
f2 5191 5107 5022
$ (8, 3, 2) $ f1 1216 1400 1624 1961
f2 4266 4266 4113 3961
$ (10, 3, 2) $ f1 989 1405 1677 1711 1791 1867 1870 1896
f2 6097 5793 5793 5488 5184 5184 4880 4575
$ (10, 3, 3) $ f1 2443 2586 2671 2695 2702 2704
f2 3295 3295 3208 3152 3152 3065
$ (10, 4, 2) $ f1 858 1047 1196 1330 1452 1601
f2 6531 6531 6328 6125 5922 5719
$ (12, 3, 2) $ f1 2106 2400 2491 2841 2946
f2 7526 7195 6863 6532 6201
$ (12, 3, 3) $ f1 1428 2331 2669 2690 3088 3109 3258 3279 3334 3438
f2 8268 7790 7313 7046 6835 6568 6358 6091 5880 5613
$ (12, 4, 2) $ f1 3812 3829
f2 6707 6184
$ (15, 4, 3) $ f1 2871 3015 3589 3610 3617 3618 3619
f2 1080 1080 1078 1077 1074 1054 1052
$ (15, 6, 3) $ f1 2100 2313 2576 2600
f2 9739 9739 9484 9483
$ (20, 4, 3) $ f1 6887 6979 7519
f2 11292 10078 9755
$ (20, 6, 5) $ f1 5712 7395 7406 7445 9537 9551 9718 9740 10162 10176 10365
f2 9718 9718 9587 9518 9518 9386 9309 9253 9044 8782 8779
$ (25, 4, 3) $ f1 11769 11826 12126 13470 17244 17665
f2 10769 10769 10598 10598 10598 10237
$ (25, 6, 5) $ f1 5851 6530 6679 6684 8501 8534 8715 9107 9122
f2 10561 10561 10389 10266 10240 10117 10114 10114 9991
$ (30, 8, 4) $ f1 13183 13805 13942 14068 15660 16033 17741 17785
f2 16567 16411 16391 16211 16191 16010 15498 15142
$ (30, 10, 6) $ f1 10899 10951 10968 13811 17298 18530 18552
f2 15173 15031 14762 14762 14566 14084 13899
$ (40, 10, 6) $ f1 21130 22146 23254
f2 25930 25229 24604
$ (40, 12, 8) $ f1 18544 18551 20567 20619 20629 21045
f2 21022 20914 20914 20910 20866 20866
$ (50, 12, 8) $ f1 47230 47348 60202 62672
f2 23776 23729 23456 21764
$ (50, 15, 10) $ f1 18791 23480 26830 28710 28254 29460
f2 28995 28995 28637 28376 28302 28202
Problem $ (n, m, w) $ Obj. functions Hybrid
P1 P2 P3 P4 P5 P6 P7 P8 P9 P10 P11
$ (8, 2, 2) $ f1 1524 1553 1617
f2 5191 5107 5022
$ (8, 3, 2) $ f1 1216 1400 1624 1961
f2 4266 4266 4113 3961
$ (10, 3, 2) $ f1 989 1405 1677 1711 1791 1867 1870 1896
f2 6097 5793 5793 5488 5184 5184 4880 4575
$ (10, 3, 3) $ f1 2443 2586 2671 2695 2702 2704
f2 3295 3295 3208 3152 3152 3065
$ (10, 4, 2) $ f1 858 1047 1196 1330 1452 1601
f2 6531 6531 6328 6125 5922 5719
$ (12, 3, 2) $ f1 2106 2400 2491 2841 2946
f2 7526 7195 6863 6532 6201
$ (12, 3, 3) $ f1 1428 2331 2669 2690 3088 3109 3258 3279 3334 3438
f2 8268 7790 7313 7046 6835 6568 6358 6091 5880 5613
$ (12, 4, 2) $ f1 3812 3829
f2 6707 6184
$ (15, 4, 3) $ f1 2871 3015 3589 3610 3617 3618 3619
f2 1080 1080 1078 1077 1074 1054 1052
$ (15, 6, 3) $ f1 2100 2313 2576 2600
f2 9739 9739 9484 9483
$ (20, 4, 3) $ f1 6887 6979 7519
f2 11292 10078 9755
$ (20, 6, 5) $ f1 5712 7395 7406 7445 9537 9551 9718 9740 10162 10176 10365
f2 9718 9718 9587 9518 9518 9386 9309 9253 9044 8782 8779
$ (25, 4, 3) $ f1 11769 11826 12126 13470 17244 17665
f2 10769 10769 10598 10598 10598 10237
$ (25, 6, 5) $ f1 5851 6530 6679 6684 8501 8534 8715 9107 9122
f2 10561 10561 10389 10266 10240 10117 10114 10114 9991
$ (30, 8, 4) $ f1 13183 13805 13942 14068 15660 16033 17741 17785
f2 16567 16411 16391 16211 16191 16010 15498 15142
$ (30, 10, 6) $ f1 10899 10951 10968 13811 17298 18530 18552
f2 15173 15031 14762 14762 14566 14084 13899
$ (40, 10, 6) $ f1 21130 22146 23254
f2 25930 25229 24604
$ (40, 12, 8) $ f1 18544 18551 20567 20619 20629 21045
f2 21022 20914 20914 20910 20866 20866
$ (50, 12, 8) $ f1 47230 47348 60202 62672
f2 23776 23729 23456 21764
$ (50, 15, 10) $ f1 18791 23480 26830 28710 28254 29460
f2 28995 28995 28637 28376 28302 28202
Table 13.  Hypervolume indicator for the problems of all sizes
Table 14.  Comparisons results for the problems of all sizes
Table 15.  One-way ANOVA for all test problems (between groups)
Metric Problem size Sum of Squares df Mean Square F. Sig.
S-metric Small 8758922.903 2 4379461.452 5.519 0.012
Medium 8.541E7 2 4.271E7 3.688 0.050
Large 1.348E9 2 6.739E8 6.716 0.008
NP Small 130.083 2 65.042 24.500 0.000
Medium 81.333 2 40.667 7.562 0.005
Large 42.333 2 21.167 15.744 0.000
MID Small 6748717.583 2 3374358.792 2.312 0.124
Medium 1.932E8 2 9.662E7 4.538 0.029
Large 2.856E9 2 1.428E9 11.064 0.001
DM Small 8430960.250 2 4215480.125 10.568 0.001
Medium 7.217E7 2 3.608E7 7.737 0.005
Large 1.954E8 2 9.768E7 5.840 0.013
SNS Small 122196.583 2 61098.292 5.399 0.013
Medium 1.564E7 2 7817526.167 2.349 0.130
Large 1.236E7 2 6179340.222 0.094 0.911
Time Small 20371.750 2 10185.875 21.221 0.000
Medium 43694.111 2 21847.056 6.425 0.010
Large 177652.111 2 88826.056 10.736 0.001
Metric Problem size Sum of Squares df Mean Square F. Sig.
S-metric Small 8758922.903 2 4379461.452 5.519 0.012
Medium 8.541E7 2 4.271E7 3.688 0.050
Large 1.348E9 2 6.739E8 6.716 0.008
NP Small 130.083 2 65.042 24.500 0.000
Medium 81.333 2 40.667 7.562 0.005
Large 42.333 2 21.167 15.744 0.000
MID Small 6748717.583 2 3374358.792 2.312 0.124
Medium 1.932E8 2 9.662E7 4.538 0.029
Large 2.856E9 2 1.428E9 11.064 0.001
DM Small 8430960.250 2 4215480.125 10.568 0.001
Medium 7.217E7 2 3.608E7 7.737 0.005
Large 1.954E8 2 9.768E7 5.840 0.013
SNS Small 122196.583 2 61098.292 5.399 0.013
Medium 1.564E7 2 7817526.167 2.349 0.130
Large 1.236E7 2 6179340.222 0.094 0.911
Time Small 20371.750 2 10185.875 21.221 0.000
Medium 43694.111 2 21847.056 6.425 0.010
Large 177652.111 2 88826.056 10.736 0.001
Table 16.  Results of post-hoc comparisons
Small Medium Large
Metrics Order of best performances Significant difference Order of best performances Significant difference Order of best performances Significant difference
S-metric MOTS-Hybrid-MOSA MOTS-MOSA MOTS-Hybrid-MOSA MOTS-MOSA MOTS-Hybrid-MOSA MOTS-MOSA
NPS Hybrid-MOTS-MOSA Hybrid-MOSA, Hybrid-MOTS Hybrid-MOTS-MOSA - Hybrid-MOSA-MOTS Hybrid-MOSA, Hybrid-MOTS
MID Hybrid-MOTS-MOSA - MOTS-Hybrid-MOSA MOTS-MOSA MOTS-Hybrid-MOSA MOTS-MOSA
DM Hybrid-MOTS-MOSA Hybrid-MOSA, Hybrid-MOTS Hybrid-MOTS-MOSA - Hybrid-MOSA-MOTS Hybrid-MOTS
SNS Hybrid-MOTS-MOSA Hybrid-MOSA Hybrid-MOTS-MOSA - Hybrid-MOSA-MOTS -
Time Hybrid-MOSA-MOTS Hybrid-MOSA, Hybrid-MOTS Hybrid-MOSA-MOTS Hybrid-MOTS Hybrid-MOSA-MOTS Hybrid-MOSA, Hybrid-MOTS
Small Medium Large
Metrics Order of best performances Significant difference Order of best performances Significant difference Order of best performances Significant difference
S-metric MOTS-Hybrid-MOSA MOTS-MOSA MOTS-Hybrid-MOSA MOTS-MOSA MOTS-Hybrid-MOSA MOTS-MOSA
NPS Hybrid-MOTS-MOSA Hybrid-MOSA, Hybrid-MOTS Hybrid-MOTS-MOSA - Hybrid-MOSA-MOTS Hybrid-MOSA, Hybrid-MOTS
MID Hybrid-MOTS-MOSA - MOTS-Hybrid-MOSA MOTS-MOSA MOTS-Hybrid-MOSA MOTS-MOSA
DM Hybrid-MOTS-MOSA Hybrid-MOSA, Hybrid-MOTS Hybrid-MOTS-MOSA - Hybrid-MOSA-MOTS Hybrid-MOTS
SNS Hybrid-MOTS-MOSA Hybrid-MOSA Hybrid-MOTS-MOSA - Hybrid-MOSA-MOTS -
Time Hybrid-MOSA-MOTS Hybrid-MOSA, Hybrid-MOTS Hybrid-MOSA-MOTS Hybrid-MOTS Hybrid-MOSA-MOTS Hybrid-MOSA, Hybrid-MOTS
[1]

Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, 2022, 18 (6) : 3807-3830. doi: 10.3934/jimo.2021124

[2]

Hongtruong Pham, Xiwen Lu. The inverse parallel machine scheduling problem with minimum total completion time. Journal of Industrial and Management Optimization, 2014, 10 (2) : 613-620. doi: 10.3934/jimo.2014.10.613

[3]

Ran Ma, Jiping Tao. An improved 2.11-competitive algorithm for online scheduling on parallel machines to minimize total weighted completion time. Journal of Industrial and Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057

[4]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial and Management Optimization, 2014, 10 (1) : 259-273. doi: 10.3934/jimo.2014.10.259

[5]

Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial and Management Optimization, 2022, 18 (1) : 681-691. doi: 10.3934/jimo.2020174

[6]

Ming-Jong Yao, Tien-Cheng Hsu. An efficient search algorithm for obtaining the optimal replenishment strategies in multi-stage just-in-time supply chain systems. Journal of Industrial and Management Optimization, 2009, 5 (1) : 11-32. doi: 10.3934/jimo.2009.5.11

[7]

Zhichao Geng, Jinjiang Yuan. Scheduling family jobs on an unbounded parallel-batch machine to minimize makespan and maximum flow time. Journal of Industrial and Management Optimization, 2018, 14 (4) : 1479-1500. doi: 10.3934/jimo.2018017

[8]

Fan Zhang, Guifa Teng, Mengmeng Gao, Shuai Zhang, Jingjing Zhang. Multi-machine and multi-task emergency allocation algorithm based on precedence rules. Discrete and Continuous Dynamical Systems - S, 2019, 12 (4&5) : 1501-1513. doi: 10.3934/dcdss.2019103

[9]

Ganggang Li, Xiwen Lu, Peihai Liu. The coordination of single-machine scheduling with availability constraints and delivery. Journal of Industrial and Management Optimization, 2016, 12 (2) : 757-770. doi: 10.3934/jimo.2016.12.757

[10]

Ganggang Li, Xiwen Lu. Two-machine scheduling with periodic availability constraints to minimize makespan. Journal of Industrial and Management Optimization, 2015, 11 (2) : 685-700. doi: 10.3934/jimo.2015.11.685

[11]

Bin Zheng, Min Fan, Mengqi Liu, Shang-Chia Liu, Yunqiang Yin. Parallel-machine scheduling with potential disruption and positional-dependent processing times. Journal of Industrial and Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041

[12]

Le Thi Hoai An, Tran Duc Quynh, Kondo Hloindo Adjallah. A difference of convex functions algorithm for optimal scheduling and real-time assignment of preventive maintenance jobs on parallel processors. Journal of Industrial and Management Optimization, 2014, 10 (1) : 243-258. doi: 10.3934/jimo.2014.10.243

[13]

Jiping Tao, Ronghuan Huang, Tundong Liu. A $2.28$-competitive algorithm for online scheduling on identical machines. Journal of Industrial and Management Optimization, 2015, 11 (1) : 185-198. doi: 10.3934/jimo.2015.11.185

[14]

Ping Yan, Ji-Bo Wang, Li-Qiang Zhao. Single-machine bi-criterion scheduling with release times and exponentially time-dependent learning effects. Journal of Industrial and Management Optimization, 2019, 15 (3) : 1117-1131. doi: 10.3934/jimo.2018088

[15]

Xingong Zhang. Single machine and flowshop scheduling problems with sum-of-processing time based learning phenomenon. Journal of Industrial and Management Optimization, 2020, 16 (1) : 231-244. doi: 10.3934/jimo.2018148

[16]

Chengwen Jiao, Qi Feng. Research on the parallel–batch scheduling with linearly lookahead model. Journal of Industrial and Management Optimization, 2021, 17 (6) : 3551-3558. doi: 10.3934/jimo.2020132

[17]

Bin Dan, Huali Gao, Yang Zhang, Ru Liu, Songxuan Ma. Integrated order acceptance and scheduling decision making in product service supply chain with hard time windows constraints. Journal of Industrial and Management Optimization, 2018, 14 (1) : 165-182. doi: 10.3934/jimo.2017041

[18]

P. Liu, Xiwen Lu. Online scheduling of two uniform machines to minimize total completion times. Journal of Industrial and Management Optimization, 2009, 5 (1) : 95-102. doi: 10.3934/jimo.2009.5.95

[19]

Tugba Sarac, Aydin Sipahioglu, Emine Akyol Ozer. A two-stage solution approach for plastic injection machines scheduling problem. Journal of Industrial and Management Optimization, 2021, 17 (3) : 1289-1314. doi: 10.3934/jimo.2020022

[20]

Haoxuan Shen, Shuguang Li, Yanyue Liang. Faster algorithms for bicriteria scheduling of identical jobs on uniform machines. Journal of Industrial and Management Optimization, 2022  doi: 10.3934/jimo.2022178

2021 Impact Factor: 1.411

Metrics

  • PDF downloads (481)
  • HTML views (529)
  • Cited by (0)

[Back to Top]