Abstract
This paper addresses a flexible job-shop scheduling problem with no-wait constraint (FJSPNW) which combines features of two well-known combinatorial optimization problems – flexible job-shop scheduling problem and no-wait job-shop scheduling problem. To solve FJSPNW with the objective of minimizing the makespan, an artificial bee colony (ABC) algorithm is proposed. This problem finds application in remanufacturing scheduling systems. ABC algorithm is a recently developed swarm intelligence technique based on intelligent foraging behavior of honey bee swarm. Since its inception, it has shown promising performance for the solution of numerous hard optimization problems. Numerical experiments have been performed on a set of standard benchmark instances in order to demonstrate the effectiveness of ABC algorithm.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
References
Garey, M.R., Johnson, D.S., Sethi, R.: The Complexity of Flow Shop and Job-shop Scheduling. Mathematics of Operations Research 1, 117–129 (1976)
Brucker, P., Schlie, R.: Job-shop Scheduling with Multi-purpose Machines. Computing 45, 369–375 (1990)
Brandimarte, P.: Routing and Scheduling in a Flexible Job Shop by Tabu Search. Annals of Operations Research 41, 157–183 (1993)
Mastrolilli, M., Gambardella, L.M.: Effective Neighborhood Functions for the Flexible Job Shop Problem. Journal of Scheduling 3, 3–20 (2000)
Gao, J., Sun, L., Gen, M.: A Hybrid Genetic and Variable Neighborhood Descent Algorithm for Flexible Job Shop Scheduling Problems. Computers & Operations Research 35, 2892–2907 (2008)
Lenstra, J.K., Rinnooy Kan, A.H.G., Brucker, P.: Complexity of Machine Scheduling Problems. Annals of Discrete Mathematics 1, 343–362 (1977)
Sahni, S., Cho, Y.: Complexity of Scheduling Shops with No Wait in Process. Mathematics of Operations Research 4, 448–457 (1979)
Kamoun, H., Sriskandarajah, C.: The Complexity of Scheduling Jobs in Repetitive Manufacturing Systems. European Journal of Operational Research 70, 350–364 (1993)
Hall, N.J., Sriskandarajah, C.: A Survey on Machine Scheduling Problems with Blocking and No-wait in Process. Operations Research 44, 510–525 (1996)
Zhu, J., Li, X.: An Effective Meta-heuristic for No-wait Job Shops to Minimize Makespan. IEEE Transactions on Automation Science and Engineering 9, 189–198 (2012)
Karaboga, D.: An Idea Based on Honey Bee Swarm for Numerical Optimization. Technical Report - TR06, Computer Engineering Department, Erciyes University, Turkey (2005)
Singh, A.: An Artificial Bee Colony Algorithm for the Leaf-Constrained Minimum Spanning Tree Problem. Applied Soft Computing 9, 625–631 (2009)
Pan, Q.-K., Tasgetiren, M.F., Suganthan, P.N., Chua, T.J.: A Discrete Artificial Bee Colony Algorithm for the Lot-Streaming Flow Shop Scheduling Problem. Information Sciences 181, 2455–2468 (2011)
Sundar, S., Singh, A.: A Swarm Intelligence Approach to the Quadratic Minimum Spanning Tree Problem. Information Sciences 180, 3182–3191 (2010)
Sundar, S., Singh, A.: A Swarm Intelligence Approach to the Quadratic Multiple Knapsack Problem. In: Wong, K.W., Mendis, B.S.U., Bouzerdoum, A. (eds.) ICONIP 2010, Part I. LNCS, vol. 6443, pp. 626–633. Springer, Heidelberg (2010)
Karaboga, D., Gorkemli, B., Ozturk, C., Karaboga, N.: A Comprehensive Survey: Artificial Bee Colony (ABC) Algorithm and Applications. Artificial Intelligence Review (2012), doi:10.1007/s10462-012-9328-0
Sundar, S., Singh, A.: A Swarm Intelligence Approach to the Early/Tardy Scheduling Problem. Swarm and Evolutionary Computation 4, 25–32 (2012)
Brizuela, C.A., Zhao, Y., Sannomiya, N.: No-wait and Blocking Job-shops: Challenging Problems for GA’s. In: Proceeding of IEEE International Conference on Systems, Man, and Cybernetics, pp. 2349–2354 (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sundar, S., Suganthan, P.N., Chua, T.J. (2013). A Swarm Intelligence Approach to Flexible Job-Shop Scheduling Problem with No-Wait Constraint in Remanufacturing. In: Rutkowski, L., Korytkowski, M., Scherer, R., Tadeusiewicz, R., Zadeh, L.A., Zurada, J.M. (eds) Artificial Intelligence and Soft Computing. ICAISC 2013. Lecture Notes in Computer Science(), vol 7895. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-38610-7_54
Download citation
DOI: https://doi.org/10.1007/978-3-642-38610-7_54
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-38609-1
Online ISBN: 978-3-642-38610-7
eBook Packages: Computer ScienceComputer Science (R0)