Abstract
The Job Shop problem with Time Lags (JSTL) is an important extension of the classical job shop scheduling problem, in that additional constraints of minimum and maximum time lags existing between two successive operations of the same job are added. The objective of this work is to present a distributed approach based on cooperative behaviour and a tabu search metaheuristic to finding the scheduling giving a minimum makespan. The proposed model is composed of two classes of agents: a Supervisor Agent, responsible for generating the initial solution and containing the Tabu Search core, and Resource_Scheduler Agents, which are responsible for moving several operations and satisfaction of some constraints. Good performances of our model are shown through experimental comparisons on benchmarks of the literature.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Artigues, C., Huguet, M., Lopez, P.: Generalized disjunctive constraint propagation for solving the job shop problem with time lags. Engineering Applications of Artificial Intelligence 24, 220–231 (2011)
Ben Yahia, A., Belkahla Driss, O.: A multi-agent approach for the job shop problem with time lags. In: International Conference on Artificial Intelligence, ICAI, Tunisie (2013)
Caumond, A., Gourgand, M., Lacomme, P., Tchernev, N.: Métaheuristiques pour le problème de jobshop avec time lags : Jm|li,s j(i)|Cmax. In: 5ème Confèrence Francophone de Modélisation et SIMulation (MOSIM 2004). Modélisation et simulation pour l’analyse et l’optimisation des systèmes industriels et logistiques, Nantes, France, pp. 939–946 (2004)
Caumond, A., Lacomme, P., Tchernev, N.: Feasible schedule generation with extension of the Giffler and Thompson’s heuristic for the job shop problem with time lags. In: International Conference of Industrial Engineering and Systems Management, pp. 489−499 (2005)
Caumond, A., Lacomme, P., Tchernev, N.: A memetic algorithm for the job-shop with time-lags. Computers Operations Research 35, 2331–2356 (2008)
Deppner, F.: Ordonnancement d’atelier avec contraintes temporelles entre opérations. PhD thesis, Institut National Polytechnique de Lorraine (2004)
Fisher, H., Thompson, G.L.: Probabilistic learing combination of local jobshop scheduling rules. In: Industrial Scheduling, pp. 225−251. Prentice Hall (1963)
Glover, F.: Future paths for Integer Programming and Links to Artificial Intelligence. Computers and Operations Research 5, 533–549 (1986)
Heilman, R.: A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags. European Journal of Operational Research 144(2), 348–365 (2003)
Hurink, J., Keuchel, J.: Local search algorithms for a single machine scheduling problem with positive and negative time-lags. Discrete Applied Mathematics 112, 179–197 (2001)
Karoui, W., Huguet, M.-J., Lopez, P., Haouari, M.: Méthode de recherche à divergence limitée pour les problèmes d’ordonnancement avec contraintes de délais [Limited discrepancy search for scheduling problems with time-lags]. In: 8ème ENIM IFAC Conférence Internationale de Modélisation et Simulation (MOSIM 2010), Hammamet, Tunisie, May 10−12, 2010
Lawrence, S.: Supplement to Resource Constrained Project Scheduling : An experimental investigation of Heuristic Scheduling Techniques. Graduate School of Industrial Administration, Carnegie Mellon University, Pittsburgh, PA (1984)
Lacomme, P., Huguet, M.J., Tchernev, N.: Dedicated constraint propagation for Job-Shop problem with generic time-lags. In: 16th IEEE Conference on Emerging Technologies and Factory Automation IEEE Catalog Number: CFP11ETF-USB, Toulouse, France (2011). ISBN 978-1- 4577-0016-3
Mitten, L.G.: Sequencing n jobs on two mahines with arbitrary timlags. Management Science 5(3) (1958)
Wikum, E.D., Llewellyn, D.C., Nemhauser, G.L.: One-machine generalized precedence constrained scheduling problems. Operations Research Letters 16, 87–99 (1994)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Harrabi, M., Olfa, B. (2015). MATS–JSTL: A Multi-Agent Model Based on Tabu Search for Job Shop Problem with Time Lags. In: Núñez, M., Nguyen, N., Camacho, D., Trawiński, B. (eds) Computational Collective Intelligence. Lecture Notes in Computer Science(), vol 9329. Springer, Cham. https://doi.org/10.1007/978-3-319-24069-5_4
Download citation
DOI: https://doi.org/10.1007/978-3-319-24069-5_4
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-24068-8
Online ISBN: 978-3-319-24069-5
eBook Packages: Computer ScienceComputer Science (R0)