Minimizing the total tardiness for the tool change scheduling problem on parallel machines

Abstract: This paper deals with the total tardiness minimization problem in a parallel machines manufacturing environment where tool change operations have to be scheduled along with jobs. The mentioned issue belongs to the family of scheduling problems under deterministic machine availability restrictions. A new model that considers the effects of the tool wear on the quality characteristics of the worked product is proposed. Since no mathematical programming-based approach has been developed by literature so far, two distinct mixed integer linear programming models, able to schedule jobs as well as tool change activities along the provided production horizon, have been devised. The former is an adaptation of a well-known model presented by the relevant literature for the single machine scheduling problem with tool changes. The latter has been specifically developed for the issue at hand. After a theoretical analysis aimed at revealing the differences between the proposed mathematical models in terms of computational complexity, an extensive experimental campaign has been fulfilled to assess performances of the proposed methods under the CPU time viewpoint. Obtained results have been statistically analyzed through a properly arranged ANOVA analysis.

How to cite this paper

 Costa, A., Cappadonna, F & Fichera, S. (2016). Minimizing the total tardiness for the tool change scheduling problem on parallel machines.International Journal of Industrial Engineering Computations , 7(2), 283-294.

Refrences

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(3), 784-790.

Akturk, M. S., Ghosh, J. B., & Kayan, R. K. (2007). Scheduling with tool changes to minimize total completion time under controllable machining conditions. Computers & operations research, 34(7), 2130-2146.

Biskup, D., Herrmann, J., & Gupta, J. N. (2008). Scheduling identical parallel machines to minimize total tardiness. International Journal of Production Economics, 115(1), 134-142.

Chen, J. S. (2008). Optimization models for the tool change scheduling problem. Omega, 36(5), 888-894.

Edis, E. B., Oguz, C., & Ozkarahan, I. (2013). Parallel machine scheduling with additional resources: Notation, classification, models and solution methods. European Journal of Operational Research, 230(3), 449-463.

Gray, A. E., Seidmann, A., & Stecke, K. E. (1993). A synthesis of decision models for tool management in automated manufacturing. Management science, 39(5), 549-567.

Hertz, A., Laporte, G., Mittaz, M., & Stecke, K. E. (1998). Heuristics for minimizing tool switches when scheduling part types on a flexible machine. IIE transactions, 30(8), 689-694.

Hwang, H. C., & Chang, S. Y. (1998). Parallel machines scheduling with machine shutdowns. Computers & Mathematics with Applications, 36(3), 21-31.

Hwang, H. C., Lee, K., & Chang, S. Y. (2005). The effect of machine availability on the worst-case performance of LPT. Discrete Applied Mathematics, 148(1), 49-61.

Lee, C. Y. (1996). Machine scheduling with an availability constraint. Journal of global optimization, 9(3-4), 395-416.

Lee, C. Y. (1991). Parallel machines scheduling with nonsimultaneous machine available time. Discrete Applied Mathematics, 30(1), 53-61

Lee, C. Y., Lei, L., & Pinedo, M. (1997). Current trends in deterministic scheduling. Annals of Operations Research, 70, 1-41.

Liao, C. J., Shyur, D. L., & Lin, C. H. (2005). Makespan minimization for two parallel machines with an availability constraint. European Journal of Operational Research, 160(2), 445-456.

Lin, C. H., & Liao, C. J. (2007). Makespan minimization for two parallel machines with an unavailable period on each machine. The International Journal of Advanced Manufacturing Technology, 33(9-10), 1024-1030.

Low, C., Ji, M., Hsu, C. J., & Su, C. T. (2010). Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance. Applied Mathematical Modelling, 34(2), 334-342.

Ma, Y., Chu, C., & Zuo, C. (2010). A survey of scheduling with deterministic machine availability constraints. Computers & Industrial Engineering, 58(2), 199-211.

Montgomery, D. C., (2007). Design and analysis of experiments. New York: Wiley.

Naderi, B., & Salmasi, N. (2012). Permutation flowshops in group scheduling with sequence-dependent setup times. European Journal of Industrial Engineering, 6(2), 177-198.

Pinedo, M. L. (2012). Scheduling: theory, algorithms, and systems. Springer Science & Business Media.
Kan, A. R. (1976). Machine scheduling problems: classification, complexity and computations. Springer Science & Business Media.

Schmidt, G. (2000). Scheduling with limited machine availability. European Journal of Operational Research, 121(1), 1-15.

Tang, C. S., & Denardo, E. V. (1988). Models arising from a flexible manufacturing machine, part I: minimization of the number of tool switches. Operations research, 36(5), 767-777.

Wang, J. B., & Wei, C. M. (2011). Parallel machine scheduling with a deteriorating maintenance activity and total absolute differences penalties. Applied Mathematics and Computation, 217(20), 8093-8099.

Xu, D., Sun, K., & Li, H. (2008). Parallel machine scheduling with almost periodic maintenance and non-preemptive jobs to minimize makespan. Computers & operations research, 35(4), 1344-1349.

Xu, D., Liu, M., Yin, Y., & Hao, J. (2013). Scheduling tool changes and special jobs on a single machine to minimize makespan. Omega, 41(2), 299-304.

Yang, D. L., Cheng, T. C. E., Yang, S. J., & Hsu, C. J. (2012). Unrelated parallel-machine scheduling with aging effects and multi-maintenance activities. Computers & Operations Research, 39(7), 1458-1464.

Zarook, Y., & Abedi, M. (2014). JIT-scheduling in unrelated parallel-machine environment with aging effect and multi-maintenance activities. International Journal of Services and Operations Management, 18(1), 99-113.