Scheduling Jobs with Piecewise Linear Decreasing Processing Times

Edwin Tai Chiu Cheng, Qing Ding, Mikhail Y. Kovalyov, Aleksander Bachman, Adam Janiak

Research output: Journal article publicationJournal articleAcademic researchpeer-review

56 Citations (Scopus)


We study the problems of scheduling a set of nonpreemptive jobs on a single or multiple machines without idle times where the processing time of a job is a piecewise linear nonincreasing function of its start time. The objectives are the minimization of makespan and minimization of total job completion time. The single machine problems are proved to be NP-hard, and some properties of their optimal solutions are established. A pseudopolynomial time algorithm is constructed for makespan minimization. Several heuristics are derived for both total completion time and makespan minimization. Computational experiments are conducted to evaluate their efficiency. NP-hardness proofs and polynomial time algorithms are presented for some special cases of the parallel machine problems.
Original languageEnglish
Pages (from-to)531-554
Number of pages24
JournalNaval Research Logistics
Issue number6
Publication statusPublished - 1 Sept 2003


  • Computational complexity
  • Machine scheduling
  • Start time dependent processing times

ASJC Scopus subject areas

  • Modelling and Simulation
  • Ocean Engineering
  • Management Science and Operations Research


Dive into the research topics of 'Scheduling Jobs with Piecewise Linear Decreasing Processing Times'. Together they form a unique fingerprint.

Cite this