» Download Article

Authors
Imen Essafi; Yazid Mati

Digital Object Identifier (DOI)
10.3182/20060517-3-FR-2903.00261

Page Numbers:
499-504

Index Terms
job-shop scheduling,total weighted tardiness,hybrid genetic algorithm

Abstract
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.

References

[1] 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.
[2] 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.
[3] Giffler, B. and G. Thompson (1960). Algorithms
    for solving production scheduling problems.
    Operations Research 8, 487-503.
[4] 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.
[5] 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.
[6] Jain, A. S. and S. Meeran (1999). Deterministic
    job-shop scheduling: Past, present and future.
    European Journal of Operational Research
    113, 390-434.
[7] Kreipl, S. (2000). A large step random walk for
    minimizing total weighted tardiness in a job
    shop. Journal of Scheduling 3, 125-138.
[8] 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.
[9] Lawrence, S. (1984). Supplement to resource
    constrained project scheduling: An experimental
     investigation of heuristic scheduling
     techniques. Technical report, Carnegie-Mellon
     University, Pittsburgh.
[10] 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.
[11] 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.
[12] 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.
[13] Nowicki, E. and C. Smutnicki (1996). A fast taboo
     search algorithm for the job shop problem.
     Management Science 42, 797-813.
[14] 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.
[15] Roy, M. and M. Sussmann (1969). Les problèmes
     d'ordonnancement avec contraintes disjonctives.
      SEMA Notes DS, Paris.
[16] Singer, M. (2001). Decomposition methods for
     large job shops. Computers and Operations
     Research 28, 193-207.
[17] 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.
[18] 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.
[19] Taillard, E. D. (1994). Parallel taboo search techniques
      for the job shop scheduling problem.
     ORSA Journal on Computing 6, 108-117.
[20] Vepsalainen, A.P.J. and T. E. Morton (1985). Priority
      rules for job shops with weighted tardiness
      costs. Management Science 33, 585-596.
[21] Volta, R., G. Della Croce and F. Tadei (1995). A
     genetic algorithm for the job shop scheduling
     problem. Computers & Operations Research
     22, 15-24.