doi: 10.3934/jimo.2021124
Online First

Online First articles are published articles within a journal that have not yet been assigned to a formal issue. This means they do not yet have a volume number, issue number, or page numbers assigned to them, however, they can still be found and cited using their DOI (Digital Object Identifier). Online First publication benefits the research community by making new scientific discoveries known as quickly as possible.

Readers can access Online First articles via the “Online First” tab for the selected journal.

Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem

1. 

Department of Industrial Engineering and Future Studies, Faculty of Engineering, University of Isfahan, Iran

2. 

Department of Industrial Engineering, Semnan University, Semnan, Iran

* Corresponding author: Taha Keshavarz

Received  July 2020 Revised  March 2021 Early access July 2021

In this research, a parallel machine sequence-dependent group scheduling problem with the goal of minimizing total weighted earliness and tardiness is investigated. First, a mathematical model is developed for the research problem which can be used for solving small-sized instances. Since the problem is shown to be NP-hard, this research focuses on proposing meta-heuristic algorithms for finding near-optimal solutions. In this regard, the main contribution of this research is to apply the Biogeography-based Optimization (BBO) algorithm as a novel meta-heuristic and Variable Neighborhood Search (VNS) algorithm as a best-known one. In order to evaluate the mathematical model and solution methods, several computational experiments are conducted. The computational experiments demonstrate the efficiency of the proposed meta-heuristic algorithms in terms of speed and solution quality. The maximum gap of BBO algorithm is 1.04% and for VNS algorithm, it is 1.35%.

Citation: Alireza Goli, Taha Keshavarz. Just-in-time scheduling in identical parallel machine sequence-dependent group scheduling problem. Journal of Industrial and Management Optimization, doi: 10.3934/jimo.2021124
References:
[1]

J. Abell and D. A. Du, Framework for multi-objective, biogeography based optimization of complex system families, In, 13th AIAA/ISSMO Multidisciplinary Analysis Optimization Conference, 250 (2010), 9327.

[2]

A. Allahverdi, The third comprehensive survey on scheduling problems with setup times/costs, European J. Oper. Res., 246 (2015), 345-378.  doi: 10.1016/j.ejor.2015.04.004.

[3]

A. Allahverdi and H. Soroush, The significance of reducing setup times/setup costs, European J. Oper. Res., 187 (2008), 978-984. 

[4]

R. Alvarez-ValdésJ. M. Tamarit and F. Villa, Minimizing weighted earliness-tardiness on parallel machines using hybrid metaheuristics, Comput. Oper. Res., 54 (2015), 1-11.  doi: 10.1016/j.cor.2014.08.020.

[5]

S. BáezF. Angel-BelloA. Alvarez and B. Melián-Batista, A hybrid metaheuristic algorithm for a parallel machine scheduling problem with dependent setup times, Computers & Industrial Engineering, 131 (2019), 295-305. 

[6]

K. R. Baker, Scheduling groups of jobs in the two-machine flow shop, Mathematical and Computer Modelling, 13 (1990), 29-36.  doi: 10.1016/0895-7177(90)90368-W.

[7]

S. BathrinathS. SaravanasankarS. MahapatraM. R. Singh and S. Ponnambalam, An improved meta-heuristic approach for solving identical parallel processor scheduling problem, Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 230 (2016), 1114-1126. 

[8]

M. A. Bozorgirad and R. Logendran, Sequence-dependent group scheduling problem on unrelated-parallel machines, Expert Systems with Applications, 39 (2012), 9021-9030. 

[9]

T. Cheng, A heuristic for common due-date assignment and job scheduling on parallel machines, Journal of the Operational Research Society, 40 (1989), 1129-1135. 

[10]

J.-Y. DingS. SongR. ZhangR. Chiong and C. Wu, Parallel machine scheduling under time-of-use electricity prices: New models and optimization approaches, IEEE Transactions on Automation Science and Engineering, 13 (2016), 1138-1154. 

[11]

M. R. GareyR. E. Tarjan and G. T. Wilfong, One-processor scheduling with symmetric earliness and tardiness penalties, Math. Oper. Res., 13 (1988), 330-348.  doi: 10.1287/moor.13.2.330.

[12]

A. H. Goodarzi and S. H. Zegordi, A location-routing problem for cross-docking networks: A biogeography-based optimization algorithm, Computers & Industrial Engineering, 102 (2016), 132-146. 

[13]

R. L. GrahamE. L. LawlerJ. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.

[14]

T. KeshavarzN. Salmasi and M. Varmazyar, Flowshop sequence-dependent group scheduling with minimisation of weighted earliness and tardiness, European Journal of Industrial Engineering, 13 (2019), 54-80. 

[15]

T. KeshavarzM. Savelsbergh and N. Salmasi, A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties, Appl. Math. Model., 39 (2015), 6410-6424.  doi: 10.1016/j.apm.2015.01.069.

[16]

A. KramerM. Iori and P. Lacomme, Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization, European J. Oper. Res., 289 (2021), 825-840.  doi: 10.1016/j.ejor.2019.07.006.

[17]

A. Kramer and A. Subramanian, A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems, J. Sched., 22 (2019), 21-57.  doi: 10.1007/s10951-017-0549-6.

