Abstract
This paper deals with the Job shop Scheduling problem with Time Lags (JSTL). JSTL is an extension of the job shop scheduling problem, where minimum and maximum time lags are introduced between successive operations of the same job. We propose a combination between Biogeography-Based Optimization (BBO) algorithm and Greedy heuristic for solving the JSTL problem with makespan minimization. Biogeography-Based optimization is an evolutionary algorithm which is inspired by the migration of species between habitats. BBO has successfully solved optimization problems in many different domains and has reached a relatively mature state using two main steps: migration and mutation. Good performances of the proposed combination between Greedy and BBO algorithms are shown through different comparisons on benchmarks of Fisher and Thompson, Lawrence and Carlier for JSTL problem.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Afsar, H.M., Lacomme, P., Ren, L., Prodhon, C., Vigo, D.: Resolution of a job-shop problem with transportation constraints, a master/slave approach. In: IFAC Conference on Manufacturing Modelling, Management and Control (2016)
Artigues, C., Huguet, M., Lopez, P.: Generalized disjunctive constraint propagation for solving the job shop problem with time lags. Eng. Appl. Artif. Intell. 24, 220–231 (2011)
Carlier, J.: Ordonnancements a contraintes disjunctives. RAIRO Rech. operationelle/Oper. Res. 12, 333–351 (1978)
Caumond, A., Lacomme, A,P., Tchernev, N.: Proposition d’un algorithme génétique pour le job-shop avec time-lags. In: ROADEF 2005, pp. 183–200 (2005)
Caumond, A., Gourgand, M., Lacomme, P., Tchernev, N.: Métaheuristiques pour le problème de job shop 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, pp. 939–946. Nantes, France (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. Comput. Oper. Res. 35, 2331–2356 (2008)
Deppner, F.: Ordonnancement d’atelier avec contraintes temporelles entre opérations, Ph.D. thesis, Institut National Polytechnique de Lorraine (2004)
Fisher, H., Thompson, G.L.: Probabilistic Learing Combination of Local Job Shop Scheduling Rules, pp. 225–251. Prentice Hall, Industrial Scheduling (1963)
González, M.A., Oddi, A., Rasconi, R., Varela, R.: Scatter search with path relinking for the job shop with time lags and set up times. Comput. Oper. Res. 60, 37–54 (2015)
Harrabi, M., Belkahla Driss, O.: MATS-JSTL: a multi-agent model based on tabu search for the job shop problem with time lags. In: International Computational Collective Intelligence Technologies and Applications ICCCI, pp. 39–46 (2015)
Harrabi, M., Belkahla Driss, O., Ghedira, K.: Competitive agents implementing parallel tabu searches for job shop scheduling problem with time lags. In: IASTED International Conference on Modelling, Identification and Control, pp. 848–052. MIC (2017)
Harrabi, M., Belkahla Driss, O., Ghedira, K.: Combining genetic algorithm and tabu search for job shop scheduling problem with time lags. In: IEEE International Conference on Engineering & MIS, pp. 1–8 (2017)
Harrabi, M., Belkahla Driss, O., Ghedira, K.: A multi-agent model based on hybrid genetic algorithm for job shop scheduling problem with generic time lags. In: ACS/IEEE International Conference on Computer Systems and Applications AICCSA, pp. 995–1002 (2017)
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, Hammamet, Tunisie, pp. 10–12 (2000)
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)
Lacomme, P., Tchernev, N.: Job-shop with generic time lags: a heuristic based approach. In: 9th International Conference of Modeling, Optimization and Simulation – MOSIM (2012)
Lawrence, S.: Supplement to Resource Constrained Project Scheduling: An experimental investigation of Heuristic Scheduling Techniques. Graduate School of Industrial Administration, Carnegie Mellon University (1984)
MacArthur, R., Wilson, E.: The Theory of Biogeography. Princeton University Press, Princeton (1967)
Manne, S.: On the job-shop scheduling problem. Oper. Res. 8, 219–223 (1960)
Simon, D.: Biogeography-based optimization. IEEE Trans. Evol. Comput. 12, 702–713 (2008)
Wikum, E.D., Lewellynn, D.C., Nemhauser, G.L.: One-machine generalized precedence constrained scheduling problems. Oper. Res. Lett. 16, 87–99 (1994)
Yang, Y.: A Modified Biogeography-Based Optimization for the Flexible Job Shop Scheduling Problem, Mathematical Problems in Engineering (2015)
Brucker, P.: Scheduling and constraint propagation. Discrete Appl. Math. 123, 227–256 (2002)
Huang, K.L., Liao, C.J.: Ant colony optimization combined with taboo search for the job shop scheduling problem. Comput. Oper. Res. 35, 1030–1046 (2008)
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2019 Springer International Publishing AG, part of Springer Nature
About this paper
Cite this paper
Harrabi, M., Driss, O.B., Ghedira, K. (2019). A Greedy Biogeography-Based Optimization Algorithm for Job Shop Scheduling Problem with Time Lags. In: Graña, M., et al. International Joint Conference SOCO’18-CISIS’18-ICEUTE’18. SOCO’18-CISIS’18-ICEUTE’18 2018. Advances in Intelligent Systems and Computing, vol 771. Springer, Cham. https://doi.org/10.1007/978-3-319-94120-2_47
Download citation
DOI: https://doi.org/10.1007/978-3-319-94120-2_47
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-94119-6
Online ISBN: 978-3-319-94120-2
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)