Abstract
The problem dealt with in this study has job sequence-dependent setup times under suitable machine constraints and due date constraints. The performance criterion for this problem is to minimize the sum of makespan and total tardiness. In the literature, an application of ABC algorithm for the problems which includes all the properties that we have dealt has not been discussed. Because there is no appropriate test data, a real-life data was collected from a factory. In this study, a new approach has been proposed for the solution with meta-heuristics of unrelated parallel machine scheduling problems which is a combinatorial problem. This new neighborhood approach provides different machine assignments for every candidate job sequences. This approach is used by integrating into ABC and GA. To evaluate the performances of the algorithms, the real-life problem was solved by using ABC and GA algorithms under similar conditions. It was found that all jobs can be completed in two shifts without the need for a third shift. Computational results show that ABC algorithm has better performance than GA.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Pinedo M (2012) Scheduling: theory, algorithms, and systems. Springer Science Business Media, New York
Allahverdi A, Ng C, Cheng T, Kovalyov MY (2008) A survey of scheduling problems with setup times or costs. Eur J Oper Res 187(3):985–1032
Akyol S, Alataş B (2012) Güncel Sürü Zekası Optamizasyon Algoritmaları. Nevşehir Universitesi Fen Bilimleri Enstitusu Dergisi 1(1):36–50
Bozorgirad MA, Logendran R (2012) Sequence-dependent group scheduling problem on unrelated-parallel machines. Expert Syst Appl 39(10):9021–9030
Eren T, Güner E (2002) Tek ve paralel makineli problemlerde çok olcutlu cizelgeleme problemleri için bir literatur taramasi. Gazi Universitesi Muhendislik Mimarlik Dergisi 17(4):37–69
Shim SO (2009) Generating subproblems in branch and bound algorithms for parallel machines scheduling problem. Comput Ind Eng 57(3):1150–1153. doi:10.1016/j.cie.2009.02.013
Gharehgozli A, Tavakkoli-Moghaddam R, Zaerpour N (2009) A fuzzy-mixed-integer goal programming model for a parallel-machine scheduling problem with sequence-dependent setup times and release dates. Robot Cim-Int Manuf 25(4):853–859
Ponnambalam S, Aravindan P, Chandrasekaran S (2001) Constructive and improvement flow shop scheduling heuristics: an extensive evaluation. Prod Plan Control 12(4):335–344
Fan L, Zhang F, Gongming W, Zhiyong L (2009) An effective scheduling algorithm for linear makespan minimization on unrelated parallel machines. International Conference on High Performance Computing, Kochi,16-19 Dec 2009, pp 40–49
Lin YK, Lin CW (2013) Dispatching rules for unrelated parallel machine scheduling with release dates. Int J Adv Manuf Tech 67(1–4):269–279
Low CY, Hsu CJ, Su CT (2008) A two-stage hybrid flowshop scheduling problem with a function constraint and unrelated alternative machines. Comput Oper Res 35(3):845–853
Fanjul-Peyro L, Ruiz R (2012) Scheduling unrelated parallel machines with optional machines and jobs selection. Comput Oper Res 39(7):1745–1753
Li K, Yang S (2009) Non-identical parallel-machine scheduling research with minimizing total weighted completion times: models, relaxations and algorithms. Appl Math Model 33(4):2145–2158
Güler A (2008) Tamsayılı Programlama Problemleri İçin Garanti Değerli Algoritmalar, MSc Thesis, Turkey
Muratore G, Schwarz UM, Woeginger GJ (2010) Parallel machine scheduling with nested job assignment restrictions. Oper Res Lett 38(1):47–50
Svensson O (2012) Santa Claus schedules jobs on unrelated machines. Siam J Comput 41(5):1318–1341
Osman IH, Laporte G (1996) Metaheuristics: a bibliography. Ann Oper Res 63(5):511–623
Tavakkoli-Moghaddam R, Taheri F, Bazzazi M, Izadi M, Sassani F (2009) Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints. Comput Oper Res 36(12):3224–3230
Chyu C-C, Chang W-S (2010) A Pareto evolutionary algorithm approach to bi-objective unrelated parallel machine scheduling problems. Int J Adv Manuf Technol 49(5–8):697–708
Logendran R, McDonell B, Smucker B (2007) Scheduling unrelated parallel machines with sequence-dependent setups. Comput Oper Res 34(11):3420–3438
Chen C-L, Chen C-L (2009) Hybrid metaheuristics for unrelated parallel machine scheduling with sequence-dependent setup times. Int J Adv Manuf Technol 43(1–2):161–169
Kim D-W, Kim K-H, Jang W, Frank Chen F (2002) Unrelated parallel machine scheduling with setup times using simulated annealing. Robot Cim-Int Manuf 18(3):223–231
Chen J-F (2009) Scheduling on unrelated parallel machines with sequence-and machine-dependent setup times and due-date constraints. Int J Adv Manuf Technol 44(11–12):1204–1212
Wang W-L, Wang H-Y, Zhao Y-W, Zhang L-P, Xu X-L (2012) Parallel machine scheduling with splitting jobs by a hybrid differential evolution algorithm. Comput Oper Res 40(5):1196–1206
Lin CW, Lin YK, Hsieh HT (2013) Ant colony optimization for unrelated parallel machine scheduling. Int J Adv Manuf Tech 67(1–4):35–45
Rodriguez FJ, García-Martínez C, Blum C, Lozano M (2012) An artificial bee colony algorithm for the unrelated parallel machines scheduling problem. In: Parallel Problem Solving from Nature-PPSN XII. Springer, pp 143–152
Ying KC, Lin SW (2012) Unrelated parallel machine scheduling with sequence- and machine-dependent setup times and due date constraints. Int J Innov Comput I 8(5A):3279–3297
Lin SW, Ying KC (2014) ABC-based manufacturing scheduling for unrelated parallel machines with machine-dependent and job sequence-dependent setup times. Comput Oper Res 51:172–181
Karaboga D (2005) An idea based on honey bee swarm for numerical optimization. Techn Rep TR06, Erciyes Univ Press, Erciyes
Karaboğa D (2004) Yapay zeka optimizasyon algoritmaları. Atlas Yayin Dagitim, Istanbul, pp 75–112
Akay B (2009) Nümerik Optimizasyon Problemlerinde Yapay Arı Kolonisi Algoritmasının Performans Analizi. PhD Thesis, Turkey
Li JQ, Pan QK, Tasgetiren MF (2014) A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Appl Math Model 38:2145–2158
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Caniyilmaz, E., Benli, B. & Ilkay, M.S. An artificial bee colony algorithm approach for unrelated parallel machine scheduling with processing set restrictions, job sequence-dependent setup times, and due date. Int J Adv Manuf Technol 77, 2105–2115 (2015). https://doi.org/10.1007/s00170-014-6614-9
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-014-6614-9