[18]

C. Y. Lee and M. Pinedo, Optimization and Heuristics of Scheduling, In Handbook of Applied Optimization, 2002.

[19]

L.-L. LiY.-F. YangC.-H. Wang and K.-P. Lin, Biogeography-based optimization based on population competition strategy for solving the substation location problem, Expert Systems with Applications, 97 (2018), 290-302. 

[20]

X.-X. LiangM. LiuY.-B. FengJ.-B. Wang and L.-S. Wen, Solution algorithms for single-machine resource allocation scheduling with deteriorating jobs and group technology, Eng. Optim., 52 (2020), 1184-1197.  doi: 10.1080/0305215X.2019.1638920.

[21]

J. Lin, A hybrid biogeography-based optimization for the fuzzy flexible job-shop scheduling problem, Knowledge-Based Systems, 78 (2015), 59-74. 

[22]

S. -W. Lin, K. -C. Ying, Y. -I. Chiang and W. -J. Wu, Minimising total weighted earliness and tardiness penalties on identical parallel machines using a fast ruin-and-recreate algorithm, International Journal of Production Research, (2016), 1–12.

[23]

Z. LiuW. Yu and T. C. E. Cheng, Scheduling groups of unit length jobs on two identical parallel machines, Inform. Process. Lett., 69 (1999), 275-281.  doi: 10.1016/S0020-0190(99)00026-5.

[24]

R. LogendranB. McDonell and B. Smucker, Scheduling unrelated parallel machines with sequence-dependent setups, Comput. Oper. Res., 34 (2007), 3420-3438.  doi: 10.1016/j.cor.2006.02.006.

[25]

C. Low and G.-H. Wu, Unrelated parallel-machine scheduling with controllable processing times and eligibility constraints to minimize the makespan, Journal of Industrial and Production Engineering, 33 (2016), 286-293. 

[26]

H. Ma, An analysis of the equilibrium of migration models for biogeography-based optimization, Information Sciences, 180 (2010), 3444-3464. 

[27]

S. MirM. Saber and J. Rezaeian, Two meta-heuristic algorithms for parallel machines scheduling problem with past-sequence-dependent setup times and effects of deterioration and learning, International Journal of Industrial Engineering & Production Research, 27 (2016), 69-88. 

[28]

N. Mladenović and P. Hansen, Variable neighborhood search, Comput. Oper. Res., 24 (1997), 1097-1100. doi: 10.1016/S0305-0548(97)00031-2.

[29]

S. Radhakrishnan and J. A. Ventura, Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times, International Journal of Production Research, 38 (2000), 2233-2252.  doi: 10.1080/00207540050028070.

[30]

S. H. A. Rahmati and M. Zandieh, A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem, The International Journal of Advanced Manufacturing Technology, 58 (2012), 1115-1129. 

[31]

K. RajaC. Arumugam and V. Selladurai, Non-identical parallel-machine scheduling using genetic algorithm and fuzzy logic approach, International Journal of Services and Operations Management, 4 (2008), 72-101. 

[32]

M. G. RavettiG. R. MateusP. L. Rocha and P. M. Pardalos, A scheduling problem with unrelated parallel machines and sequence dependent setups, Int. J. Oper. Res., 2 (2007), 380-399.  doi: 10.1504/IJOR.2007.014169.

[33]

J. E. Schaller, Minimizing total tardiness for scheduling identical parallel machines with family setups, Computers & Industrial Engineering, Springer Berlin Heidelberg, 72 (2014), 274–281.

[34]

K. SenthilkumarV. SelladuraiK. Raja and V. Thirunavukkarasu, A robust fuzzy optimization model for carbon-efficient closed-loop supply chain network design problem: a numerical illustration in electronics industry, A Hybrid Algorithm based on PSO and ACO Approach for Solving Combinatorial Fuzzy Unrelated Parallel Machine Scheduling Problem, 64 (2011), 293-313. 

[35]

D. Simon, Biogeography-based optimization, IEEE transactions on Evolutionary Computation, 12 (2008), 702-713. 

[36]

D. SimonR. RarickM. Ergezer and D. Du, Analytical and numerical comparisons of biogeography-based optimization and genetic algorithms, Information Sciences, 181 (2011), 1224-1248. 

[37]

F. Sivrikaya-Şerifoǧlu and G. Ulusoy, Parallel machine scheduling with earliness and tardiness penalties, Comput. Oper. Res., 26 (1999), 773-787.  doi: 10.1016/S0305-0548(98)00090-2.

[38]

K. Somasundaram, M. Saravanan and B. Vikneshkannan, MOGWO metaheuristic method used to solve by identical parallel machine scheduling problem with different objectives compared with GA and VNS, 2018.

[39]

W. Szwarc and S. K. Mukhopadhyay, Optimal timing schedules in earliness-tardiness single machine sequencing, Naval Research Logistics (NRL), 42 (1995), 1109-1114. 

[40]

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.

[41]

E. Vallada and R. Ruiz, Scheduling unrelated parallel machines with sequence dependent setup times and weighted earliness-tardiness minimization, Just-in-Time Systems, 60 (2012), 67-90.  doi: 10.1007/978-1-4614-1123-9_4.

