Publikationstyp: Beitrag in wissenschaftlicher Zeitschrift
Art der Begutachtung: Peer review (Publikation)
Titel: Scheduling with time-dependent discrepancy times
Autor/-in: Jaehn, Florian
Sedding, Helmut
et. al: No
DOI: 10.1007/s10951-016-0472-2
Erschienen in: Journal of Scheduling
Band(Heft): 19
Heft: 6
Seiten: 737
Seiten bis: 757
Erscheinungsdatum: 2016
Verlag / Hrsg. Institution: Springer
ISSN: 1094-6136
1099-1425
Sprache: Englisch
Schlagwörter: Time-dependent scheduling; Nonmonotonic piecewise-linear processing time; Convex processing time; Single-machine scheduling; Assembly-line worker path minimization
Fachgebiet (DDC): 005: Computerprogrammierung, Programme und Daten
658.5: Produktionssteuerung
Zusammenfassung: 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.
URI: https://digitalcollection.zhaw.ch/handle/11475/18590
Volltext Version: Publizierte Version
Lizenz (gemäss Verlagsvertrag): Lizenz gemäss Verlagsvertrag
Departement: School of Engineering
Organisationseinheit: Institut für Datenanalyse und Prozessdesign (IDP)
Enthalten in den Sammlungen:Publikationen School of Engineering

Dateien zu dieser Ressource:
Es gibt keine Dateien zu dieser Ressource.


Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt, soweit nicht anderweitig angezeigt.