A New Crossover Operator for Single Machine Total Weighted Tardiness Problem with Sequence Dependent Setup Times

Year 2012, Volume: 25 Issue: 1, 127 - 136, 24.01.2012

Gökhan Kırlık Zuhal Kartal Servet Hasgul

Abstract

The single machine total weighted tardiness problem with sequence dependent setup times is a challenging and heavily studied problem. This problem is NP-hard, so several heuristics have been proposed in the literature so far. One of them is the genetic algorithm. The genetic algorithm is both powerful solution technique and applicable to wide range of different problem types, although its performance is heavily parameter and operator dependent. It is seen in literature that the well-conducted and adapted genetic algorithm operators and parameters increase the solution quality. In this study, a new crossover operator is proposed for the single machine with sequence dependent setup times problem to minimize the total weighted tardiness. The proposed crossover operator improves the relative positions by using apparent tardiness cost with setups (ATCS) heuristic while preserving the absolute positions. These are the two main aspects of the permutation type crossover operators for scheduling problems. The performance of the proposed crossover operator is tested by comparing it with partially mapped crossover (PMX) in different test cases using benchmark instances from literature. It is shown that the proposed ATCS based crossover operator gives better results than PMX in all test problems.

Key Words: Weighted tardiness scheduling, Sequence dependent setups, Genetic algorithm, Crossover operator

 

 

Keywords

Key Words: Weighted tardiness scheduling, Sequence dependent setups, Genetic algorithm, Crossover operator

References

• Panwalkar S. S., Dudek R. A., Smith M. L., “Sequencing research and the industrial scheduling problem” Symposium on the Theory of Scheduling and its Applications, p. 29В––38, New York, USA, Springer (1973).
• Allahverdi A., Ng C. T., Cheng T., Kovalyov M., “A survey of scheduling problems with setup times Operational Research, 187:985–1032, (2008). Journal of [3] Eugene L. Lawler., “A pseudopolynomial
• algorithm for sequencing jobs to minimize total
• tardiness” Annals of Discrete Mathematics, 1:331–342, (1977).
• Lenstra J. K., Hendrik A., Kan G. R., Brucker P., “Complexity of machine scheduling problems”, Annals of Discrete Mathematics, 1:343–362, (1977).
• Abdul-Razaq T. S., Potts C., Van Wassenhove L., “A survey of algorithms for the single machine total weighted tardiness scheduling problems”, Discrete Applied Mathematics, 26:235–253, (1990).
• Pott C. N., Van Wassenhove L., “A branch and bound algorithm for the total weighted tardiness problem”, Operations Research, 26:363–377, (1985).
• Pott C. N., Van Wassenhove L., “Dynamic programming and decomposition approaches for the single machine total tardiness problem”, European Journal of Operational Research, 32:405–414, (1987).
• Vepsalainen A., Morton T. E., “Priority rules for job shops with weighted tardiness cost”, Management Science, 33(8): 1035–1047, (1987).
• Hoon L. Y., Bhaskaram K., Pinedo M., “A heuristic to minimize the total weighted tardiness with Transactions, 29:45–52, (1997). setups”, IIE
• Potts C. N. Van Wassenhove L., “Single machine tardiness Transactions, 23(4):346–354, (1991). heuristics”, IIE
• Cicirello V. A., Smith S. F., “Enhancing stochastic search performance by value-biased randomization Heuristics, 11:5–34, (2005). Journal of
• Liao C., Juan H., “An ant colony optimization for single sequence dependent setups”, Computers & Operations Research, 34:1899–1909, (2007).
• Anghinolfi D., Paolucci M., “A new ant colony optimization approach for the single machine total weighted tardiness scheduling problem” International Journal of Operations Research, 5(1):44–60, (2008).
• Lin S., Ying K., “Solving single-machine total weighted tardiness problems with sequence- dependent setup times by meta-heuristics”, International Manufacturing (2007). of Advanced 34:1183–1190,
• Cicirello V., “Non-wrapping order crossover: an order preserving crossover operator that respects absolute position” In Proceedings of the 8th annual conference on Genetic and evolutionary computation, p. 1125–1132, Seattle, Washington, USA, (2006).
• Valente J., Rui A. F. S., “Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups”, Computers & Operations Research, 35(7):2388–2405, (2008).
• Anghinolfi D., Paolucci M., “A new discrete particle swarm optimization approach for the single scheduling problem with sequence dependent setup times”, European Journal of Operations Research, 193:73–85, (2009). tardiness
• Tasgetiren M., Pan Q., Liang Y., “A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times”, Computers & Operations Research, 36(6):1900–1915, (2009).
• Gen M., Cheng R., “Genetic Algorithms and Engineering Optimization”, John Wiley Sons Inc., NY, USA, (2000).
• Goldberg D. E.,. Genetic Algorithms in Search, Optimization and Machine Learning. Addison- Wesley, Reading, MA, USA, (1989).
• Holland J. H., “Adaptation in Natural and Artificial Systems”, University of Michigan Press, Ann Arbor, MI, USA, (1975).
• Davis L., “Applying adaptive algorithms to epistatic domains”, In Proceedings of the 9th international joint conference on Artificial intelligence, p. 162–164, Los Angeles, California, USA,. Morgan Kaufmann Publishers Inc, (1985).
• Michalewicz Z., “Genetic Algorithms + Data Structures = Evolution Programs”, Springer, Berlin, 2nd edition edition, (1994).
• Goldberg D. E., Lingle R., “Alleles, loci, and the traveling salesman problem”, Proceedings of the First International Conference on Genetic Algorithms and Their Applications, p. 154–159, Mahwah, Associates, Publishers 1985. Lawrence Erlbaum
• Cheng R., Gen M., “Evolution program for resource problem”, In Proceedings of the 1st Conference on Evolutionary Computation, p. 736–741, Mahwah, NJ, USA, (1994). project scheduling
• Brindle A., “Genetic Algorithms for Function Optimization”, PhD thesis, University of Alberta, Edmonton, Canada, (1981).