[42]

R. Vickson and B. Alfredsson, Two-and three-machine flow shop scheduling problems with equal sized transfer batches, The International Journal of Production Research, 30 (1992), 1551-1574. 

[43]

G.-G. WangA. H. Gandomi and A. H. Alavi, An effective krill herd algorithm with migration operator in biogeography-based optimization, Appl. Math. Model., 38 (2014), 2454-2462.  doi: 10.1016/j.apm.2013.10.052.

[44]

G. WangL. GuoH. DuanH. WangL. Liu and M. Shao, Hybridizing harmony search with biogeography based optimization for global numerical optimization, Journal of Computational and Theoretical Nanoscience, 10 (2013), 2312-2322. 

[45]

J.-B. Wang and X.-X. Liang, Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint, Eng. Optim., 51 (2019), 231-246.  doi: 10.1080/0305215X.2018.1454442.

[46]

J.-B. WangL. LiuJ.-J. Wang and L. Li, Makespan minimization scheduling with ready times, group technology and shortening job processing times, Comput. J., 61 (2018), 1422-1428.  doi: 10.1093/comjnl/bxy007.

[47]

J.-B. Wang and J.-J. Wang, Single machine group scheduling with time dependent processing times and ready times, Inform. Sci., 275 (2014), 226-231.  doi: 10.1016/j.ins.2014.02.034.

[48]

D.-L. Yang and M.-S. Chern, Two-machine flowshop group scheduling problem, Comput. Oper. Res., 27 (2000), 975-985.  doi: 10.1016/S0305-0548(99)00070-2.

[49]

C. A. Yano and Y. -D. Kim, Algorithms for a class of single-machine weighted tardiness and earliness problems, 1991.

[50]

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

show all references

References:
[1]

J. Abell and D. A. Du, Framework for multi-objective, biogeography based optimization of complex system families, In, 13th AIAA/ISSMO Multidisciplinary Analysis Optimization Conference, 250 (2010), 9327.

[2]

A. Allahverdi, The third comprehensive survey on scheduling problems with setup times/costs, European J. Oper. Res., 246 (2015), 345-378.  doi: 10.1016/j.ejor.2015.04.004.

[3]

A. Allahverdi and H. Soroush, The significance of reducing setup times/setup costs, European J. Oper. Res., 187 (2008), 978-984. 

[4]

R. Alvarez-ValdésJ. M. Tamarit and F. Villa, Minimizing weighted earliness-tardiness on parallel machines using hybrid metaheuristics, Comput. Oper. Res., 54 (2015), 1-11.  doi: 10.1016/j.cor.2014.08.020.

[5]

S. BáezF. Angel-BelloA. Alvarez and B. Melián-Batista, A hybrid metaheuristic algorithm for a parallel machine scheduling problem with dependent setup times, Computers & Industrial Engineering, 131 (2019), 295-305. 

[6]

K. R. Baker, Scheduling groups of jobs in the two-machine flow shop, Mathematical and Computer Modelling, 13 (1990), 29-36.  doi: 10.1016/0895-7177(90)90368-W.

[7]

S. BathrinathS. SaravanasankarS. MahapatraM. R. Singh and S. Ponnambalam, An improved meta-heuristic approach for solving identical parallel processor scheduling problem, Proceedings of the Institution of Mechanical Engineers, Part B: Journal of Engineering Manufacture, 230 (2016), 1114-1126. 

[8]

M. A. Bozorgirad and R. Logendran, Sequence-dependent group scheduling problem on unrelated-parallel machines, Expert Systems with Applications, 39 (2012), 9021-9030. 

[9]

T. Cheng, A heuristic for common due-date assignment and job scheduling on parallel machines, Journal of the Operational Research Society, 40 (1989), 1129-1135. 

[10]

J.-Y. DingS. SongR. ZhangR. Chiong and C. Wu, Parallel machine scheduling under time-of-use electricity prices: New models and optimization approaches, IEEE Transactions on Automation Science and Engineering, 13 (2016), 1138-1154. 

[11]

M. R. GareyR. E. Tarjan and G. T. Wilfong, One-processor scheduling with symmetric earliness and tardiness penalties, Math. Oper. Res., 13 (1988), 330-348.  doi: 10.1287/moor.13.2.330.

[12]

A. H. Goodarzi and S. H. Zegordi, A location-routing problem for cross-docking networks: A biogeography-based optimization algorithm, Computers & Industrial Engineering, 102 (2016), 132-146. 

[13]

R. L. GrahamE. L. LawlerJ. K. Lenstra and A. H. G. Rinnooy Kan, Optimization and approximation in deterministic sequencing and scheduling: A survey, Annals of Discrete Mathematics, 5 (1979), 287-326.  doi: 10.1016/S0167-5060(08)70356-X.

[14]

T. KeshavarzN. Salmasi and M. Varmazyar, Flowshop sequence-dependent group scheduling with minimisation of weighted earliness and tardiness, European Journal of Industrial Engineering, 13 (2019), 54-80. 

[15]

