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)
Parallel machine total tardiness scheduling with a new hybrid metaheuristic approach. (English) Zbl 1127.90020

Summary: This work proposes a hybrid metaheuristic (HMH) approach which integrates several features from tabu search (TS), simulated annealing (SA) and variable neighbourhood search (VNS) in a new configurable scheduling algorithm. In particular, either a deterministic or a random candidate list strategy can be used to generate the neighbourhood of a solution, both a tabu list mechanism and the SA probabilistic rule can be adopted to accept solutions, and the dimension of the explored neighbourhood can be dynamically modified. The considered class of scheduling problems is characterized by a set of independent jobs to be executed on a set of parallel machines with non-zero ready times and sequence dependent setups. In particular, the NP-hard generalized parallel machine total tardiness problem (GPMTP) recently defined by Ü. Bilge, F. Kiraç, M. Kurtulan and P. Pekgün [Comput. Oper. Res. 31, No. 3, 397–414 (2004; Zbl 1057.90516)], is faced. Several alternative configurations of the HMH have been tested on the same benchmark set used by Bilge et al. The results obtained highlight the appropriateness of the proposed approach. Algorithms based on metaheuristics have been quite extensively used to face scheduling problems and they are a valuable tool to provide high quality solutions. A metaheuristic describes principles and features that need to be tailored on the specific problem under concern to define a customized approach.

This work aims to evaluate the possibility of defining a hybrid customizable neighbourhood search algorithm for combinatorial problems as a combination of a subset of concepts and features from three main metaheuristics of reference, i.e., the TS, the SA and the VNS. The proposed HMH approach is applied to the difficult problem of minimizing the total tardiness in parallel machines scheduling; in particular, a generalized version of such a problem has been considered, which makes it closer to several real industrial applications since it takes into account non-zero ready times, distinct due dates, uniform machines and setup times, recently proposed by Bilge, Kiraç, Kurtulan and Pekgün (loc. cit.). To evaluate the effectiveness of the HMH for the generalized parallel machine total tardiness scheduling problem, a relevant benchmark available from the literature has been considered.

90B35Scheduling theory, deterministic
90C59Approximation methods and heuristics