Skip to main content

Advertisement

SpringerLink
Log in

MIP models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints

  • Original Paper
  • Published:
TOP Aims and scope Submit manuscript

Abstract

If parallel machines use shared resources during production, jobs on machines must wait until the required resources are available. If the shared resource is single, only one job can use it at a time, but if there are multiple copies of this resource, multiple jobs can be scheduled up to the number of copies at a time. For this reason, it is crucial to consider resource usage when scheduling this type of machine. In recent years, various studies have been carried out to address identical parallel machine scheduling problems. However, although shared resources in parallel machines are an important aspect of this problem, resources are rarely considered in these studies and, in fact, have not been studied for this particular aspect. In this study, an identical parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and multiple copies of shared resources (IPMS-SMS) is considered. Mixed-integer programming (MIP) models and a model-based genetic algorithm (matheuristic) are proposed, and the objective function of the problem seeks to minimize the total weighted completion time. Randomly generated instances are solved using the proposed models and the matheuristic. Optimal schedules are obtained for almost all small problems using a mixed-integer programming model. However, better solutions are obtained for medium and large instances using the proposed matheuristic.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9

Similar content being viewed by others

References

  • Afzalirad, Rezaeian, & (2016) Resource-constrained unrelated parallel machine scheduling problem with sequence dependent setup times, precedence constraints and machine eligibility restrictions. Comput Ind Eng 98:40–52

    Article  Google Scholar 

  • Alagoz O, Azizoglu M (2003) Rescheduling of identical parallel machines under machine eligibility constraints. Eur J Oper Res 149(3):523–532

    Article  Google Scholar 

  • Arnaout JP (2010) Heuristics for the maximization of operating rooms utilization using simulation. Simulation 86(8–9):573–583

    Article  Google Scholar 

  • Avalos-Rosales O, Angel-Bello F, Alvarez A (2015) Efficient metaheuristic algorithm and re-formulations for the unrelated parallel machine scheduling problem with sequence and machine-dependent setup times. Int J Adv Manuf Technol 76:1705–1718

    Article  Google Scholar 

  • Billaut JC, Croce Federico D, Grosso A (2015) A single machine scheduling problem with two-dimensional vector packing constraints. Eur J Oper Res 243:399–411

    Article  Google Scholar 

  • Chan TS, Choy KL, Bibhushan (2011) A genetic algorithm-based scheduler for multiproduct parallel machine sheet metal job shop. Expert Syst Appl 38(7):8703–8715

    Article  Google Scholar 

  • Chaudhry IA, Drake PR (2009) Minimizing total tardiness for the machine scheduling and worker assignment problems in identical parallel machines using genetic algorithms. Int J Adv Manuf Technol 42(5–6):581–594

    Article  Google Scholar 

  • Chen CL, Chen CL (2009) Hybrid meta-heuristics for unrelated parallel machine scheduling with sequence-dependent setup times. Int J Adv Manuf Technol 43(1–2):161–169

    Article  Google Scholar 

  • Chung SH, Tai YT, Pearn WL (2009) An effective scheduling approach for maximizing polyimide printing weighted throughput in cell assembly factories. IEEE Trans Electron Packag Manuf 32(3):185–197

    Article  Google Scholar 

  • Driessel R, Moench L (2009) Scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints and ready times using variable neighborhood search. In: International Conference on Computers and Industrial Engineering, Troyes, France, July 06-09

  • Driessel R, Moench L (2011) Variable neighborhood search approaches for scheduling jobs on parallel machines with sequence-dependent setup times, precedence constraints, and ready times. Comput Ind Eng 61(2):336–345

    Article  Google Scholar 

  • Edis EB, Oguz C (2012) Parallel machine scheduling with flexible resources. Comput Ind Eng 63(2):433–447

    Article  Google Scholar 

  • Edis EB, Ozkarahan I (2011) A combined integer/constraint programming approach to a resource constrained parallel machine scheduling problem with machine eligibility restrictions. Eng Optim 43(2):135–157

    Article  Google Scholar 

  • Edis EB, Ozkarahan I (2012) Solution approaches for a real-life resource-constrained parallel machine scheduling problem. Int J Adv Manuf Technol 58(9–12):1141–1153

    Article  Google Scholar 

  • Edis EB, Oguz C, Ozkarahan I (2012) Solution approaches for simultaneous scheduling of jobs and operators on parallel machines. J Fac Eng Arch Gazi Univ 27(3):527–535

    Google Scholar 

  • Eliiyi D, Azizoglu M (2009) A fixed job scheduling problem with machine-dependent job weights. Int J Prod Res 47(9):2231–2256

    Article  Google Scholar 

  • Fanjul-Peyro L, Perea F, Ruiz R (2017) Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources. Eur J Oper Res 260(2):482–493

    Article  Google Scholar 

  • Gacias B, Artigues C, Lopez P (2010) Parallel machine scheduling with precedence constraints and setup times. Comput Oper Res 37(12):2141–2151

    Article  Google Scholar 

  • Gedik R, Rainwater C, Nachtmann H, Pohl E (2016) Analysis of a parallel machine scheduling problem with sequence dependent setup times and job availability intervals. Eur J Oper Res 251(2):640–650

    Article  Google Scholar 

  • Gokhale R, Mathirajan M (2012) Scheduling identical parallel machines with machine eligibility restrictions to minimize total weighted flow time in automobile gear manufacturing. Int J Adv Manuf Technol 60(9–12):1099–1110

    Article  Google Scholar 

  • Guimaraes L, Klabjan D, Almada-Lobo B (2013) Pricing, relaxing and fixing under lot sizing and scheduling. Eur J Oper Res 230:75–81

    Article  Google Scholar 

  • Joo CM, Kim BY (2012) Parallel machine scheduling problem with ready times, due times and sequence-dependent setup times using meta-heuristic algorithms. Eng Optim 44(9):1021–1034

    Article  Google Scholar 

  • Keskinturk T, Yildirim MB, Barut M (2012) An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup times. Comput Oper Res 39(6):1225–1235

    Article  Google Scholar 

  • Kim BK, Kim YD (2011) Heuristic algorithms for assigning and scheduling flight missions in a military aviation unit. Comput Ind Eng 61(4):1309–1317

    Article  Google Scholar 

  • Lee K, Leung JYT, Pinedo ML (2013) Makespan minimization in online scheduling with machine eligibility. Ann Oper Res 204(1):189–222

    Article  Google Scholar 

  • Li X, Yalaoui F, Amodeo L (2010) A multi objective meta-heuristic with a fuzzy logic controller for solving a scheduling problem. In: Computational intelligence: foundations and applications: proceedings of the 9th international FLINS conference, Emei, CHINA, August 02–04

  • Li K, Shia Y, Yanga S, Cheng B (2011) Parallel machine scheduling problem to minimize the makespan with resource dependent processing times. Appl Soft Comput 11(8):5551–5557

    Article  Google Scholar 

  • Li X, Chehade H, Yalaoui F, Amodeo L (2012) Fuzzy logic controller based multi-objective meta-heuristics to solve a parallel machines scheduling problem. J Mult Val Logic Soft Comput 18(5–6):617–636

    Google Scholar 

  • Lin SW, Lee ZJ, Ying KC, Lu CC (2011) Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates. Comput Oper Res 38(5):809–815

    Article  Google Scholar 

  • Liu M, Wu C (2003) Scheduling algorithm based on evolutionary computing in identical parallel machine production line. Robot Comput Integr Manuf 19(2003):401–407

    Article  Google Scholar 

  • Montoya-Torres JR, Soto-Ferrari M, Gonzalez-Solano F, Alfonso-Lizarazo EH (2009) Machine scheduling with sequence-dependent setup times using a randomized search heuristic. In: International conference on computers and industrial engineering troyes, France, July 06–09

  • Montoya-Torres JR, Soto-Ferrari M, Gonzalez-Solano F (2010) Production scheduling with sequence-dependent setups and job release times. Dyn Colomb 77(163):260–269

    Google Scholar 

  • Nessah R, Chengbin C, Yalaoui F (2007) An exact method for Pm/sds/Σ ni=1 ci problem. Comput Oper Res 34(9):2840–2848

    Article  Google Scholar 

  • Park T, Lee T, Kim CO (2012) Due-date scheduling on parallel machines with job splitting and sequence-dependent major/minor setup times. Int J Adv Manuf Technol 59(1–4):325–333

    Article  Google Scholar 

  • Pinedo ML (2009) Planning and scheduling in manufacturing and services. Springer, New York

    Book  Google Scholar 

  • Pinedo ML (2011) Scheduling theory, algorithms, and systems. Springer, New York

    Google Scholar 

  • Ruiz R, Andrés-Romano C (2011) Scheduling unrelated parallel machines with resource-assignable sequence-dependent setup times. Int J Adv Manuf Technol 57(5–8):777–794

    Article  Google Scholar 

  • Singha A, Rossi A, Sevaux M (2012) Matheuristic approaches for Q-coverage problem versions in wireless sensor networks. Eng Optim 45(5):609–626

    Article  Google Scholar 

  • Su LH, Chang WY, Chou FD (2011) Minimizing maximum lateness on identical parallel machines with flexible resources and machine eligibility constraints. Int J Adv Manuf Technol 56(9–12):1195–1204

    Article  Google Scholar 

  • Tahar DN, Yalaoui F, Chu C, Amodeo L (2006) A linear programming approach for identical parallel machine scheduling with job splitting and sequence-dependent setup times International. J Prod Econ 99:1–2

    Article  Google Scholar 

  • Turker AK, Sel C (2011) A hybrid approach on single server parallel machines scheduling problem with sequence-dependent setup times. J Fac. Eng Arch Gazi Univ 26(4):731–740

    Google Scholar 

Download references

Acknowledgements

This research did not receive any specific grant from funding agencies in the public, commercial, or not-for-profit sectors.

Author information

Authors and Affiliations

  1. Department of Industrial Engineering, Eskisehir Technical University, Iki Eylul Campus, 26555, Eskisehir, Turkey

    Emine Akyol Ozer

  2. Department of Industrial Engineering, Osmangazi University, Meselik, 26480, Eskisehir, Turkey

    Tugba Sarac

Authors
  1. Emine Akyol Ozer
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Tugba Sarac
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Emine Akyol Ozer.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Akyol Ozer, E., Sarac, T. MIP models and a matheuristic algorithm for an identical parallel machine scheduling problem under multiple copies of shared resources constraints. TOP 27, 94–124 (2019). https://doi.org/10.1007/s11750-018-00494-x

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s11750-018-00494-x

Keywords

Search

Navigation