T. KeshavarzM. Savelsbergh and N. Salmasi, A branch-and-bound algorithm for the single machine sequence-dependent group scheduling problem with earliness and tardiness penalties, Appl. Math. Model., 39 (2015), 6410-6424.  doi: 10.1016/j.apm.2015.01.069.

[16]

A. KramerM. Iori and P. Lacomme, Mathematical formulations for scheduling jobs on identical parallel machines with family setup times and total weighted completion time minimization, European J. Oper. Res., 289 (2021), 825-840.  doi: 10.1016/j.ejor.2019.07.006.

[17]

A. Kramer and A. Subramanian, A unified heuristic and an annotated bibliography for a large class of earliness-tardiness scheduling problems, J. Sched., 22 (2019), 21-57.  doi: 10.1007/s10951-017-0549-6.

[18]

C. Y. Lee and M. Pinedo, Optimization and Heuristics of Scheduling, In Handbook of Applied Optimization, 2002.

[19]

L.-L. LiY.-F. YangC.-H. Wang and K.-P. Lin, Biogeography-based optimization based on population competition strategy for solving the substation location problem, Expert Systems with Applications, 97 (2018), 290-302. 

[20]

X.-X. LiangM. LiuY.-B. FengJ.-B. Wang and L.-S. Wen, Solution algorithms for single-machine resource allocation scheduling with deteriorating jobs and group technology, Eng. Optim., 52 (2020), 1184-1197.  doi: 10.1080/0305215X.2019.1638920.

[21]

J. Lin, A hybrid biogeography-based optimization for the fuzzy flexible job-shop scheduling problem, Knowledge-Based Systems, 78 (2015), 59-74. 

[22]

S. -W. Lin, K. -C. Ying, Y. -I. Chiang and W. -J. Wu, Minimising total weighted earliness and tardiness penalties on identical parallel machines using a fast ruin-and-recreate algorithm, International Journal of Production Research, (2016), 1–12.

[23]

Z. LiuW. Yu and T. C. E. Cheng, Scheduling groups of unit length jobs on two identical parallel machines, Inform. Process. Lett., 69 (1999), 275-281.  doi: 10.1016/S0020-0190(99)00026-5.

[24]

R. LogendranB. McDonell and B. Smucker, Scheduling unrelated parallel machines with sequence-dependent setups, Comput. Oper. Res., 34 (2007), 3420-3438.  doi: 10.1016/j.cor.2006.02.006.

[25]

C. Low and G.-H. Wu, Unrelated parallel-machine scheduling with controllable processing times and eligibility constraints to minimize the makespan, Journal of Industrial and Production Engineering, 33 (2016), 286-293. 

[26]

H. Ma, An analysis of the equilibrium of migration models for biogeography-based optimization, Information Sciences, 180 (2010), 3444-3464. 

[27]

S. MirM. Saber and J. Rezaeian, Two meta-heuristic algorithms for parallel machines scheduling problem with past-sequence-dependent setup times and effects of deterioration and learning, International Journal of Industrial Engineering & Production Research, 27 (2016), 69-88. 

[28]

N. Mladenović and P. Hansen, Variable neighborhood search, Comput. Oper. Res., 24 (1997), 1097-1100. doi: 10.1016/S0305-0548(97)00031-2.

[29]

S. Radhakrishnan and J. A. Ventura, Simulated annealing for parallel machine scheduling with earliness-tardiness penalties and sequence-dependent set-up times, International Journal of Production Research, 38 (2000), 2233-2252.  doi: 10.1080/00207540050028070.

[30]

S. H. A. Rahmati and M. Zandieh, A new biogeography-based optimization (BBO) algorithm for the flexible job shop scheduling problem, The International Journal of Advanced Manufacturing Technology, 58 (2012), 1115-1129. 

[31]

K. RajaC. Arumugam and V. Selladurai, Non-identical parallel-machine scheduling using genetic algorithm and fuzzy logic approach, International Journal of Services and Operations Management, 4 (2008), 72-101. 

[32]

M. G. RavettiG. R. MateusP. L. Rocha and P. M. Pardalos, A scheduling problem with unrelated parallel machines and sequence dependent setups, Int. J. Oper. Res., 2 (2007), 380-399.  doi: 10.1504/IJOR.2007.014169.

[33]

J. E. Schaller, Minimizing total tardiness for scheduling identical parallel machines with family setups, Computers & Industrial Engineering, Springer Berlin Heidelberg, 72 (2014), 274–281.

[34]

K. SenthilkumarV. SelladuraiK. Raja and V. Thirunavukkarasu, A robust fuzzy optimization model for carbon-efficient closed-loop supply chain network design problem: a numerical illustration in electronics industry, A Hybrid Algorithm based on PSO and ACO Approach for Solving Combinatorial Fuzzy Unrelated Parallel Machine Scheduling Problem, 64 (2011), 293-313. 

[35]

D. Simon, Biogeography-based optimization, IEEE transactions on Evolutionary Computation, 12 (2008), 702-713. 

[36]

D. SimonR. RarickM. Ergezer and D. Du, Analytical and numerical comparisons of biogeography-based optimization and genetic algorithms, Information Sciences, 181 (2011), 1224-1248. 

