×

A tabu search approach for proportionate multiprocessor open shop scheduling. (English) Zbl 1295.90007

Summary: In the multiprocessor open shop scheduling problem, jobs are to be processed on a set of processing centers – each having one or more parallel identical machines, while jobs do not have a pre-specified obligatory route. A special case is the proportionate multiprocessor open shop scheduling problem (PMOSP) in which the processing time on a given center is not job-dependent. Applications of the PMOSP are evident in health care systems, maintenance and repair shops, and quality auditing and final inspection operations in industry. In this paper, a tabu search (TS) approach is presented for solving the PMOSP with the objective of minimizing the makespan. The TS approach utilizes a neighborhood search function that is defined over a network representation of feasible solutions. A set of 100 benchmark problems from the literature is used to evaluate the performance of the developed approach. Experimentations show that the developed approach outperforms a previously developed genetic algorithm as it produces solutions with an average of less than 5 % deviation from a lower bound, and 40 % of its solutions are provably optimal.

MSC:

90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming

Software:

Beam-ACO
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Matta, M.: An empirical and theoretical study of outpatient scheduling problems employing simulation and genetic algorithm methodologies. Ph.D. thesis, Duke University (2004) · Zbl 1122.90427
[2] Matta, M.E.: A genetic algorithm for the proportionate multiprocessor open shop. Comput. Oper. Res. 36(9), 2601-2618 (2009). doi:10.1016/j.cor.2008.11.009 · Zbl 1179.90144 · doi:10.1016/j.cor.2008.11.009
[3] Matta, M.E., Elmaghraby, S.E.: Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop. Eur. J. Oper. Res. 201(3), 720-728 (2010). doi:10.1016/j.ejor.2009.03.048 · Zbl 1176.90231 · doi:10.1016/j.ejor.2009.03.048
[4] Pinedo, M.: Scheduling: Theory, Algorithms, and Systems. Springer, Berlin (2012) · Zbl 1239.90002 · doi:10.1007/978-1-4614-2361-4
[5] Naderi, B., Fatemi Ghomi, S., Aminnayeri, M., Zandieh, M.: A study on open shop scheduling to minimise total tardiness. Int. J. Prod. Res. 49(15), 4657-4678 (2011). doi:10.1080/00207543.2010.497174 · Zbl 1356.90059 · doi:10.1080/00207543.2010.497174
[6] Gonzalez, T., Sahni, S.: Open shop scheduling to minimize finish time. J. Assoc. Comput. Mach. 23(4), 665-679 (1976) · Zbl 0343.68031 · doi:10.1145/321978.321985
[7] Shmoys, D.B., Stein, C., Wein, N.J.: Improved approximation algorithms for shop scheduling problems. SIAM J. Comput. 23(3), 617-632 (1994) · Zbl 0814.68026 · doi:10.1137/S009753979222676X
[8] Chen, B., Strusevich, V.A.: Approximation algorithms for three-machine open shop scheduling. ORSA J. Comput. 5(3), 321-326 (1993) · Zbl 0789.90040 · doi:10.1287/ijoc.5.3.321
[9] Fang, H.l.; Ross, P.; Corne, D., A promising hybrid GA/Heuristic approach for open-shop scheduling problems, 590-594 (1994)
[10] Alcaide, D., Sicilia, J., Vig, D.: A tabu search algorithm for the open shop problem. Bol. Soc. Estad. Investig. Oper. 5(2), 283-296 (1997) · Zbl 0892.90095
[11] Liaw, C.f.: A tabu search algorithm for the open shop scheduling problem. Comput. Oper. Res. 26, 109-126 (1999) · Zbl 0947.90048 · doi:10.1016/S0305-0548(98)00056-2
[12] Liaw, C.F.: Applying simulated annealing to the open shop scheduling problem. IIE Trans. 31(5), 457-465 (1999). doi:10.1080/07408179908969848 · doi:10.1080/07408179908969848
[13] Liaw, C.F.: A hybrid genetic algorithm for the open shop scheduling problem. Eur. J. Oper. Res. 124(1), 28-42 (2000). doi:10.1016/S0377-2217(99)00168-X · Zbl 0960.90039 · doi:10.1016/S0377-2217(99)00168-X
[14] Prins, C.: Competitive genetic algorithms for the open-shop scheduling problem. Math. Methods Oper. Res. 52(3), 389-411 (2000). doi:10.1007/s001860000090 · Zbl 1023.90030 · doi:10.1007/s001860000090
[15] Blum, C.: Beam-ACO-hybridizing ant colony optimization with beam search: an application to open shop scheduling. Comput. Oper. Res. 32(6), 1565-1591 (2005). doi:10.1016/j.cor.2003.11.018 · Zbl 1122.90427 · doi:10.1016/j.cor.2003.11.018
[16] Sha, D., Hsu, C.Y.: A new particle swarm optimization for the open shop scheduling problem. Comput. Oper. Res. 35(10), 3243-3261 (2008). doi:10.1016/j.cor.2007.02.019 · Zbl 1133.90017 · doi:10.1016/j.cor.2007.02.019
[17] Schuurman, P., Woeginger, G.J.: Approximation algorithms for the multiprocessor open shop scheduling problem. Oper. Res. Lett. 24, 157-163 (1999) · Zbl 0967.90049 · doi:10.1016/S0167-6377(99)00005-X
[18] Sevastianov, S., Woeginger, G.: Linear time approximation scheme for the multiprocessor open shop problem. Discrete Appl. Math. 114(1-3), 273-288 (2001). doi:10.1016/S0166-218X(00)00375-9 · Zbl 1020.68016 · doi:10.1016/S0166-218X(00)00375-9
[19] Sevastianov, S.V., Woeginger, G.J.: Makespan minimization in open shops: a polynomial time approximation scheme. Math. Program. 82, 191-198 (1998) · Zbl 0920.90075
[20] Naderi, B., Fatemi Ghomi, S., Aminnayeri, M., Zandieh, M.: Scheduling open shops with parallel machines to minimize total completion time. J. Comput. Appl. Math. 235(5), 1275-1287 (2011). doi:10.1016/j.cam.2010.08.013 · Zbl 1200.90083 · doi:10.1016/j.cam.2010.08.013
[21] Glover, F.: Tabu search: part I. ORSA J. Comput. 1, 190-206 (1989) · Zbl 0753.90054 · doi:10.1287/ijoc.1.3.190
[22] Glover, F.: Tabu search: part II. ORSA J. Comput. 2, 4-32 (1990) · Zbl 0771.90084 · doi:10.1287/ijoc.2.1.4
[23] Roy, B., Sussmann, B.: Les problemes d’ordonnancement avec constraints disjunctives. Tech. Rep. 9, SEMA, Paris (1964) · Zbl 0615.90083
[24] Abdelmaguid, T.F.: Permutation-induced acyclic networks for the job shop scheduling problem. Appl. Math. Model. 33(3), 1560-1572 (2009). doi:10.1016/j.apm.2008.02.004 · Zbl 1168.90414 · doi:10.1016/j.apm.2008.02.004
[25] Grabowski, J., Nowicki, E., Zdrzałka, S.: A block approach for single-machine scheduling with release dates and due dates. Eur. J. Oper. Res. 26(2), 278-285 (1986). doi:10.1016/0377-2217(86)90191-8 · Zbl 0603.90073 · doi:10.1016/0377-2217(86)90191-8
[26] Nowicki, E., Smutnicki, C.: A fast taboo search algorithm for the job shop problem. Manag. Sci. 42(6), 797-813 (1996) · Zbl 0880.90079 · doi:10.1287/mnsc.42.6.797
[27] Laarhoven, P.J.M.V., Aarts, E.H.L., Lenstra, J.K.: Job shop scheduling by simulated annealing. Oper. Res. 40(1), 113-125 (1992) · Zbl 0751.90039 · doi:10.1287/opre.40.1.113
[28] Glover, F.: Future paths for integer programming and links to artificial intelligence. Comput. Oper. Res. 13(5), 533-549 (1986). doi:10.1016/0305-0548(86)90048-1 · Zbl 0615.90083 · doi:10.1016/0305-0548(86)90048-1
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.