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
Pages: 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
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 SizeFormat 
2020_Sedding_Scheduling-jobs_VoR.pdfArticle in Issue637.94 kBAdobe PDFView/Open
2020_Sedding_Scheduling-jobs.pdfOnline First707.01 kBAdobe PDFThumbnail
View/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.