[37]

F. Sivrikaya-Şerifoǧlu and G. Ulusoy, Parallel machine scheduling with earliness and tardiness penalties, Comput. Oper. Res., 26 (1999), 773-787.  doi: 10.1016/S0305-0548(98)00090-2.

[38]

K. Somasundaram, M. Saravanan and B. Vikneshkannan, MOGWO metaheuristic method used to solve by identical parallel machine scheduling problem with different objectives compared with GA and VNS, 2018.

[39]

W. Szwarc and S. K. Mukhopadhyay, Optimal timing schedules in earliness-tardiness single machine sequencing, Naval Research Logistics (NRL), 42 (1995), 1109-1114. 

[40]

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.

[41]

E. Vallada and R. Ruiz, Scheduling unrelated parallel machines with sequence dependent setup times and weighted earliness-tardiness minimization, Just-in-Time Systems, 60 (2012), 67-90.  doi: 10.1007/978-1-4614-1123-9_4.

[42]

R. Vickson and B. Alfredsson, Two-and three-machine flow shop scheduling problems with equal sized transfer batches, The International Journal of Production Research, 30 (1992), 1551-1574. 

[43]

G.-G. WangA. H. Gandomi and A. H. Alavi, An effective krill herd algorithm with migration operator in biogeography-based optimization, Appl. Math. Model., 38 (2014), 2454-2462.  doi: 10.1016/j.apm.2013.10.052.

[44]

G. WangL. GuoH. DuanH. WangL. Liu and M. Shao, Hybridizing harmony search with biogeography based optimization for global numerical optimization, Journal of Computational and Theoretical Nanoscience, 10 (2013), 2312-2322. 

[45]

J.-B. Wang and X.-X. Liang, Group scheduling with deteriorating jobs and allotted resource under limited resource availability constraint, Eng. Optim., 51 (2019), 231-246.  doi: 10.1080/0305215X.2018.1454442.

[46]

J.-B. WangL. LiuJ.-J. Wang and L. Li, Makespan minimization scheduling with ready times, group technology and shortening job processing times, Comput. J., 61 (2018), 1422-1428.  doi: 10.1093/comjnl/bxy007.

[47]

J.-B. Wang and J.-J. Wang, Single machine group scheduling with time dependent processing times and ready times, Inform. Sci., 275 (2014), 226-231.  doi: 10.1016/j.ins.2014.02.034.

[48]

D.-L. Yang and M.-S. Chern, Two-machine flowshop group scheduling problem, Comput. Oper. Res., 27 (2000), 975-985.  doi: 10.1016/S0305-0548(99)00070-2.

[49]

C. A. Yano and Y. -D. Kim, Algorithms for a class of single-machine weighted tardiness and earliness problems, 1991.

[50]

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

