×

A mathematical model and heuristic algorithms for an unrelated parallel machine scheduling problem with sequence-dependent setup times, machine eligibility restrictions and a common server. (English) Zbl 1458.90253

Summary: Parallel machine scheduling problems with common servers have many industrial applications. In this paper, we study a generalized problem of scheduling with a common server, which is the unrelated parallel machine scheduling problem with sequence-dependent setup times and machine eligibility restrictions. The objective function involves the minimization of the total weighted tardiness. A mixed integer linear programming (MILP) model is proposed to solve this complex problem. Due to the NP hardness of the problem, tabu search (TS) and simulated annealing (SA) algorithms are proposed. The initial solutions of the algorithms are obtained by a modified apparent tardiness cost with setups (ATCS) dispatching rule. The proposed algorithms are compared using a randomly generated data set.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abdekhodaee, A. H.; Wirth, A., Scheduling parallel machines with a single server: Some solvable cases and heuristics, Comput. Oper. Res., 29, 3, 295-315, (2002) · Zbl 0993.90047
[2] Abdekhodaee, A. H.; Wirth, A.; Gan, H. S., Equal processing and equal setup time cases of scheduling parallel machines with a single server, Comput. Oper. Res., 31, 11, 1867-1889, (2004) · Zbl 1068.68030
[3] Abdekhodaee, A. H.; Wirth, A.; Gan, H. S., Scheduling two parallel machines with a single server: the general case, Comput. Oper. Res., 33, 4, 994-1009, (2006) · Zbl 1079.90043
[4] Afzalirad, M.; Rezaeian, J., A realistic variant of bi- objective unrelated parallel machine scheduling problem: NSGA II and MOACO approaches, Appl. Soft Comput., 50, 109-123, (2017)
[5] Alagöz, O.; Azizoğlu, M., Rescheduling of identical parallel machines under machine eligibility constraints, Eur. J. Oper. Res., 149, 3, 523-532, (2003) · Zbl 1033.90031
[6] Bektur, G.; Saraç, T., Two parallel injection machine scheduling under crane constraint, J. Fac. Eng. Archit. Gazi Univ., 21, 4, 903-911, (2016)
[7] Bilge, Ü.; Kıraç, F.; Kutulan, M.; Akgün, P., A tabu search algorithm for parallel machine total tardiness problem, Comput. Oper. Res., 31, 3, 397-414, (2004) · Zbl 1057.90516
[8] Bozorgirad, M. A.; Logendran, R., Sequence dependent group scheduling problem on unrelated parallel machines, Expert Syst. Appl., 39, 10, 9021-9030, (2012)
[9] Brucker, P.; Dhaenens- Flipo, C.; Knust, S.; Kravchenko, S. A.; Werner, F., Complexity results for parallel machine problems with a single server, J. Sched., 5, 6, 429-457, (2002) · Zbl 1040.90016
[10] Chang, P. C.; Chen, S. H., Integrating dominance properties with genetic algorithms for parallel machine scheduling problems with setup times, Appl. Soft Comput., 11, 1263-1274, (2011)
[11] Chen, C. L.; Chen, C. L., Hybrid metaheuristics for unrelated parallel machine scheduling with sequence dependent setup times, Int. J. Adv. Manuf. Technol., 43, 161-169, (2009)
[12] Chen, J. F., Scheduling on unrelated parallel machines with sequence and machine dependent setup times and due date constraints, Int. J. Adv. Manuf. Technol., 44, 1204-1212, (2009)
[13] Chen, C. L., Iterated hybrid metaheuristic algorithms for unrelated parallel machines problem with unequal ready times and sequence dependent setup times, Int. J. Adv. Manuf. Technol., 60, 693-705, (2012)
[14] Du, J.; Leung, J. Y.T., Minimizing total tardiness on one machine is NP- hard, Math. Oper. Res., 15, 3, 483-495, (1990) · Zbl 0714.90052
[15] Gan, H.; Wirth, A.; Abdekhodaee, A., A branch-and-price algorithm for the general case of scheduling parallel machines with a single server, Comput. Oper. Res., 39, 9, 2242-2247, (2012) · Zbl 1251.90144
[16] Glass, C. A.; Shafransky, Y. M.; Strusevich, V. A., Scheduling for parallel dedicated machines with a single server, Nav. Res. Logist., 47, 4, 304-328, (2000) · Zbl 0968.90036
[17] Glass, C. A.; Potts, C. N.; Shade, P., Unrelated parallel-machine scheduling using local search, Math. Comput. Model., 20, 41-52, (1994) · Zbl 0810.90066
[18] Glover, F., Future paths for integer programming and links to artificial intelligence, Comput. Oper. Res., 13, 533-549, (1986) · Zbl 0615.90083
[19] Graham, R.; Lawler, L. E.L.; Lenstra, J. K.L.; Rinnooy Kan, A. H.G., Optimization and approximation in deterministic sequencing and scheduling: a surver, Ann. Discrete Math., 5, 287-326, (1979) · Zbl 0411.90044
[20] Guirchoun, S.; Souhkal, A.; Martineau, P., Complexity results for parallel machine scheduling problems with a server in computer systems, (In Proceedings of the 2nd Multidisciplinary International Conference on Scheduling: Theory and Applications (MISTA), (2005)), 232-236
[21] Güngör, Z.; Ünler, A., K- Harmonic means data clustering with tabu- search method, Appl. Math. Model., 32, 6, 1115-1125, (2008) · Zbl 1145.68395
[22] Hall, N. G.; Potts, C. N.; Sriskandarajah, C., Parallel machine scheduling with a common server, Discrete Appl. Math., 102, 3, 223-243, (2000) · Zbl 0972.90031
[23] Hamzadayı, A.; Yıldız, G., Event driven strategy based complete rescheduling approaches for dynamic m identical parallel machines scheduling problem with a common server, Comput. Ind. Eng., 91, 66-84, (2016)
[24] Hamzadayı, A.; Yıldız, G., Hybrid strategy based complete rescheduling approaches for dynamic m identical parallel machines scheduling problem with a common server, Simul. Model. Pract. Theory, 63, 104-132, (2016)
[25] Hamzadayı, A.; Yildiz, G., Modeling and solving static m identical parallel machines scheduling problem with a common server and sequence dependent setup times, Comput. Ind. Eng., 106, 287-298, (2017)
[26] Hasani, K.; Kravchenko, S. A.; Werner, F., Simulated annealing and genetic algorithms for the two machine scheduling problem with a single server, Int. J. Prod. Res., 52, 13, 3778-3792, (2014)
[27] Hasani, K.; Kravchenko, S. A.; Werner, F., Block models for scheduling jobs on two parallel machines with a single server, Comput. Oper. Res., 41, 94-97, (2014) · Zbl 1348.90270
[28] Huang, S.; Cai, L.; Zhang, X., Parallel dedicated machine scheduling problem with sequence-dependent setups and a single server, Comput. Opera. Res., 58, 1, 165-174, (2010)
[29] Jiang, Y.; Dong, J.; Ji, M., Preemptive scheduling on two parallel machines with a single server, Comput. Ind. Eng., 66, 2, 514-518, (2013)
[30] Jiang, Y.; Zhang, Q.; Hu, J.; Dong, J.; Ji, M., Single server parallel machine scheduling with loading and unloading times, J. Comb. Optim., 30, 2, 201-213, (2015) · Zbl 1319.90032
[31] Kayvanfar, V.; Teymourian, E., Hybrid intelligent water drops algorithm to unrelated parallel machines scheduling problem: a just-in-time approach, Int. J. Prod. Res., 52, 19, 5857-5879, (2014)
[32] Kim, M.; Lee, Y. H., MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server, Comput. Oper. Res., 39, 11, 2457-2468, (2012) · Zbl 1251.90156
[33] Kim, C. O.; Shin, H. J., Scheduling jobs on parallel machines: a restricted tabu search approach, Int. J. Adv. Manuf. Technol., 22, 278-287, (2003)
[34] Kim, D. W.; Kim, K. H.; Jang, W.; Chen, F. F., Unrelated parallel machine scheduling with setup times using simulated annealing, Robot. Comput. Integr. Manuf., 18, 3, 223-231, (2002)
[35] Kirkpatrick, S.; Gelatt, S. C.D.; Vecchi, M. P., Optimization by simulated annealing, Science, 220, 4598, 671-680, (1983) · Zbl 1225.90162
[36] Koulamas, C. P., Scheduling two parallel semiautomatic machines to minimize machine interference, Comput. Oper. Res., 23, 10, 945-956, (1996) · Zbl 0863.90089
[37] Kravchenko, S. A.; Werner, F., Parallel machine scheduling problems with a single server, Math. Comput. Modell., 26, 12, 1-11, (1997) · Zbl 1185.90082
[38] Kravchenko, S. A.; Werner, F., Scheduling on Parallel Machines with a Single and Multiple Servers, 1-18, (1998), Otto- van- Guericke- Universitat Mgdeburg
[39] Kravchenko, S. A.; Werner, F., A heuristic algorithm for minimizing mean flow time with unit setups, Inf. Process. lett., 79, 6, 291-296, (2001) · Zbl 1032.68026
[40] Kuei, L. Y.; Wei, L. C., Dispatching rules for unrelated parallel machine scheduling with release dates, Int. J. Adv. Manuf. Technol., 67, 269-279, (2013)
[41] Lee, Y. H.; Bhaskaran, K.; Pinedo, M., A heuristic to minimize the total weigted tardiness with sequence- dependent setups, IIE Trans., 29, 1, 45-52, (1997)
[42] Lee, J. H.; Yu, J. M.; Lee, D. H., A tabu search algorithm for unrelated parallel machine scheduling with sequence and machine dependent setups: minimizing total tardiness, Int. J. Adv. Manuf. Technol., 69, 2081-2089, (2013)
[43] Lin, Y. K.; Fowler, J. W.; Pfund, M. E., Multiple- objective heuristics for scheduling unrelated parallel machines, Eur. J. Oper. Res., 227, 239-253, (2013)
[44] Mönch, L.; Balasubramanian, H.; Fowler, J. W.; Pfund, M. E., Heuristic scheduling of jobs on parallel batch machines with incompatible job families and unequal ready times, Comput. Oper. Res., 32, 2731-2750, (2005) · Zbl 1071.90019
[45] Ou, J.; Qi, X.; Lee, C. Y., Parallel machine scheduling with multiple unloading servers, J. Sched., 13, 3, 213-226, (2010) · Zbl 1193.90108
[46] Özpeynirci, S.; Gökgür, B.; Hnich, B., Parallel machine scheduling with tool loading, Appl. Math. Model., 40, 9-10, 5660-5671, (2016)
[47] Pfund, M.; Fowler, J. W.; Gadkari, A.; Chen, Y., Scheduling jobs on parallel machines with setup times and ready times, Comput. Ind. Eng., 54, 764-782, (2008)
[48] Sarıçiçek, İ.; Çelik, C., Two meta- heuristics for parallel machine scheduling with job splitting to minimize total tardiness, Appl. Math. Model., 35, 8, 4117-4126, (2011) · Zbl 1221.90049
[49] Sels, V.; Coelho, J.; Dias, A. M.; Vanhoucke, M., Hybrid tabu search and truncated branch and bound for the unrelated parallel machine scheduling problem, Comput. Oper. Res., 53, 107-117, (2015) · Zbl 1348.90308
[50] Su, C., Online LPT algorithms for parallel machines scheduling with a single server, J. Comb. Optim., 26, 3, 480-488, (2011) · Zbl 1282.90077
[51] Türker, A. K.; Sel, Ç., A hybrit approach on single server parallel machines scheduling problem with sequence dependent setup times, J. Fac. Eng. Archit. Gazi Univ., 26, 4, 731-740, (2011)
[52] Vallada, E.; Ruben, R., A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times, Eur. J. Oper. Res., 211, 3, 612-622, (2011)
[53] Werner, F.; Kravchenko, S. A., Scheduling with multiple servers, Autom. Remote Control, 71, 10, 2109-2121, (2010) · Zbl 1218.93058
[54] Yang-Kueui, L.; Chi- Wei, L., Dispatching rules for unrelated parallel machine scheduling with release dates, Int. J. Adv. Manuf. Technol., 67, 1, 269-279, (2013)
[55] Zhang, L.; Wirth, A., On-line scheduling of two parallel machines with a single server, Comput. Oper. Res., 36, 5, 1529-1553, (2009) · Zbl 1177.90193
[56] Zhang, A.; Wang, H.; Chen, Y.; Chen, G., Scheduling jobs with equal processing times and a single server on parallel identical machines, Discrete Appl. Math., 213, 196-206, (2016) · Zbl 1353.90069
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.