Optimization Online


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

Helmut Sedding (helmut***at***sedding.net)

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 times 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.

Keywords: Single-machine scheduling; Time-dependent scheduling; Non-monotonic processing time; Piecewise-linear processing tim; Convex V-shaped processing time

Category 1: Applications -- OR and Management Sciences (Scheduling )

Category 2: Combinatorial Optimization (Approximation Algorithms )


Download: [PDF]

Entry Submitted: 02/01/2019
Entry Accepted: 02/01/2019
Entry Last Modified: 09/09/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society