Figure 1.  An example of the studied problem
Figure 2.  An example of solution representation and its scheduling plan
Figure 3.  An example of a feasible solution
Figure 4.  An example of LS1
Figure 5.  An example of LS2
Figure 6.  An example of migration operator
Figure 7.  An example of mutation operator
Figure 8.  Comparison of the CPU time of VNS and BBO with GAMS
Figure 9.  The standard deviation of the results of the proposed algorithms in large-sized instances
Figure 10.  Average CPU time of proposed algorithms in large-sized instances
Table 1.  Input values of the BBO algorithm
Parameter Level
1 2 3
$ m_{max} $ 0.1 0.2 0.3
$ \lambda $ 0.4 0.5 0.6
$ \mu $ 0.5 0.6 0.7
Number of habitats 400 450 500
Numner of iterations 300 400 500
Parameter Level
1 2 3
$ m_{max} $ 0.1 0.2 0.3
$ \lambda $ 0.4 0.5 0.6
$ \mu $ 0.5 0.6 0.7
Number of habitats 400 450 500
Numner of iterations 300 400 500
Table 2.  Optimal values of the BBO algorithm parameters
Parameter Value
$ m_{max} $ 0.2
$ \lambda $ 0.4
$ \mu $ 0.6
Number of habitats 500
Numner of iterations 500
Parameter Value
$ m_{max} $ 0.2
$ \lambda $ 0.4
$ \mu $ 0.6
Number of habitats 500
Numner of iterations 500
Table 3.  Specification of generated problem instances in single machine mode
CLASS $ \#G $ $ \#J $
1 10 2
2 10 3
3 15 2
4 15 3
5 20 2
6 20 3
7 25 2
8 25 3
CLASS $ \#G $ $ \#J $
1 10 2
2 10 3
3 15 2
4 15 3
5 20 2
6 20 3
7 25 2
8 25 3
Table 4.  The results of each class of problems in single machine mode
Class B & B time[15] BBO time BBO GAP VNS time VNS GAP
M S M S M S NG M S M S NG
G1 0.178 0.277 6.411 1.718 0.900 0.836 226 4.622 4.091 1.376 1.354 153
G2 0.180 0.209 4.560 0.927 0.721 0.815 293 4.800 1.801 0.981 1.013 211
G3 5.204 11.510 3.625 1.414 0.662 0.696 328 2.872 1.894 0.661 1.139 317
G4 3.920 6.617 4.080 0.717 0.711 0.813 304 3.721 1.248 1.031 1.021 184
G5 209.360 685.260 6.770 1.954 0.861 1.043 249 6.281 2.782 0.751 0.783 270
G6 40.810 104.362 9.140 1.946 0.761 0.855 266 7.940 2.715 1.121 1.176 175
G7 812.350 2060.100 11.090 2.192 0.872 0.993 235 9.340 3.008 1.062 1.013 189
G8 848.190 3497.207 11.301 1.727 0.998 1.035 199 12.370 1.834 1.321 1.345 144
Class B & B time[15] BBO time BBO GAP VNS time VNS GAP
M S M S M S NG M S M S NG
G1 0.178 0.277 6.411 1.718 0.900 0.836 226 4.622 4.091 1.376 1.354 153
G2 0.180 0.209 4.560 0.927 0.721 0.815 293 4.800 1.801 0.981 1.013 211
G3 5.204 11.510 3.625 1.414 0.662 0.696 328 2.872 1.894 0.661 1.139 317
G4 3.920 6.617 4.080 0.717 0.711 0.813 304 3.721 1.248 1.031 1.021 184
G5 209.360 685.260 6.770 1.954 0.861 1.043 249 6.281 2.782 0.751 0.783 270
G6 40.810 104.362 9.140 1.946 0.761 0.855 266 7.940 2.715 1.121 1.176 175
G7 812.350 2060.100 11.090 2.192 0.872 0.993 235 9.340 3.008 1.062 1.013 189
G8 848.190 3497.207 11.301 1.727 0.998 1.035 199 12.370 1.834 1.321 1.345 144
Table 5.  Problem instances of the multi machines cases
$ \# $problem $ \#J $ $ \#G $ $ \#M $ $ \tau $ $ \rho $
P1 15 3 2 0.4 0.6
P2 15 4 2 0.5 0.5
P3 20 4 2 0.4 0.6
P4 20 5 3 0.5 0.5
P5 25 5 3 0.4 0.6
P6 25 6 3 0.5 0.5
P7 30 6 4 0.4 0.6
P8 30 7 4 0.5 0.5
P9 40 7 4 0.4 0.6
P10 50 8 4 0.5 0.5
$ \# $problem $ \#J $ $ \#G $ $ \#M $ $ \tau $ $ \rho $
P1 15 3 2 0.4 0.6
P2 15 4 2 0.5 0.5
P3 20 4 2 0.4 0.6
P4 20 5 3 0.5 0.5
P5 25 5 3 0.4 0.6
P6 25 6 3 0.5 0.5
P7 30 6 4 0.4 0.6
P8 30 7 4 0.5 0.5
P9 40 7 4 0.4 0.6
P10 50 8 4 0.5 0.5
Table 6.  The results of each class of problems in single machine mode
GAMS BBO VNS
$ Z $ $ T $ $ Z $ $ T $ $ GAP $ $ Z $ $ T $ $ GAP $
P1 51268 1.8 51268 6.3 0 51268 4.2 0
P2 50613 8.3 50667 6.9 0.106 50726 9.6 0.223
P3 63790 51.2 63894 8.3 0.163 63993 11.8 0.318
P4 62784 96.4 62903 10.4 0.189 62923 12.6 0.221
P5 86771 234.5 86835 12.9 0.073 86801 15.1 0.034
P6 83735 1003.5 83799 17.9 0.076 83831 19.8 0.114
P7 93481 2836.1 93556 26.4 0.080 93599 21.2 0.126
P8 92433$ ^* $ 3600.0 92573 29.6 0.151 92591 26.4 0.170
P9 98286$ ^* $ 3600.0 98330 41.2 0.044 98495 31.3 0.212
P10 Not Solved - 109647 59.4 - 109704 41.5 -
AVERAGE 75906.78 1270.21 79347.20 21.93 0.098 79393.1 19.35 0.157
$ ^* $ Not Optimal
GAMS BBO VNS
$ Z $ $ T $ $ Z $ $ T $ $ GAP $ $ Z $ $ T $ $ GAP $
P1 51268 1.8 51268 6.3 0 51268 4.2 0
P2 50613 8.3 50667 6.9 0.106 50726 9.6 0.223
P3 63790 51.2 63894 8.3 0.163 63993 11.8 0.318
P4 62784 96.4 62903 10.4 0.189 62923 12.6 0.221
P5 86771 234.5 86835 12.9 0.073 86801 15.1 0.034
P6 83735 1003.5 83799 17.9 0.076 83831 19.8 0.114
P7 93481 2836.1 93556 26.4 0.080 93599 21.2 0.126
P8 92433$ ^* $ 3600.0 92573 29.6 0.151 92591 26.4 0.170
P9 98286$ ^* $ 3600.0 98330 41.2 0.044 98495 31.3 0.212
P10 Not Solved - 109647 59.4 - 109704 41.5 -
AVERAGE 75906.78 1270.21 79347.20 21.93 0.098 79393.1 19.35 0.157
$ ^* $ Not Optimal
Table 7.  Characteristics of large sized instances
$ \# $CLASS $ \#J $ $ \#G $ $ \#M $
C1 60 8 5
C2 70 9 5
C3 80 10 10
C4 90 11 10
C5 100 12 15
C6 120 13 15
C7 140 14 20
C8 160 15 20
C9 180 16 30
C10 200 17 30
$ \# $CLASS $ \#J $ $ \#G $ $ \#M $
C1 60 8 5
C2 70 9 5
C3 80 10 10
C4 90 11 10
C5 100 12 15
C6 120 13 15
C7 140 14 20
C8 160 15 20
C9 180 16 30
C10 200 17 30
Table 8.  The results of large sized instances
Class BBO VNS Heuristic 1
$ Z $ $ T $ $ Z $ $ T $ $ Z $ $ T $
M S M S M S M S M M
C1 115416.1 2991.7 61.9 3.0 118173.6 3253.8 58.8 15.9 175099.1 0.51
C2 116347.5 9161.1 65.8 7.4 127467.8 12101.2 60.4 15.1 205043.1 0.53
C3 117114.5 10696.7 70.0 12.2 128149.5 11642.2 61.0 8.2 220951.7 0.59
C4 120344.9 12083.6 72.5 2.2 133754.1 13688.1 63.6 0.6 199085.9 0.64
C5 122183.1 12017.9 78.8 6.9 143719.8 15595.5 67.3 2.5 205340.6 0.71
C6 126887.2 14540.4 79.1 13.2 144539.7 15354.9 68.5 4.3 231762.8 0.78
C7 138645.8 15007.8 81.5 5.2 156041.1 16616.2 71.5 21.4 230155.7 0.83
C8 146345.9 15578.7 87.7 14.6 158638.1 17468.5 74.2 8.4 241440.2 0.92
C9 150911.0 16049.9 95.8 17.5 169091.7 20566.0 78.5 1.7 238611.6 1.07
C10 152013.7 18975.0 101.3 7.5 177151.7 22362.4 79.2 7.0 267502.5 1.15
Ave 130621.0 12710.3 79.4 9.0 145672.7 14864.9 68.3 8.5 221499.3 0.77
Class BBO VNS Heuristic 1
$ Z $ $ T $ $ Z $ $ T $ $ Z $ $ T $
M S M S M S M S M M
C1 115416.1 2991.7 61.9 3.0 118173.6 3253.8 58.8 15.9 175099.1 0.51
C2 116347.5 9161.1 65.8 7.4 127467.8 12101.2 60.4 15.1 205043.1 0.53
C3 117114.5 10696.7 70.0 12.2 128149.5 11642.2 61.0 8.2 220951.7 0.59
C4 120344.9 12083.6 72.5 2.2 133754.1 13688.1 63.6 0.6 199085.9 0.64
C5 122183.1 12017.9 78.8 6.9 143719.8 15595.5 67.3 2.5 205340.6 0.71
C6 126887.2 14540.4 79.1 13.2 144539.7 15354.9 68.5 4.3 231762.8 0.78
C7 138645.8 15007.8 81.5 5.2 156041.1 16616.2 71.5 21.4 230155.7 0.83
C8 146345.9 15578.7 87.7 14.6 158638.1 17468.5 74.2 8.4 241440.2 0.92
C9 150911.0 16049.9 95.8 17.5 169091.7 20566.0 78.5 1.7 238611.6 1.07
C10 152013.7 18975.0 101.3 7.5 177151.7 22362.4 79.2 7.0 267502.5 1.15
Ave 130621.0 12710.3 79.4 9.0 145672.7 14864.9 68.3 8.5 221499.3 0.77
Table 9.  The improvement rate of VNS and BBO
Class BBO VNS
C1 34.09 32.51
C2 43.26 37.83
C3 47.01 42.00
C4 39.55 32.82
C5 40.5 30.01
C6 45.25 37.63
C7 39.76 32.2
C8 39.39 34.3
C9 36.75 29.14
C10 43.17 33.78
Average 40.87 34.22
Class BBO VNS
C1 34.09 32.51
C2 43.26 37.83
C3 47.01 42.00
C4 39.55 32.82
C5 40.5 30.01
C6 45.25 37.63
C7 39.76 32.2
C8 39.39 34.3
C9 36.75 29.14
C10 43.17 33.78
Average 40.87 34.22
Table 10.  HSD value of BBO algorithm
BBO results Subset for alpha = 0.05
1 2 3 4
C1 116982.2882
C2 119882.7701 119882.7701
Tukey HSD C3 120721.4447 120721.4447
C4 122278.5560 122278.5560
c5 126051.3100 126051.3100
C6 129921.2360
C7 144581.7216
C8 150809.0004 150809.0004
C9 155897.8618 155897.8618
C10 157336.4760
Sig 0.284 0.180 0.092 0.691
BBO results Subset for alpha = 0.05
1 2 3 4
C1 116982.2882
C2 119882.7701 119882.7701
Tukey HSD C3 120721.4447 120721.4447
C4 122278.5560 122278.5560
c5 126051.3100 126051.3100
C6 129921.2360
C7 144581.7216
C8 150809.0004 150809.0004
C9 155897.8618 155897.8618
C10 157336.4760
Sig 0.284 0.180 0.092 0.691
Table 11.  HSD value of VNS algorithm
VNS results Subset for alpha = 0.05
1 2 3 4
C1 122540.1582
C2 129272.8453
C3 130296.0748
C4 136931.6283 136931.6283
c5 149413.9052 149413.9052
Tukey HSD C6 149470.4904 149470.4904
C7 162710.7451 162710.7451
C8 166810.9620
C9 173810.6045 173810.6045
C10 182901.9209
Sig 0.284 0.180 0.092 0.691
VNS results Subset for alpha = 0.05
1 2 3 4
C1 122540.1582
C2 129272.8453
C3 130296.0748
C4 136931.6283 136931.6283
c5 149413.9052 149413.9052
Tukey HSD C6 149470.4904 149470.4904
C7 162710.7451 162710.7451
C8 166810.9620
C9 173810.6045 173810.6045
C10 182901.9209
Sig 0.284 0.180 0.092 0.691
[1]

