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. In the literature portrayed models are mostly monotonic processing time functions. In this work, motivated by a moving assembly line planning problem, a non-monotonic processing time function with a convex, piecewise-linear V-shape is introduced to the field. Here, the processing time is minimum, equal to a job-specific basic processing time only if the job starts at a common ideal start time. It increases linearly if it starts earlier or later with slopes that can be asymmetric and job-specific. The objective is to sequence the jobs on a single machine and minimize the makespan. For this novel problem, this article provides a complexity characterization in several angles. It is shown that it is NP-complete already with the same slope for each job. On the more generic case of agreeable ratios of basic processing time and slopes, a fully polynomial time approximation scheme is devised. In the most generic case of job-specific slopes, four polynomial cases are identified, e.g., for all-zero basic processing times.

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: 02/01/2019

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