Scheduling tool changes and special jobs on a single machine to minimize makespan
AbstractThis 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%.
Download InfoIf you experience problems downloading a file, check if you have the proper application to view it first. In case of further problems read the IDEAS help page. Note that these files are not on the IDEAS site. Please be patient as the files may be large.
Bibliographic InfoArticle provided by Elsevier in its journal Omega.
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
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.:
- 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.
- 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.
If references are entirely missing, you can add them using this form.