Scheduling jobs with a V-shaped time-dependent processing time

Sedding, Helmut A.

doi:10.1007/s10951-020-00665-4

Please use this identifier to cite or link to this item: https://doi.org/10.21256/zhaw-20553

Publication type:	Article in scientific journal
Type of review:	Peer review (publication)
Title:	Scheduling jobs with a V-shaped time-dependent processing time
Authors:	Sedding, Helmut A.
et. al:	No
DOI:	10.1007/s10951-020-00665-4 10.21256/zhaw-20553
Published in:	Journal of Scheduling
Volume(Issue):	23
Issue:	6
Page(s):	751
Pages to:	768
Issue Date:	8-Sep-2020
Publisher / Ed. Institution:	Springer
ISSN:	1094-6136 1099-1425
Language:	English
Subjects:	Single-machine scheduling; Time-dependent scheduling; Non-monotonic processing time; Piecewise-linear processing time; V-shaped processing time
Subject (DDC):	005: Computer programming, programs and data 500: Natural sciences
Abstract:	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
Fulltext version:	Published version
License (according to publishing contract):	CC BY 4.0: Attribution 4.0 International
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:

File	Description	Size	Format
2020_Sedding_Scheduling-jobs_VoR.pdf	Article in Issue	637.94 kB	Adobe PDF	View/Open
2020_Sedding_Scheduling-jobs.pdf	Online First	707.01 kB	Adobe PDF	View/Open

Show full item record

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.