A genetic local search algorithm for minimizing the total weighted tardiness in a job-shop
Information Control Problems in Manufacturing, Volume # 12 | Part# 1
Imen Essafi; Yazid Mati
Digital Object Identifier (DOI)
job-shop scheduling,total weighted tardiness,hybrid genetic algorithm
We consider a job-shop scheduling problem with release dates and due dates, with the objective of minimizing the total weighted tardiness. A genetic algorithm is combined with an iterated local search that uses a neighborhood based on a disjunctive graph model. In this paper, we show that the efficiency of genetic algorithms does no longer depend on the schedule builder when an iterated local search is used. Computational experiments carried out on instances of the literature show the efficiency of the proposed algorithm over the existing methods.
 Cheng, R., M. Gen and Y. Tsujimura (1996). A tutorial survey of job-shop scheduling problems using genetic algorithms-i. representation. Computers & Industrial Engineering 30, 983-997.  Essafi, I. and Y. Mati (2005). A genetic local search algorithm for minimizing the total weighted tardiness in a job-shop. Working paper n 05/7/AUTO Ecole des Mines de Nantes.  Giffler, B. and G. Thompson (1960). Algorithms for solving production scheduling problems. Operations Research 8, 487-503.  Goncalves, J.F., J.J.M. Mendes and M.G.C. Resende (2005). A hybrid genetic algorithm for the job shop scheduling problem. European Journal of Operational Research 167, 77-95.  Graham, R.L., E.L. Lawler, J.K. Lenstra and A.H.G Rinnooy Kan (1979). Optimization and approximation in deterministic scheduling: A survey. Annals Discrete Mathematics 5, 287-326.  Jain, A. S. and S. Meeran (1999). Deterministic job-shop scheduling: Past, present and future. European Journal of Operational Research 113, 390-434.  Kreipl, S. (2000). A large step random walk for minimizing total weighted tardiness in a job shop. Journal of Scheduling 3, 125-138.  Laarhoven, P. J. M. Van, E. H. L. Aarts and J. K. Lenstra (1992). Job shop scheduling by simulated annealing. Operations Research 40, 113-125.  Lawrence, S. (1984). Supplement to resource constrained project scheduling: An experimental investigation of heuristic scheduling techniques. Technical report, Carnegie-Mellon University, Pittsburgh.  Lourenco, H.R. (1995). Job-shop scheduling: Computational study of local search and large-step optimization methods. European Journal of Operational Research 83, 347-364.  Mati, Y., S. Dauzère-Pérès and C. Lahlou (2005). A general approach for optimizing regular criteria in the job shop scheduling problem. Working paper Ecole des Mines de Nantes.  Mattfeld, D.C. and C. Bierwirth (2004). An efficient genetic algorithm for job shop scheduling with tardiness objectives. European Journal of Operational Research 155, 616-630.  Nowicki, E. and C. Smutnicki (1996). A fast taboo search algorithm for the job shop problem. Management Science 42, 797-813.  Pinedo, M. and M. Singer (1999). A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. Naval Research Logistics 46, 1-17.  Roy, M. and M. Sussmann (1969). Les problèmes d'ordonnancement avec contraintes disjonctives. SEMA Notes DS, Paris.  Singer, M. (2001). Decomposition methods for large job shops. Computers and Operations Research 28, 193-207.  Singer, M. and M. Pinedo (1998). A computational study of branch and bound techniques for minimizing the total weighted tardiness in job shops. IIE Transactions 30, 109-118.  Storer, R.H., D.S. Wu and R. Vaccari (1992). New search spaces for sequencing problems with application to job shop scheduling. Management Science 38, 1495-1509.  Taillard, E. D. (1994). Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal on Computing 6, 108-117.  Vepsalainen, A.P.J. and T. E. Morton (1985). Priority rules for job shops with weighted tardiness costs. Management Science 33, 585-596.  Volta, R., G. Della Croce and F. Tadei (1995). A genetic algorithm for the job shop scheduling problem. Computers & Operations Research 22, 15-24.