Abstract
We consider job rescheduling problems where rescheduling is required in response to newly arriving jobs. To reduce the negative impacts of disruptions to the original schedule, the processing times of the newly arriving jobs can be reduced at a cost, which we call a time compression cost. The objective of the problem is to minimize total cost after rescheduling, which includes schedule disruption costs, time compression related costs, and a cost that depends on a traditional measure of schedule efficiency. We separately consider two different measures of schedule efficiency: total completion time and weighted tardiness, and present polynomial time algorithms for the total completion time case. For the weighted tardiness cost efficiency measure, we provide a heuristic based on very large scale neighborhood (VLSN) search.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Norbis MI, Smith JM (1988) A multi objective, multi-level heuristic for dynamic resource constrained scheduling problems. Eur J Oper Res33:30–41
Bean JC, Birge JR,Mittenthal J, Noon CE (1991) Match-up scheduling with multiple resources,release dates and disruptions. Oper Res 39:470–483
Wu SD, Storer RH, ChangPC (1993) One-machine rescheduling heuristics with efficiency and stability as criteria. Comp Oper Res 20:1–14
Leon, VJ, Wu SD, StorerRH (1994) Robustness measures and robust scheduling for job shops. IIE Trans26:32–43
Unal AT, Uzsoy R, Kiran AS (1997) Rescheduling on a single machine with part-type dependent setup times and deadlines. Ann Oper Res 70:93–113
Hall NG, Potts CN (2004) Rescheduling for new orders. Oper Res 52(3):440–453
Vickson RG (1980) Choosing the job sequence and processing times to minimize total processing plus flow cost on a single machine. Oper Res 28(5):1115–1167
Du J, Leung JY-T (1990) Minimizing total tardiness on one machine is NP-hard. Math Oper Res 15:483–495
Ahuja RK, Ergun O, Orlin JB, Punnen AP (2002) A survey of very large-scale neighborhood search techniques. Discret Appl Math 123:75–102
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Yang, B. Single machine rescheduling with new jobs arrivals and processing time compression. Int J Adv Manuf Technol 34, 378–384 (2007). https://doi.org/10.1007/s00170-006-0590-7
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-006-0590-7