A Linear Programming Approach for Parallel Cell Scheduling with Sequence-Dependent Setup Times

Tuğba Yıldız, Besim Türker Özalp, İlker Küçükoğlu, Alkın Yurtkuran, Nursel Öztürk

Industrial Engineering Department, Faculty of Engineering, Uludag University, Bursa, Turkey.

DOI: 10.4236/ajor.2014.43015                

Abstract

In this study, we consider the problem of scheduling a set of jobs with sequence-dependent setup times on a set of parallel production cells. The objective of this study is to minimize the total completion time. We note that total customer demands for each type should be satisfied, and total required production time in each cell cannot exceed the capacity of the cell. This problem is formulated as an integer programming model and an interface is designed to provide integrity between data and software. Mathematical model is tested by both randomly generated data set and real-world data set from a factory that produce automotive components. As a result of this study, the solution which gives the best alternative production schedule is obtained.

Keywords

Production Scheduling, Total Completion Time, Sequence Dependent Setup Times

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Stoop, P. P. M. and Wiers, V.C.S. (1996) The Complexity of Scheduling in Practice. International Journal of Operations and Production Management, 16, 37-53. http://dx.doi.org/10.1108/01443579610130682
[2]	Allahverdi, A., Ng, C.T., Cheng, T.C.E. and Kovalyov, M.Y. (2008) Survey of Scheduling Problems with Setup Times or Costs. European Journal of Operational Research, 187, 985-1032. http://dx.doi.org/10.1016/j.ejor.2006.06.060
[3]	Yang, W.H. and Liao, C.J. (1999) Survey of Scheduling Research Involving Setup Times. International Journal of Systems Science, 30, 143-155. http://dx.doi.org/10.1080/002077299292498
[4]	Cheng, T.C.E., Gupta, J.N.D. and Wang, G. (2000) A Review of Flowshop Scheduling Research with Setup Times. Production and Operations Management, 9, 262-282. http://dx.doi.org/10.1111/j.1937-5956.2000.tb00137.x
[5]	Potts, C.N. and Kovalyov, M.Y. (2000) Scheduling with Batching: A Review. European Journal of Operational Research, 120, 228-349. http://dx.doi.org/10.1016/S0377-2217(99)00153-8
[6]	Bigras, L.P., Gamache, M. and Savard, G. (2008) The Time-Dependent Travelling Salesman Problem and Single Machine Scheduling Problems with Sequence Dependent Setup Times. Discrete Optimization, 5, 685-699. http://dx.doi.org/10.1016/j.disopt.2008.04.001
[7]	Ng, C.T., Cheng, T.C.E. and Kovalyov, M.Y. (2003) Batch Scheduling with Controllable Setup and Processing Times to Minimize Total Completion Time. Journal of the Operational Research Society, 54, 499-506. http://dx.doi.org/10.1057/palgrave.jors.2601537
[8]	Gagne, C., Price, W.L. and Gravel, M. (2002) Comparing an ACO Algorithm with Other Heuristics for the Single Machine Scheduling Problem with Sequence-Dependent Setup Times. Journal of the Operational Research Society, 53, 895-906. http://dx.doi.org/10.1057/palgrave.jors.2601390
[9]	Haung, S., Cai, L. and Zhang, X. (2009) Parallel Dedicated Machine Scheduling Problem with Sequence-Dependent Setups and a Single Server. Computers and Industrial Engineering, 58, 165-174. http://dx.doi.org/10.1016/j.cie.2009.10.003
[10]	Tahar, D.N., Yalaoui, F., Chu, C. and Amodeo, L. (2005) A Linear Programming Approach for Identical Parallel Machine Scheduling with Job Splitting and Sequence-Dependent Setup Times. International Journal of Production Economics, 99, 63-73. http://dx.doi.org/10.1016/j.ijpe.2004.12.007
[11]	Gacias, B., Artigues, C. and Lopez, P. (2010) Parallel Machine Scheduling with Precedence Constraints and Setup Times. Computers and Operations Research, 37, 2141-2151. http://dx.doi.org/10.1016/j.cor.2010.03.003