Publication type: | Article in scientific journal |
Type of review: | Peer review (publication) |
Title: | Scheduling with time-dependent discrepancy times |
Authors: | Jaehn, Florian Sedding, Helmut |
et. al: | No |
DOI: | 10.1007/s10951-016-0472-2 |
Published in: | Journal of Scheduling |
Volume(Issue): | 19 |
Issue: | 6 |
Page(s): | 737 |
Pages to: | 757 |
Issue Date: | 2016 |
Publisher / Ed. Institution: | Springer |
ISSN: | 1094-6136 1099-1425 |
Language: | English |
Subjects: | Time-dependent scheduling; Nonmonotonic piecewise-linear processing time; Convex processing time; Single-machine scheduling; Assembly-line worker path minimization |
Subject (DDC): | 005: Computer programming, programs and data 658.5: Production management |
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. |
URI: | https://digitalcollection.zhaw.ch/handle/11475/18590 |
Fulltext version: | Published version |
License (according to publishing contract): | Licence according to publishing contract |
Departement: | School of Engineering |
Organisational Unit: | Institute of Data Analysis and Process Design (IDP) |
Appears in collections: | Publikationen School of Engineering |
Files in This Item:
There are no files associated with this item.
Show full item record
Jaehn, F., & Sedding, H. (2016). Scheduling with time-dependent discrepancy times. Journal of Scheduling, 19(6), 737–757. https://doi.org/10.1007/s10951-016-0472-2
Jaehn, F. and Sedding, H. (2016) ‘Scheduling with time-dependent discrepancy times’, Journal of Scheduling, 19(6), pp. 737–757. Available at: https://doi.org/10.1007/s10951-016-0472-2.
F. Jaehn and H. Sedding, “Scheduling with time-dependent discrepancy times,” Journal of Scheduling, vol. 19, no. 6, pp. 737–757, 2016, doi: 10.1007/s10951-016-0472-2.
JAEHN, Florian und Helmut SEDDING, 2016. Scheduling with time-dependent discrepancy times. Journal of Scheduling. 2016. Bd. 19, Nr. 6, S. 737–757. DOI 10.1007/s10951-016-0472-2
Jaehn, Florian, and Helmut Sedding. 2016. “Scheduling with Time-Dependent Discrepancy Times.” Journal of Scheduling 19 (6): 737–57. https://doi.org/10.1007/s10951-016-0472-2.
Jaehn, Florian, and Helmut Sedding. “Scheduling with Time-Dependent Discrepancy Times.” Journal of Scheduling, vol. 19, no. 6, 2016, pp. 737–57, https://doi.org/10.1007/s10951-016-0472-2.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.