Zurück zu den Preprints des Jahres 2005


2005-32

Metaheuristic Approaches for the Two-Machine Flow-Shop Problem with Weighted Late Work Criterion and Common Due Date

by Blazewicz, J., Pesch, E., Sterna, M., Werner, F..


Series: 2005-32, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
In this paper, metaheuristic approaches for the two-machine flow shop
problem with a common due date and the weighted late work performance measure
are presented. The late work criterion estimates the quality of a solution with
regard to the duration of the late parts of jobs, not taking into account the
quantity of the delay for the fully late activities. Since the problem mentioned
is known to be NP-hard, three trajectory methods, namely simulated annealing,
tabu search and variable neighborhood search are proposed based on the features
of the case under consideration. Then the results of computational experiments
are reported, in which the metaheuristics were compared one to each other as
well as to an exact approach and a list scheduling algorithm.

Keywords:
Scheduling, flow-shop, late work criteria, metaheuristic, tabu search, simulated annealing, variable neighborhood search

This paper was published in:
Computers & Operations Research, Vol. 35, No. 2, 2008, 574 - 599.