Scheduling jobs with piecewise linear decreasing processing times
- 4 February 2003
- journal article
- research article
- Published by Wiley in Naval Research Logistics (NRL)
- Vol. 50 (6) , 531-554
Abstract
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, 2003Keywords
This publication has 18 references indexed in Scilit:
- Minimizing maximum lateness under linear deteriorationEuropean Journal of Operational Research, 2000
- Scheduling with time dependent processing times: Review and extensionsJournal of the Operational Research Society, 1999
- A note on single-processor scheduling with time-dependent execution timesOperations Research Letters, 1995
- Complexity of scheduling tasks with time-dependent execution timesInformation Processing Letters, 1993
- On permutation policies for the scheduling of deteriorating stochastic jobs on a single machineJournal of Applied Probability, 1993
- Single-machine scheduling of stochastic jobs subject to deterioration or delayNaval Research Logistics (NRL), 1992
- Scheduling Deteriorating Jobs on a Single ProcessorOperations Research, 1990
- Single facility scheduling with nonlinear processing timesComputers & Industrial Engineering, 1988
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey1979
- Scheduling independent tasks to reduce mean finishing timeCommunications of the ACM, 1974