Minimizing total weighted tardiness for the single machine scheduling problem with dependent setup time and precedence constraints


Hamidreza Haddad and Mohammadreza Nematollahi


This paper tackles the single machine scheduling problem with dependent setup time and precedence constraints. The primary objective of this paper is minimization of total weighted tardiness. Since the complexity of the resulted problem is NP-hard we use metaheuristics method to solve the resulted model. The proposed model of this paper uses genetic algorithm to solve the problem in reasonable amount of time. Because of high sensitivity of GA to its initial values of parameters, a Taguchi approach is presented to calibrate its parameters. Computational experiments validate the effectiveness and capability of proposed method.


DOI: j.msl.2011.12.020

Keywords: Scheduling ,Single machine ,Total weighted tardiness ,Genetic algorithm ,Precedence constraints

How to cite this paper:

Haddad, H & Nematollahi, M. (2012). Minimizing total weighted tardiness for the single machine scheduling problem with dependent setup time and precedence constraints.Management Science Letters, 2(2), 517-524.


References

Allahverdi, A., Gupta, J.N.D., & Aldowaisan, T.A. (1999). A review of scheduling research involving setup considerations. Omega, 27, 219-239.

Almeida, MT., & Centeno, M. (1998). A composite heuristic for the single machine early–tardy job scheduling problem. Computers & Operations Research, 25, 625–35.

Anghinolfi, D., & Paolucci, M. (2009). A new discrete particle swarm optimization approach for the single-machine total weighted tardiness scheduling problem with sequence-dependent setup times. European Journal of Operational Research, 193, 73–85

Aarts, E., & Lenstra, J.K. (1997). Local Search in Combinatorial Optimization. New York:John Wiley & Sons.

Bahalke, U., Yolmeh, A.M., & Shahanaghi, K. (2010). Meta-heuristics to solve single-machine scheduling problem with sequence-dependent setup time and deteriorating jobs. International Journal of Advanced Manufacturing Technology, 50, 749-759.

Cheng, T.C.E., Lazarev, A., & Gafarov, E.R. (2009). A hybrid algorithm for the single-machine total tardiness problem. Computers & Operations Research, 36, 308 – 315.

Cicirello, V.A. (2003). Weighted tardiness scheduling with sequence-dependent setups. New York: A benchmark library. Technical Report, Intelligent Coordination and Logistics Laboratory, Robotics Institute, Carnegie Mellon University.

Der Chou, F. (2009). An experienced learning genetic algorithm to solve the single machine total weighted tardiness scheduling problem. Expert Systems with Applications, 36, 3857–3865.

Feo, T.A., Sarathy, K., & McGahan, J. (1996). A GRASP for single machine scheduling with sequence dependent setup costs and linear delay penalties. Computers & Operations Research, 23, 881–895.

Franca, P.M., Mendes, A., & Moscato, P. (2001). A mimetic algorithm for the total tardiness single machine scheduling problem. European Journal of Operational Research, 132, 224–42.

Holsenback, J.E., Russell, R.M., Markland, RE., & Philipoom, P.R. (1999). An improved heuristic for the single-machine.weighted-tardiness problem, Omega, 27, 485–495.

Jolai, F., Rabbani, M., Amalnick, S., Dabaghi, A., Dehghan, M., & YazadnParast, M. (2007). Genetic algorithm for bi-criteria single machine scheduling problem of minimizing maximum earliness and number of tardy jobs. Applied Mathematics and Computation, 194, 552–560

Khorshidian, H., Javadian, N., Zandieh, M., Rezaeian, J., & Rahmani, K. (2011). A genetic algorithm for JIT single machine scheduling with preemption and machine idle time. Expert Systems with Applications, 38, 7911–7918.

Lawler, E.L. (1997). A pseudo polynomial algorithm for sequencing jobs to minimize total tardiness. Annals of Discrete Mathematics, 1, 331–342.

Lee, Y.H., Bhaskaram, K., & Pinedo, M. (1997). A heuristic to minimize the total weighted tardiness with sequence-dependent setups. IIE Transactions, 29, 45–52.

Xiaochuan, L., & Feng, Ch. (2006). A branch and bound algorithm of the single machine schedule with sequence dependent setup times for minimizing total tardiness. Applied Mathematics and Computation, 183, 575–588.

M’Hallah, R. (2007). Minimizing total earliness and tardiness on a single machine using a hybrid heuristic. Computers & Operations Research, 34, 3126 – 3142.

Sen, T., Sulek, J.M., & Dileepan, P. (2003). Static scheduling research to minimize weighted and unweighted tardiness: a state-of-the-art survey. International Journal of Production Economics, 83, 1–12.

Tan, K.C., Narasimhan, R., Rubin, P.A., & Ragatz, G.L. (2000). A comparison of four methods for minimizing total tardiness on a single processor with sequence dependent setup times. Omega-International Journal of Management Science, 28, 313–326.

Tasgetirena, MF., Quan-Ke, P., & Yun-Chia, L. (2009). A discrete differential evolution algorithm for the single machine total weighted tardiness problem with sequence dependent setup times. Computers & Operations Research, 36, 1900-1915.

Valente, J.M.S., & Alves, R. (2008). Beam search algorithms for the single machine total weighted tardiness scheduling problem with sequence-dependent setups. Computers & Operations Research, 35, 2388–2405.

Van Laarhoven, P.J.M., & Aarts, E.H. (1988). Simulated Annealing: Theory and Applications. Dordrecht: Kluwer Academic Publishers.