Premium
Scheduling jobs with piecewise linear decreasing processing times
Author(s) -
Cheng T.C. Edwin,
Ding Qing,
Kovalyov Mikhail Y.,
Bachman Aleksander,
Janiak Adam
Publication year - 2003
Publication title -
naval research logistics (nrl)
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.665
H-Index - 68
eISSN - 1520-6750
pISSN - 0894-069X
DOI - 10.1002/nav.10073
Subject(s) - job shop scheduling , minification , heuristics , mathematical optimization , time complexity , computer science , scheduling (production processes) , piecewise linear function , piecewise , mathematical proof , computational complexity theory , algorithm , mathematics , schedule , mathematical analysis , geometry , operating system
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. © 2003 Wiley Periodicals, Inc. Naval Research Logistics 50: 531–554, 2003