Peng Guo, Wenming Cheng, Yi Wang. A general variable neighborhood search for single-machine total tardiness scheduling problem with step-deteriorating jobs. Journal of Industrial and Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[2]

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, 2021  doi: 10.3934/jimo.2021190

[3]

Lalida Deeratanasrikul, Shinji Mizuno. Multiple-stage multiple-machine capacitated lot-sizing and scheduling with sequence-dependent setup: A case study in the wheel industry. Journal of Industrial and Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024

[4]

Adel Dabah, Ahcene Bendjoudi, Abdelhakim AitZai. An efficient Tabu Search neighborhood based on reconstruction strategy to solve the blocking job shop scheduling problem. Journal of Industrial and Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029

[5]

Mehmet Duran Toksari, Emel Kizilkaya Aydogan, Berrin Atalay, Saziye Sari. Some scheduling problems with sum of logarithm processing times based learning effect and exponential past sequence dependent delivery times. Journal of Industrial and Management Optimization, 2022, 18 (3) : 1795-1807. doi: 10.3934/jimo.2021044

[6]

Y. K. Lin, C. S. Chong. A tabu search algorithm to minimize total weighted tardiness for the job shop scheduling problem. Journal of Industrial and Management Optimization, 2016, 12 (2) : 703-717. doi: 10.3934/jimo.2016.12.703

