×
Brueggemann, Tobias; Hurink, Johann L.

Matching based very large-scale neighborhoods for parallel machine scheduling. (English) Zbl 1237.90084

J. Heuristics 17, No. 6, 637-658 (2011).
Summary: In this paper we study very large-scale neighborhoods for the minimum total weighted completion time problem on parallel machines, which is known to be strongly NP-hard. We develop two different ideas leading to very large-scale neighborhoods in which the best improving neighbor can be determined by calculating a weighted matching. The first neighborhood is introduced in a general fashion using combined operations of a basic neighborhood. Several examples for basic neighborhoods are given. The second approach is based on a partitioning of the job sets on the machines and a reassignment of them. In a computational study we evaluate the possibilities and the limitations of the presented very large-scale neighborhoods.

Cited in 2 Documents

MSC:

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

Keywords:

scheduling; parallel machines; total weighted completion time; very large-scale neighborhoods; local search
Cite Review PDF
Full Text: DOI
OA License

References:

[1] Agarwal, R., Ergun, Ö., Orlin, J.B., Potts, C.N.: Solving parallel machine scheduling problems with very-large scale neighborhood search. Working paper (2007). http://www2.isye.gatech.edu/\(\sim\)oergun/publications/ParallelMachineJOS.pdf , J. Sched., to appear
[2] Ahuja, R.K., Özlem, E., Orlin, J.B., Punnen, A.P.: A survey of very large-scale neighborhood search techniques. Discrete Appl. Math. 123, 75–102 (2002) · Zbl 1014.68052 · doi:10.1016/S0166-218X(01)00338-9
[3] van den Akker, J.M., Hoogeveen, J.A., van de Velde, S.L.: Parallel machine scheduling by column generation. Oper. Res. 47, 862–872 (1999) · Zbl 0979.90051 · doi:10.1287/opre.47.6.862
[4] Baker, K.R., Merten, A.G.: Scheduling with parallel processors and linear delay costs. Nav. Res. Logist. Q. 20, 793–804 (1973) · Zbl 0273.90030 · doi:10.1002/nav.3800200417
[5] Barnes, J.W., Laguna, M.: Solving the multiple-machine weighted flow time problem using tabu search. IIE Trans. 25(2), 121–128 (1993) · doi:10.1080/07408179308964284
[6] Belouadah, H., Potts, C.N.: Scheduling identical parallel machines to minimize total weighted completion time. Discrete Appl. Math. 48(3), 201–218 (1994) · Zbl 0809.90073 · doi:10.1016/0166-218X(92)00176-M
[7] Brucker, P.: Scheduling Algorithms, 4th edn. Springer, Berlin (2004) · Zbl 1060.90034
[8] Brueggemann, T., Hurink, J.L.: Two exponential neighborhoods for single machine scheduling. OR Spectrum 29, 513–533 (2007) · Zbl 1145.90018 · doi:10.1007/s00291-006-0052-5
[9] Chen, Z.L., Powell, W.B.: Solving parallel machine scheduling problems by column generation. INFORMS J. Comput. 11, 78–94 (1999) · Zbl 1034.90506 · doi:10.1287/ijoc.11.1.78
[10] Congram, R.K., Potts, C.P., van de Velde, S.L.: An iterated dynasearch algorithm for the single machine total weighted tardiness problem. INFORMS J. Comput. 14, 52–67 (2002) · Zbl 1238.90061 · doi:10.1287/ijoc.14.1.52.7712
[11] Deineko, V., Woeginger, G.J.: A study of exponential neighborhoods for the traveling salesman problem and the quadratic assignment problem. INFORMS J. Comput. 14, 52–67 (2000)
[12] Eastman, W.L., Even, S., Isaacs, I.M.: Bounds for the optimal scheduling of n jobs on m processors. Manag. Sci. 11, 268–279 (1964) · doi:10.1287/mnsc.11.2.268
[13] Edmonds, J.: Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bureau Stand. B 69, 125–130 (1965) · Zbl 0141.21802 · doi:10.6028/jres.069B.013
[14] Elmaghraby, S.E., Park, S.H.: Scheduling jobs on a number of identical machines. Trans. Am. Inst. Ind. Eng. 6, 1–12 (1974)
[15] Ergun, Ö., Orlin, J.B., Steele-Feldman, A.: Creating very large-scale neighborhoods out of smaller ones by compounding moves. J. Heuristics 12, 115–140 (2006) · Zbl 1122.68593 · doi:10.1007/s10732-006-5561-5
[16] Gabow, H.N.: Implementation of algorithms for maximum matching on nonbipartite graphs. Ph.D. Thesis, Department of Computer Science, Stanford University, Stanford, California (1973)
[17] Garey, M.R., Johnson, D.S.: Computers and Intractability. A Guide to the Theory of NP-Completeness. Freeman, New York (1979) · Zbl 0411.68039
[18] Graham, R.L., Lawler, E.L., Lenstra, J.K., Rinnooy Kan, A.H.G.: Optimization and approximation in deterministic sequencing and scheduling: a survey. Ann. Discrete Math. 5, 287–326 (1979) · Zbl 0411.90044 · doi:10.1016/S0167-5060(08)70356-X
[19] Hoede, C.: Private communication (2006)
[20] Hurink, J.: An exponential neighborhood for a one machine batching problem. OR Spektrum 21, 461–476 (1999) · Zbl 0940.90039 · doi:10.1007/s002910050098
[21] Kawaguchi, T., Kyan, S.: Worst case bound of an LRF schedule for the mean weighted flow-time problem. SIAM J. Comput. 15(4), 1119–1129 (1986) · Zbl 0621.68024 · doi:10.1137/0215081
[22] Lawler, E.L.: Combinatorial Optimization: Networks and Matroids. Holt, Rinehart and Winston, New York (1976) · Zbl 0413.90040
[23] Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P.: Complexity of machine scheduling problems. Ann. Discrete Math. 1, 343–362 (1977) · Zbl 0353.68067 · doi:10.1016/S0167-5060(08)70743-X
[24] Potts, C.N., van de Velde, S.L.: Dynasearch-iterative local improvement by dynamic programming: Part 1. The traveling salesman problem. Technical Report, University of Twente, Enschede, The Netherlands (1995)
[25] Sahni, S.K.: Algorithms for scheduling independent tasks. J. Assoc. Comput. Mach. 23, 116–127 (1976) · Zbl 0326.68024 · doi:10.1145/321921.321934
[26] Skutella, M., Woeginger, G.J.: A PTAS for minimizing the total weighted completion time on identical parallel machines. Math. Oper. Res. 25, 63–75 (2000) · Zbl 1073.90564 · doi:10.1287/moor.25.1.63.15212
[27] Smith, W.E.: Various optimizers for single-stage production. Nav. Res. Logist. Q. 3, 59–66 (1956). Math. Oper. Res. 25, 63–75 · doi:10.1002/nav.3800030106
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.