Abstract
This paper deals with the flexible job shop scheduling problem with the objective of minimizing the makespan. An efficient heuristic based on a constructive procedure is developed to obtain high-quality schedules very quickly. The algorithm is tested on benchmark instances from the literature in order to evaluate its performance. Computational results show that, despite its simplicity, the proposed heuristic can obtain effective solutions in very short and nearly zero time and is comparable with even metaheuristic algorithms and promising for practical problems.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Bagheri A, Zandieh M, Mahdavi I, Yazdani M (2010) An artificial immune algorithm for the flexible job-shop scheduling problem. Futur Gener Comput Syst 26:533–541
Baker K (1974) Introduction to sequencing and scheduling. Wiley, NewYork
Bozejko W, Uchronski M, Wodecki M (2010) Parallel hybrid metaheuristics for the flexible job shop problem. Comput Ind Eng 59:323–333
Bozejko W, Uchronski M, Wodecki M (2010) The new golf neighborhood for the flexible job shop problem. Procedia Comput Sci 1:289–296
Brandimarte P (1993) Routing and scheduling in a flexible job shop by tabu search. Ann Oper Res 41:157–183
Chiang T-C, Lin H-J (2013) A simple and effective evolutionary algorithm for multiobjective flexible job shop scheduling. Int J Prod Econ 141:87–98
Dauzere-Peres S, Paulli J (1997) An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Ann Oper Res 70:281–306
Dell’Amico M, Trubian M (1993) Applying tabu-search to the job-shop scheduling problem. Ann Oper Res 4:231–252
Ennigrou M, Ghédira K (2008) New local diversification techniques for flexible job shop scheduling problem with a multi-agent approach. Auton Agent Multi-Agent Syst 17:270–287
Garey MR, Johnson DS, Sethi R (1976) The complexity of flow shop and job-shop scheduling. Math Oper Res 1(2):117–129
Girish BS, Jawahar N (2009) Scheduling job shop associated with multiple routings with genetic and ant colony heuristics. Int J Prod Res 47(14):3891–3917
Gutiérrez C, García-Magariño I (2011) Modular design of a hybrid genetic algorithm for a flexible job-shop scheduling problem. Knowl-Based Syst 24(1):102–112
Hmida AB, Haouari M, Huguet M-J, Lopez P (2010) Discrepancy search for the flexible job shop scheduling problem. Comput Oper Res 37:2192–2201
Ho NB, Tay JC, Lai EM-K (2007) An effective architecture for learning and evolving flexible job-shop schedules. Eur J Oper Res 179:316–333
Huang R-H, Yang C-L, Cheng W-C (2013) Flexible job shop scheduling with due window: a two-pheromone ant colony approach. Int J Prod Econ 141:685–697
Kacem I, Hammadi S, Borne P (2002) Approach by localization and multiobjective evolutionary optimization for flexible job-shop scheduling problems. IEEE Trans Syst Man Cybern Part C 32(1):1–13
Kacem I, Hammadi S, Borne P (2002) Pareto-optimality approach for flexible job-shop scheduling problems: hybridization of evolutionary algorithms and fuzzy logic. Math Comput Simul 60:245–276
Li J-Q, Pan Q-K, Suganthan PN, Chua TJ (2010) A hybrid tabu search algorithm with an efficient neighborhood structure for the flexible job shop scheduling problem. Int J Adv Manuf Technol 52(5–8):683–697
Li J-Q, Pan Q-K, Xie S-X, Jia B-X, Wang Y-T (2010) A hybrid particle swarm optimization and tabu search algorithm for flexible job-shop scheduling problem, International Journal of Computer Theory and. Engineering 2(2):1793–8201
Liouane N, Saad I, Hammadi S, Borne P (2007) Ant systems and local search optimization for flexible job shop scheduling production. Int J Comput Commun Control 2(2):174–184
Mastrolilli M, Gambardella LM (2000) Effective neighborhood functions for the flexible job shop problem. J Sched 3(1):3–20
Matsuo H, Suh C, Sullivan R (1988) A controlled search simulated annealing method for the general job-shop scheduling problem, Tech. Rep. 03-04-88, Dept. of Management, The University of Texas, Austin
Montgomery DC (2000) Design and analysis of experiments, 5th edn. John Wiley & Sons, NewYork
Pezzella F, Morganti G, Ciaschetti G (2008) A genetic algorithm for the flexible job-shop scheduling problem. Comput Oper Res 35:3202–3212
Pinedo M (2002) Scheduling: theory, algorithms, and systems. Prentice-Hall, Englewood cliffs
Rossi A, Dini G (2007) Flexible job-shop scheduling with routing flexibility and separable setup times using ant colony optimisation method. Robot Comput Integr Manuf 23:503–516
Van Laarhoven P, Aarts E, Lenstra J (1992) Job shop scheduling by simulated annealing. Oper Res 40:113–125
Wang L, Wang S, Xu Y, Zhou G, Liu M (2012) A bi-population based estimation of distribution algorithm for the flexible job-shop scheduling problem. Comput Ind Eng 62:917–926
Wang L, Zhou G, Xu Y, Wang S, Liu M (2012) An effective artificial bee colony algorithm for the flexible job-shop scheduling problem. Int J Adv Manuf Technol 60:03–315
Xing L-N, Chen Y-W, Wang P, Zhao Q-S, Xiong J (2010) A knowledge-based ant colony optimization for flexible job shop scheduling problems. Appl Soft Comput 10:888–896
Xiong J, Xing L-N, Chen Y-W (2013) Robust scheduling for multi-objective flexible job-shop problems with random machine breakdowns. Int J Prod Econ 141:112–126
Yazdani M, Amiri M, Zandieh M (2010) Flexible job-shop scheduling with parallel variable neighborhood search algorithm. Expert Syst Appl 37:678–687
Yuan Y, Xu H (2013) Flexible job shop scheduling using hybrid differential evolution algorithms. Comput Ind Eng 65:246–260
Yuan Y, Xu H, Yang J (2013) A hybrid harmony search algorithm for the flexible job shop scheduling problem. Appl Soft Comput 13:3259–3272
Zhang G, Gao L, Shi Y (2011) An effective genetic algorithm for the flexible job-shop scheduling problem. Expert Syst Appl 38(4):3563–3573
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Ziaee, M. A heuristic algorithm for solving flexible job shop scheduling problem. Int J Adv Manuf Technol 71, 519–528 (2014). https://doi.org/10.1007/s00170-013-5510-z
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00170-013-5510-z