Scheduling tool changes and special jobs on a single machine to minimize makespan
This paper considers a variation of the classical single machine scheduling problem with tool changes. In the variation, two sets of jobs, namely special jobs and normal jobs, are considered. By special jobs, we mean that each special job must be processed within the first prefixed time units of a tool life. To solve the scheduling problem with small size and moderate size, we propose two mathematical programming models. To solve the scheduling problem with large size, we propose three sets of algorithms and focus on the performance of six algorithms based on the studies of a new bin packing problem. Worst-case analysis is conducted. Numerical experiment shows that each of the six algorithms can solve instances with up to 5000 jobs in about 0.5s with an average relative error less than 4%.
Volume (Year): 41 (2013)
Issue (Month): 2 ()
|Contact details of provider:|| Web page: http://www.elsevier.com/wps/find/journaldescription.cws_home/375/description#description|
|Order Information:|| Postal: http://www.elsevier.com/wps/find/supportfaq.cws_home/regional|
Please report citation or reference errors to , or , if you are the registered author of the cited work, log in to your RePEc Author Service profile, click on "citations" and make appropriate adjustments.:
- Akturk, M. Selim & Ghosh, Jay B. & Gunes, Evrim D., 2004. "Scheduling with tool changes to minimize total completion time: Basic results and SPT performance," European Journal of Operational Research, Elsevier, vol. 157(3), pages 784-790, September.
- Chen, Jen-Shiang, 2008. "Optimization models for the tool change scheduling problem," Omega, Elsevier, vol. 36(5), pages 888-894, October.
- Sun, Kaibiao & Li, Hongxing, 2010. "Scheduling problems with multiple maintenance activities and non-preemptive jobs on two identical parallel machines," International Journal of Production Economics, Elsevier, vol. 124(1), pages 151-158, March.
When requesting a correction, please mention this item's handle: RePEc:eee:jomega:v:41:y:2013:i:2:p:299-304. See general information about how to correct material in RePEc.
If references are entirely missing, you can add them using this form.