Minimizing Total Weighted Tardiness in Identical Parallel Machine with Sequence Dependent Setup Time Using Genetic Algorithm

Authors

  • Sivarhubhen Sivapragasam Faculty of Engineering and Technology, Multimedia University, Melaka, Malaysia.
  • Yasothei Suppiah Faculty of Engineering and Technology, Multimedia University, Melaka, Malaysia.

Keywords:

Dispatching Heuristic, Genetic Algorithm, Parallel Machine, Scheduling, Tardiness,

Abstract

This paper considers a scheduling problem in an identical parallel machine environment to minimize total weighted tardiness with the consideration of sequence dependent setup times. As the scheduling problem is proven to be NP-hard, a genetic algorithm is developed with the aim of providing good solution in a reasonable time to the scheduling problem. Computational experiments were performed to study the effectiveness of the genetic algorithm solution quality and the CPU time. Various dispatch heuristics were developed to provide initial solutions to the genetic algorithm besides comparing their solution quality with the genetic algorithm’s solution. The developed genetic algorithm has the capability to provide good results and good improvement compared to all the developed dispatching heuristics.

References

Allahverdi, A., Ng, C.T., Cheng, T.C.E. and Kovalyov Mikhail, Y., “A Survey of Scheduling Problems with Setup Times or Costs”, European Journal of Operational Research, vol. 187, 2008, pp. 985-1032.

Behnamian, J., Ghomi, F. and Zandieh, “M. A Multi-Phase Covering Pareto-Optimal Front Method to Multi-Objective Scheduling in a Realistic Hybrid Flowshop using a Hybrid Metaheuristic”,International Journal of Production Research, vol. 48, 2009, pp.4949–4976.

Biskup, D., Herrmann, J. and Gupta, J.N.D., “Scheduling Identical Parallel Machines to Minimize Total Tardiness”, International Journal of Production Economics, vol. 115, no. 1, 2008, pp. 134-142.

Chen, T., Rajendran, C. and Wu, C. W. “Advanced Dispatching Rules

for Large-Scale Manufacturing Systems”, International Journal of Advanced Manufacturing Technology, 2013. Doi 10.1007/s00170-013-4843-y.

Conner, G., “10 questions”, Manufacturing Engineering Magazine, 2009.

Demirel, T., Özkır, V., Demirel, N. C. and Taşdelen, B., “A Genetic Algorithm Approach for Minimizing Total Tardiness in Parallel Machine Scheduling Problems”,Proceedings of the World Congress on Engineering London, U.K, Vol II, pp. 6 – 8, July 2011.

Dunstall, S. and Wirth, A., “Heuristic Methods for the Identical Parallel Machine Flowtime Problem with Set-Up Times”, Computers and Operations Research, vol. 32, no. 9, 2005, pp. 2479-2491.

Holland J.H., “Adaptation in Natural and Artificial Systems”, Ann Arbor: University of Michigan Press, 1975.

Huegler, P.A. and Vasko, F.J., “A Performance Comparison of Heuristics for the Total Weighted Tardiness Problem”, Computers and Industrial Engineering, vol. 32, no. 4, 1997, pp. 753-767.

Joo, C.M. and Kim, B.S. “Hybrid Genetic Algorithms with Dispatching Rules for Unrelated Parallel Machine Scheduling with Setup Time and Production Availability”, Computers and Industrial Engineering, vol. 85, 2015, pp. 102-109.

Krajewski, L.J., King, B.E., Ritzman, L.P. and Wong, D.S., “Kaban, MRP and Shaping the Manufacturing Environment”, Management Science, vol. 33, 1987, pp. 39-57.

Lin, Y. K., Pfund, M. E. and Fowler, J. W., “Heuristics for Minimizing Regular Performance Measures in Unrelated Parallel Machine Scheduling Problem”, Computers & Operations Research, vol. 38, no. 6, 2011, pp. 901–916.

Malve S. and Uzsoy, R., “A Genetic Algorithm for Minimizing Maximum Lateness on Parallel Identical Batch Processing Machines with Dynamic Job Arrivals and Incompatible Job Families”,Computers and Operations Research, vol. 34, 2007, pp. 3016-3028.

Morton, T. E. and Pentico, D. W., “Heuristic Scheduling Systems: With Applications to Production Systems and Project Management”, John Wiley and Sons, 1993.

Pfund, M., Fowler, J. W., Gadkari, A. and Chen, Y., “Scheduling Jobs on Parallel Machines with Setup Times and Ready Times”, Computers and Industrial Engineering, vol. 54, 2008, pp. 764-782.

Pinedo, M., “Scheduling: Theory, Algorithms and Systems”,Englewood Cliffs, NJ: Prentice Hall, 1995.

Pinedo M., “Scheduling Theory, Algorithms and Systems”, Edition 2. New Jersey : Prentice Hall, 2002.

Roshanaei, V., Seyyed Esfehani, M.M. and Zandieh, M., “Integrating Non-Preemptive Open Shops Scheduling with Sequence-Dependent Setup Times using Advanced Metaheuristics”, Expert Systems with Applications, vol. 37, no. 1, 2010, pp. 259-266.

Schaller, J.E., “Minimizing Total Tardiness for Scheduling Identical

Parallel Machines with Family Setups”, Computers and IndustrialEngineering, vol. 72, 2014, pp. 274-281.

Vepsalainen, A. P. J. and Morton, T. E., “Priority Rules for Job Shops with Weighted Tardiness Cost”, Management Science, vol. 33, no. 8,1987, pp. 1035-1047.

Volgenant, A. and Teerhuis, E., “Improved Heuristics for the N-Job Single-Machine Weighted Tardiness Problem”, Computers and Operations Research, vol. 26, no. 1, 1999, pp. 35-44.

Zandieh, M., Fatemi,Ghomi, S, M, T. and Moattar Husseini, S.M., “An Immune Algorithm Approach to Hybrid Flow Shops Scheduling with

Sequence-Dependent Setup Times”, Applied Mathematics and Computation, vol. 180, no. 1, 2006, pp. 111-127.

Zhou, H., Cheung, W. and Leung, L.C., “Minimizing Weighted

Tardiness of Job-Shop Scheduling using a Hybrid Genetic Algorithm”, European Journal of Operational Research, vol. 194, no.

, 2009, pp. 637-649.

Zhu, X. and Wilhelm, W. E., “Scheduling and Lot Sizing with

Sequence-Dependent Setup; A Literature Review”, IIE Transactions, vol. 38, 2006, pp. 987-1007

Downloads

Published

2017-03-15

How to Cite

Sivapragasam, S., & Suppiah, Y. (2017). Minimizing Total Weighted Tardiness in Identical Parallel Machine with Sequence Dependent Setup Time Using Genetic Algorithm. Journal of Telecommunication, Electronic and Computer Engineering (JTEC), 9(1-4), 89–93. Retrieved from https://jtec.utem.edu.my/jtec/article/view/1786