Developing a new approximation algorithm with a tight worst-case for a single machine scheduling problem with tool change and special jobs

Document Type : Research Paper

Authors

Abstract

Scheduling problems with tool changes considerations have been investigated extensively in the last two decades. Tool change activities applied in flexible maintenance activities where the tools may be changed at any time of their lifespan. Also, to determining the quality of the final product, considering the quality of the tools as a production condition items is inevitable. In this paper, the classical single machine scheduling problem with tool change is examined. In this problem, two sets of jobs, namely special jobs and normal jobs are considered. Special jobs must be processed during a certain time after the tool change. This problem has been studied in the literature. Mathematical programming models used to solve scheduling problems with small size and medium size. For scheduling problems with large size, six algorithms based on Bin Packing problem presented and focused on their performance. In this paper, we present a new algorithm for solving large size scheduling problems. The computational results show that the proposed algorithm performance at the half of instance problems is better than four algorithms of literature. In addition, in the other instance it is better than all developed literature algorithms.

Keywords

Main Subjects

References

[1]     Schmidt, G., (2000). “Scheduling with limited machine availability”, European Journal of OperationalResearch, 121: 1-15
[2]     Ma, Y., Chu, C., Zuo, C., (2010). “A survey of scheduling with deterministic machine availability constraints”, Computers and Industrial Engineering, 58: 199-211.
[3]     Akturk, M.S., Ghosh, J.B., Gunes, E.D., (2003(. “Scheduling with tool changes to minimize total completion time: a study of heuristics and their performance”, Naval Research Logistics, 50: 15–30.
[4]     Akturk, M.S., Ghosh, J.B., Kayan, R.K., (2007). “Scheduling with tool changes to minimize total completion time under controllable machining conditions”, Computers and Operations Research, 37: 2130–2146.
[5]     Akturk, M.S., Ghosh, J.B. Gunes, E.D., (2004). “Scheduling with tool changes to minimize total completion time: basic results and SPT performance”, European Journal of Operational Research, 157: 784–790.
[6]     Chen, J.S., (2008). “Optimization models for the tool change scheduling problem”, Omega, 36: 888-894.
[7]     Qi, X., Chen, T., Tu, F., (1999). “Scheduling the Maintenance on a Single Machine”, the Journal of the Operational Research Society, 50: 1071-1078.
[8]     Xu, D., Yin, Y., Li, H., (2010). “Scheduling jobs under increasing linear machine maintenance time”, Journal of scheduling, 13: 443-449.
[9]     Shi, X., Xu, D., (2014). “Best Possible Approximation Algorithms for Single Machine Scheduling with Increasing Linear Maintenance Durations”, The Scientific World Journal, 2014: 547-573.
[10] Xu, D., Liu, M., Yin, Y., Hao, J., (2013). “Scheduling tool changes and special jobs on a single machine to minimize makespan”, Omega, 41: 299–304.
[11] ] Costa, A., Cappadonna, F.A., Fichera, S., (2016). “Minimizing the total completion time on a parallel machine system with tool changes”, Computers and Industrial Engineering, 91: 209-301.
[12] Yazdani, M., Khalili, S.M., Jolai, F., (2016). “A parallel machine scheduling problem with two-agent and tool change activities: an efficient hybrid metaheuristic algorithm”, International Journal of Computer Integrated Manufacturing, 29(10): 1075-1088.
[13] ] He, J., Li, Q., Xu, D., (2016). “Scheduling two parallel machines with machine-dependent availabilities”, Computers and Operations Research, 72: 31-42.
[14] Graham, R.L., Lawler, Lenstra, E.L., Rinnooy, J.K., Kan, A.H.G., (1979). “Optimization and approximation in deterministic sequencing and scheduling: a survey”, Annals of Discrete Mathematics, 5: 287–326.
[15] Coffman, E.G., Garey, M.R., Johnson, D.S., (1997). Approximation algorithms for bin packing: a survey, In Approximation algorithms for NP-hard problem, edited by Hochbaum, D.S., Boston: PWS Publishing Company.
Journal of Industrial Engineering Research in Production Systems
Volume 4, Issue 9
Special Issue: 11th & 12th International Conference on Industrial Engineering
March 2017
Pages 297-305

Files

Share

How to cite

Statistics