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

## 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

## How to Cite

*Journal of Telecommunication, Electronic and Computer Engineering (JTEC)*,

*9*(1-4), 89–93. Retrieved from https://jtec.utem.edu.my/jtec/article/view/1786

## Issue

## Section

## License

**TRANSFER OF COPYRIGHT AGREEMENT**

The manuscript is herewith submitted for publication in the Journal of Telecommunication, Electronic and Computer Engineering (JTEC). It has not been published before, and it is not under consideration for publication in any other journals. It contains no material that is scandalous, obscene, libelous or otherwise contrary to law. When the manuscript is accepted for publication, I, as the author, hereby agree to transfer to JTEC, all rights including those pertaining to electronic forms and transmissions, under existing copyright laws, except for the following, which the author(s) specifically retain(s):

- All proprietary right other than copyright, such as patent rights
- The right to make further copies of all or part of the published article for my use in classroom teaching
- The right to reuse all or part of this manuscript in a compilation of my own works or in a textbook of which I am the author; and
- The right to make copies of the published work for internal distribution within the institution that employs me

I agree that copies made under these circumstances will continue to carry the copyright notice that appears in the original published work. I agree to inform my co-authors, if any, of the above terms. I certify that I have obtained written permission for the use of text, tables, and/or illustrations from any copyrighted source(s), and I agree to supply such written permission(s) to JTEC upon request.