COMBINING METAHEURISTICS FOR THE JOB SHOP SCHEDULING PROBLEM WITH SEQUENCE DEPENDENT SETUP TIMES

Miguel A. González, María R. Sierra, Camino R. Vela, Ramiro Varela, Jorge Puente

2006

Abstract

The Job Shop Scheduling (J SS) is a hard problem that has interested to researchers in various fields such as Operations Research and Artificial Intelligence during the last decades. Due to its high complexity, only small instances can be solved by exact methods, while instances with a size of practical interest should be solved by means of approximate methods guided by heuristic knowledge. In this paper we confront the Job Shop Scheduling with Sequence Dependent Setup Times (SDJ SS). The SDJ SS problem models many real situations better than the J SS. Our approach consists in extending a genetic algorithm and a local search method that demonstrated to be efficient in solving the J SS problem. We report results from an experimental study showing that the proposed approaches are more efficient than other genetic algorithm proposed in the literature, and that it is quite competitive with some of the state-of-the-art approaches.

References

  1. Artigues, C., Belmokhtar, S., and Feillet, D. (2004). A New Exact Algorithm for the Job shop Problem with Sequence Dependent Setup Times, pages 96-109. LNCS 3011. Springer-Verlag.
  2. Artigues, C., Lopez, P., and P.D., A. (2005). Schedule generation schemes for the job shop problem with sequence-dependent setup times: Dominance properties and computational analysis. Annals of Operational Research, 138:21-52.
  3. Bierwirth, C. (1995). A generalized permutation approach to jobshop scheduling with genetic algorithms. OR Spectrum, 17:87-92.
  4. Brucker, P. (2004). Scheduling Algorithms. SpringerVerlag, 4th edition.
  5. Brucker, P., Jurisch, B., and Sievers, B. (1994). A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics, 49:107-127.
  6. Brucker, P. and Thiele, O. (1996). A branch and bound method for the general-job shop problem with sequence-dependent setup times. Operations Research Spektrum, 18:145-161.
  7. Carlier, J. and Pinson, E. (1994). Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research, 78:146-161.
  8. Cheung, W. and Zhou, H. (2001). Using genetic algorithms and heuristics for job shop scheduling with sequencedependent setup times. Annals of Operational Research, 107:65-81.
  9. Dell' Amico, M. and Trubian, M. (1993). Applying tabu search to the job-shop scheduling problem. Annals of Operational Research, 41:231-252.
  10. Giffler, B. and Thomson, G. (1960). Algorithms for solving production scheduling problems. Operations Reseach, 8:487-503.
  11. González, M., Sierra, M., Vela, C., and Varela, R. (2006). Genetic Algorithms Hybridized with Greedy Algorithms and Local Search over the Spaces of Active and Semi-active Schedules. LNCS (to appear). SpringerVerlag.
  12. Lawrence, S. (1984). Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (supplement). Technical report, Graduate School of Industrial Administration, Carnegie Mellon University.
  13. Mattfeld, D. (1995). Evolutionary Search and the Job Shop. Investigations on Genetic Algorithms for Production Scheduling. Springer-Verlag.
  14. Nowicki, E. and Smutnicki, C. (1996). A fast taboo search algorithm for the job shop problem. Management Science, 42:797-813.
  15. Ovacik, I. and Uzsoy, R. (1993). Exploiting shop floors status information to schedule complex jobs. Operations Research Letters, 14:251-256.
  16. Taillard, E. (1993). Parallel taboo search techniques for the job shop scheduling problem. ORSA Journal of Computing, 6:108-117.
  17. Varela, R., Serrano, D., and M., S. (2005). New Codification Schemas for Scheduling with Genetic Algorithms, pages 11-20. LNCS 3562. Springer-Verlag.
  18. Varela, R., Vela, C., Puente, J., and A., G. (2003). A knowledge-based evolutionary strategy for scheduling problems with bottlenecks. European Journal of Operational Research, 145:57-71.
  19. Zoghby, J., Barnes, J., and J.J., H. (2005). Modeling the re-entrant job shop scheduling problem with setup for metaheuristic searches. European Journal of Operational Research, 167:336-348.
Download


Paper Citation


in Harvard Style

A. González M., R. Sierra M., R. Vela C., Varela R. and Puente J. (2006). COMBINING METAHEURISTICS FOR THE JOB SHOP SCHEDULING PROBLEM WITH SEQUENCE DEPENDENT SETUP TIMES . In Proceedings of the First International Conference on Software and Data Technologies - Volume 2: ICSOFT, ISBN 978-972-8865-69-6, pages 211-218. DOI: 10.5220/0001312402110218


in Bibtex Style

@conference{icsoft06,
author={Miguel A. González and María R. Sierra and Camino R. Vela and Ramiro Varela and Jorge Puente},
title={COMBINING METAHEURISTICS FOR THE JOB SHOP SCHEDULING PROBLEM WITH SEQUENCE DEPENDENT SETUP TIMES},
booktitle={Proceedings of the First International Conference on Software and Data Technologies - Volume 2: ICSOFT,},
year={2006},
pages={211-218},
publisher={SciTePress},
organization={INSTICC},
doi={10.5220/0001312402110218},
isbn={978-972-8865-69-6},
}


in EndNote Style

TY - CONF
JO - Proceedings of the First International Conference on Software and Data Technologies - Volume 2: ICSOFT,
TI - COMBINING METAHEURISTICS FOR THE JOB SHOP SCHEDULING PROBLEM WITH SEQUENCE DEPENDENT SETUP TIMES
SN - 978-972-8865-69-6
AU - A. González M.
AU - R. Sierra M.
AU - R. Vela C.
AU - Varela R.
AU - Puente J.
PY - 2006
SP - 211
EP - 218
DO - 10.5220/0001312402110218