Single-machine scheduling to minimize total absolute differences in waiting times with deteriorating jobs
Authors:
- 1 April 2011
- journal article
- Published by Taylor & Francis in Journal of the Operational Research Society
- Vol. 62 (4) , 768-775
Abstract
In this paper we consider a single-machine scheduling problem with simple linear deterioration. By simple linear deterioration, we mean that the processing time of a job is a simple linear function of its execution starting time and its deterioration rate. The objective is to find a schedule that minimizes total absolute differences in waiting times. We show that the optimal schedule is V-shaped: jobs are arranged in descending order of their deterioration rates if they are placed before the job with the smallest deterioration rate, but in ascending order of their deterioration rates if placed after it. We prove other several properties of an optimal schedule, and introduce two efficient heuristic algorithms that are tested against a lower bound. We also provide computational results to evaluate the performance of the heuristic algorithms.Keywords
This publication has 21 references indexed in Scilit:
- A two-machine flowshop makespan scheduling problem with deteriorating jobsComputers & Industrial Engineering, 2008
- Scheduling deteriorating jobs on a single machine with release timesComputers & Industrial Engineering, 2008
- Multi-machine scheduling with deteriorating jobs and scheduled maintenanceApplied Mathematical Modelling, 2008
- Due-date assignment and parallel-machine scheduling with deteriorating jobsJournal of the Operational Research Society, 2007
- Flow shop scheduling problems with deteriorating jobs under dominating machinesJournal of the Operational Research Society, 2006
- Flow shop scheduling with deteriorating jobs under dominating machinesOmega, 2005
- Single machine due‐date scheduling of jobs with decreasing start‐time dependent processing timesInternational Transactions in Operational Research, 2005
- Due-date assignment and single machine scheduling with deteriorating jobsJournal of the Operational Research Society, 2004
- Scheduling with time dependent processing times: Review and extensionsJournal of the Operational Research Society, 1999
- Scheduling jobs under simple linear deteriorationComputers & Operations Research, 1994