• Previous Article
    Designing an annual leave scheduling policy: Case of a financial center
  • JIMO Home
  • This Issue
  • Next Article
    Two-level optimization approach with accelerated proximal gradient for objective measures in sparse speech reconstruction
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 & 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. Google Scholar

[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.  Google Scholar

[3]

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

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[8]

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

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

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

[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.   Google Scholar

[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.  Google Scholar

[21]

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

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[26]

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

[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.   Google Scholar

[28]

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

[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.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.   Google Scholar

[35]

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

[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.   Google Scholar

[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.  Google Scholar

[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. Google Scholar

[39]

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

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[49]

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

[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.   Google Scholar

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. Google Scholar

[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.  Google Scholar

[3]

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

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[8]

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

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

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

[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.   Google Scholar

[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.  Google Scholar

[21]

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

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[26]

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

[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.   Google Scholar

[28]

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

[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.  Google Scholar

[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.   Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.   Google Scholar

[35]

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

[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.   Google Scholar

[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.  Google Scholar

[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. Google Scholar

[39]

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

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[49]

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

[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.   Google Scholar

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 & Management Optimization, 2014, 10 (4) : 1071-1090. doi: 10.3934/jimo.2014.10.1071

[2]

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 & Management Optimization, 2017, 13 (1) : 413-428. doi: 10.3934/jimo.2016024

[3]

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 & Management Optimization, 2017, 13 (4) : 2015-2031. doi: 10.3934/jimo.2017029

[4]

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 & Management Optimization, 2021  doi: 10.3934/jimo.2021044

[5]

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

[6]

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 & Management Optimization, 2018, 14 (2) : 497-510. doi: 10.3934/jimo.2017057

[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 & Management Optimization, 2014, 10 (2) : 591-611. doi: 10.3934/jimo.2014.10.591

[8]

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 & Management Optimization, 2017, 13 (2) : 697-711. doi: 10.3934/jimo.2016041

[9]

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 & Management Optimization, 2013, 9 (2) : 323-339. doi: 10.3934/jimo.2013.9.323

[10]

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

[11]

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

[12]

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 & Continuous Dynamical Systems - S, 2020, 13 (6) : 1721-1741. doi: 10.3934/dcdss.2020101

[13]

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

[14]

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

[15]

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

[16]

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

[17]

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 & Management Optimization, 2021, 17 (4) : 2013-2030. doi: 10.3934/jimo.2020056

[18]

Min Ji, Xinna Ye, Fangyao Qian, T.C.E. Cheng, Yiwei Jiang. Parallel-machine scheduling in shared manufacturing. Journal of Industrial & Management Optimization, 2020  doi: 10.3934/jimo.2020174

[19]

Leiyang Wang, Zhaohui Liu. Heuristics for parallel machine scheduling with batch delivery consideration. Journal of Industrial & 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 & Management Optimization, 2021, 17 (6) : 3551-3558. doi: 10.3934/jimo.2020132

2020 Impact Factor: 1.801

Article outline

Figures and Tables

[Back to Top]