zbMATH — the first resource for mathematics

Geometry Search for the term Geometry in any field. Queries are case-independent.
Funct* Wildcard queries are specified by * (e.g. functions, functorial, etc.). Otherwise the search is exact.
"Topological group" Phrases (multi-words) should be set in "straight quotation marks".
au: Bourbaki & ti: Algebra Search for author and title. The and-operator & is default and can be omitted.
Chebyshev | Tschebyscheff The or-operator | allows to search for Chebyshev or Tschebyscheff.
"Quasi* map*" py: 1989 The resulting documents have publication year 1989.
so: Eur* J* Mat* Soc* cc: 14 Search for publications in a particular source with a Mathematics Subject Classification code (cc) in 14.
"Partial diff* eq*" ! elliptic The not-operator ! eliminates all results containing the word elliptic.
dt: b & au: Hilbert The document type is set to books; alternatively: j for journal articles, a for book articles.
py: 2000-2015 cc: (94A | 11T) Number ranges are accepted. Terms can be grouped within (parentheses).
la: chinese Find documents in a given language. ISO 639-1 language codes can also be used.

a & b logic and
a | b logic or
!ab logic not
abc* right wildcard
"ab c" phrase
(ab c) parentheses
any anywhere an internal document identifier
au author, editor ai internal author identifier
ti title la language
so source ab review, abstract
py publication year rv reviewer
cc MSC code ut uncontrolled term
dt document type (j: journal article; b: book; a: book article)
Minimization of maximum lateness on parallel machines with sequence-dependent setup times and job release dates. (English) Zbl 1202.90138
Summary: We consider an identical parallel machine scheduling problem with sequence-dependent setup times and job release dates. An improved iterated greedy heuristic with a sinking temperature is presented to minimize the maximum lateness. To verify the developed heuristic, computational experiments are conducted on a well-known benchmark problem data set. The experimental results show that the proposed heuristic outperforms the basic iterated greedy heuristic and the state-of-art algorithms on the same benchmark problem data set. It is believed that this improved approach will also be helpful for other applications.

90B35Scheduling theory, deterministic
90C59Approximation methods and heuristics
Full Text: DOI
[1] Graham, R. L.; Lawler, E. L.; Lenstra, J. K.; Kan, A. H. G. Rinnooy: Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of discrete mathematics 5, 287-326 (1979) · Zbl 0411.90044
[2] Lenstra, J. K.; Kan, A. H. G. Rinnooy; Brucker, P.: Complexity of machine scheduling problems, Annals of discrete mathematics 1, 343-362 (1977) · Zbl 0353.68067
[3] Ullman, J. D.: NP-complete scheduling problem, Journal of computer and system sciences 10, 384-393 (1975) · Zbl 0313.68054 · doi:10.1016/S0022-0000(75)80008-0
[4] Allahverdi, A.; Gupta, J. N. D.; Aldowaisan, T.: A review of scheduling research involving setup considerations, Omega: international journal of management science 27, 219-239 (1999)
[5] Allahverdi, A.; Ng, C. T.; Cheng, T. C. E.; Kovalyov, M. Y.: A survey of scheduling problems with setup times or costs, European journal of operational research 187, 985-1032 (2008) · Zbl 1137.90474 · doi:10.1016/j.ejor.2006.06.060
[6] Ovacik, I. M.; Uzsoy, R.: Rolling horizon procedures for dynamic parallel machine scheduling with sequence-dependent setup times, International journal of production research 33, 3173-3192 (1995) · Zbl 0911.90217 · doi:10.1080/00207549508904867
[7] Lee, Z. J.; Lin, S. W.; Ying, K. C.: Scheduling jobs on dynamic parallel machines with sequence-dependent setup times, International journal of advanced manufacturing technology 47, 773-781 (2010)
[8] Kim, C. O.; Shin, H. J.: Scheduling jobs on parallel machines: a restricted tabu search approach, International journal of advanced manufacturing technology 22, 278-287 (2003)
[9] Jacobs, L. W.; Brusco, M. J.: A local-search heuristic for large set-covering problems, Naval research logistics quarterly 42, 1129-1140 (1995) · Zbl 0839.90085 · doi:10.1002/1520-6750(199510)42:7<1129::AID-NAV3220420711>3.0.CO;2-M
[10] Marchiori, E.; Steenbeek, A.: An evolutionary algorithm for large scale set covering problems with application to airline crew scheduling, Lecture notes in computer science 1803, 367-381 (2000)
[11] Ruiz, R.; Stützle, T.: A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European journal of operational research 177, 2033-2049 (2007) · Zbl 1110.90042 · doi:10.1016/j.ejor.2005.12.009
[12] Baraz, D.; Mosheiov, G.: A note on a greedy heuristic for flow-shop makespan minimization with no machine idle-time, European journal of operational research 184, 810-813 (2008) · Zbl 1168.90420 · doi:10.1016/j.ejor.2006.11.025
[13] Ruiz, R.; Stützle, T.: An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives, European journal of operational research 187, 1143-1159 (2008) · Zbl 1137.90514 · doi:10.1016/j.ejor.2006.07.029
[14] Ying, K. C.: Solving non-permutation flowshop scheduling problems by an effective iterated greedy heuristic, International journal of advanced manufacturing technology 38, 348-354 (2008)
[15] Ying, K. C.: An iterated greedy heuristic for multistage hybrid flowshop scheduling problems with multiprocessor tasks, Journal of the operational research 60, 810-817 (2009) · Zbl 1171.90412 · doi:10.1057/palgrave.jors.2602625
[16] Ying, K. C.; Lin, S. W.; Huang, C. Y.: Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic, Expert systems with applications 36, 7087-7092 (2009)