Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
https://doi.org/10.21256/zhaw-20553| Publikationstyp: | Beitrag in wissenschaftlicher Zeitschrift |
| Art der Begutachtung: | Peer review (Publikation) |
| Titel: | Scheduling jobs with a V-shaped time-dependent processing time |
| Autor/-in: | Sedding, Helmut A. |
| et. al: | No |
| DOI: | 10.1007/s10951-020-00665-4 10.21256/zhaw-20553 |
| Erschienen in: | Journal of Scheduling |
| Band(Heft): | 23 |
| Heft: | 6 |
| Seite(n): | 751 |
| Seiten bis: | 768 |
| Erscheinungsdatum: | 8-Sep-2020 |
| Verlag / Hrsg. Institution: | Springer |
| ISSN: | 1094-6136 1099-1425 |
| Sprache: | Englisch |
| Schlagwörter: | Single-machine scheduling; Time-dependent scheduling; Non-monotonic processing time; Piecewise-linear processing time; V-shaped processing time |
| Fachgebiet (DDC): | 005: Computerprogrammierung, Programme und Daten 500: Naturwissenschaften |
| Zusammenfassung: | In the field of time-dependent scheduling, a job’s processing time is specified by a function of its start time. While monotonic processing time functions are well-known in the literature, this paper introduces non-monotonic functions with a convex, piecewise-linear V-shape similar to the absolute value function. They are minimum at an ideal start time, which is the same for all given jobs. Then, the processing time equals the job’s basic processing time. Earlier or later, it increases linearly with slopes that can be asymmetric and job-specific. The objective is to sequence the given jobs on a single machine and minimize the makespan. This is motivated by production planning of moving car assembly lines, in particular, to sequence a worker’s assembly operations such that the time-dependent walking time to gather materials from the line-side is minimized. This paper characterizes the problem’s computational complexity in several angles. NP-hardness is observed even if the two slopes are the same for all jobs. A fully polynomial time approximation scheme is devised for the more generic case of agreeable ratios of basic processing time and slopes. In the most generic case with job-specific slopes, several polynomial cases are identified. |
| URI: | https://digitalcollection.zhaw.ch/handle/11475/20553 |
| Volltext Version: | Publizierte Version |
| Lizenz (gemäss Verlagsvertrag): | CC BY 4.0: Namensnennung 4.0 International |
| Departement: | School of Engineering |
| Organisationseinheit: | Institut für Datenanalyse und Prozessdesign (IDP) |
| Enthalten in den Sammlungen: | Publikationen School of Engineering |
Dateien zu dieser Ressource:
| Datei | Beschreibung | Größe | Format | |
|---|---|---|---|---|
| 2020_Sedding_Scheduling-jobs_VoR.pdf | Article in Issue | 637.94 kB | Adobe PDF | Öffnen/Anzeigen |
| 2020_Sedding_Scheduling-jobs.pdf | Online First | 707.01 kB | Adobe PDF |  Öffnen/Anzeigen |
Zur Langanzeige
Sedding, H. A. (2020). Scheduling jobs with a V-shaped time-dependent processing time. Journal of Scheduling, 23(6), 751–768. https://doi.org/10.1007/s10951-020-00665-4
Sedding, H.A. (2020) ‘Scheduling jobs with a V-shaped time-dependent processing time’, Journal of Scheduling, 23(6), pp. 751–768. Available at: https://doi.org/10.1007/s10951-020-00665-4.
H. A. Sedding, “Scheduling jobs with a V-shaped time-dependent processing time,” Journal of Scheduling, vol. 23, no. 6, pp. 751–768, Sep. 2020, doi: 10.1007/s10951-020-00665-4.
SEDDING, Helmut A., 2020. Scheduling jobs with a V-shaped time-dependent processing time. Journal of Scheduling. 8 September 2020. Bd. 23, Nr. 6, S. 751–768. DOI 10.1007/s10951-020-00665-4
Sedding, Helmut A. 2020. “Scheduling Jobs with a V-Shaped Time-Dependent Processing Time.” Journal of Scheduling 23 (6): 751–68. https://doi.org/10.1007/s10951-020-00665-4.
Sedding, Helmut A. “Scheduling Jobs with a V-Shaped Time-Dependent Processing Time.” Journal of Scheduling, vol. 23, no. 6, Sept. 2020, pp. 751–68, https://doi.org/10.1007/s10951-020-00665-4.
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt, soweit nicht anderweitig angezeigt.