[7]

Wen-Hung Wu, Yunqiang Yin, Wen-Hsiang Wu, Chin-Chia Wu, Peng-Hsiang Hsu. A time-dependent scheduling problem to minimize the sum of the total weighted tardiness among two agents. Journal of Industrial and Management Optimization, 2014, 10 (2) : 591-611. doi: 10.3934/jimo.2014.10.591

[8]

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

[9]

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

[10]

Yunqiang Yin, T. C. E. Cheng, Jianyou Xu, Shuenn-Ren Cheng, Chin-Chia Wu. Single-machine scheduling with past-sequence-dependent delivery times and a linear deterioration. Journal of Industrial and Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323

[11]

Xiaoxiao Yuan, Jing Liu, Xingxing Hao. A moving block sequence-based evolutionary algorithm for resource investment project scheduling problems. Big Data & Information Analytics, 2017, 2 (1) : 39-58. doi: 10.3934/bdia.2017007

[12]

Fengqiu Liu, Xiaoping Xue. Subgradient-based neural network for nonconvex optimization problems in support vector machines with indefinite kernels. Journal of Industrial and Management Optimization, 2016, 12 (1) : 285-301. doi: 10.3934/jimo.2016.12.285

[13]

Yi An, Zhuohan Li, Changzhi Wu, Huosheng Hu, Cheng Shao, Bo Li. Earth pressure field modeling for tunnel face stability evaluation of EPB shield machines based on optimization solution. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1721-1741. doi: 10.3934/dcdss.2020101

[14]

Güvenç Şahin, Ravindra K. Ahuja. Single-machine scheduling with stepwise tardiness costs and release times. Journal of Industrial and Management Optimization, 2011, 7 (4) : 825-848. doi: 10.3934/jimo.2011.7.825

[15]

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

[16]

Zhong Wan, Chaoming Hu, Zhanlu Yang. A spectral PRP conjugate gradient methods for nonconvex optimization problem based on modified line search. Discrete and Continuous Dynamical Systems - B, 2011, 16 (4) : 1157-1169. doi: 10.3934/dcdsb.2011.16.1157

[17]

Mingyong Lai, Xiaojiao Tong. A metaheuristic method for vehicle routing problem based on improved ant colony optimization and Tabu search. Journal of Industrial and Management Optimization, 2012, 8 (2) : 469-484. doi: 10.3934/jimo.2012.8.469

[18]

Yishui Wang, Dongmei Zhang, Peng Zhang, Yong Zhang. Local search algorithm for the squared metric $ k $-facility location problem with linear penalties. Journal of Industrial and Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056

[19]

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

[20]

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

2020 Impact Factor: 1.801

Metrics

  • PDF downloads (568)
  • HTML views (395)
  • Cited by (0)

Other articles
by authors

[Back to Top]