Scheduling with time-dependent discrepancy times
Publication date
2016-04-15
Document type
Forschungsartikel
Author
Sedding, Helmut A.
Organisational unit
University of Augsburg
Scopus ID
Publisher
Springer
Series or journal
Journal of Scheduling
ISSN
Periodical volume
19
Periodical issue
6
First page
737
Last page
757
Part of the university bibliography
Nein
Language
English
Keyword
Assembly-line worker path minimization
Convex processing time
Nonmonotonic piecewise-linear processing time
Single-machine scheduling
Time-dependent scheduling
Abstract
In time-dependent scheduling, various processing time functions are studied, yet absolute value functions have surprisingly been omitted from the discussion. Such a processing time function increases linearly with a job’s discrepancy from its ideal midtime. The objective is to find a schedule that minimizes the makespan, introducing the discrepancy time minimization problem. This single-machine scheduling problem with time-dependent processing times is motivated by optimization of walking times on a car assembly line. Its decision version is NP hard, as we show by reduction of the even–odd partition problem. For the variant with known start time, we develop several heuristics. Further insights form lower bounds and dominance rules for a branch-and-bound search. Numerical experiments show the performance of our algorithms on problem instances of up to 60 jobs. For the variant with common ideal midtime and flexible start time, we present a polynomial-time algorithm.
Version
Published version
Access right on openHSU
Metadata only access