A heuristic hybrid framework for vector job scheduling
DOI:
https://doi.org/10.2298/YJOR150416013AKeywords:
Variable Neighborhood Search, Ant Colony Optimization, Scheduling, Integer ProgrammingAbstract
We examine the first phase of a known NP-hard 2-stage assembly problem. It consists of sequencing a set of jobs having multiple components to be processed. Each job has to be worked on independently on a specific machine. We consider these jobs to form a vector of tasks. Our objective is to schedule jobs on the particular machines in order to minimize the completion time before the second stage starts. We first develop a new mathematical programming formulation of the problem and test it on a small problem instance using an integer programming solver. Then, we develop a heuristic algorithm based on Ant Colony Optimization and Variable Neighborhood Search metaheuristics in order to minimize the total completion time. The performance of our implementation appears to be efficient and effective.References
Chen, Z.L., and Hall, N.G., “Supply chain scheduling conflict and cooperation in assembly systems”, Operations Research, 55 (6) (2007) 1072-1089.
Potts, C.N., “An algorithm for the single machine sequencing problem with precedence constraints”, Mathematical Programming Studies, 13 (1980) 78-87.
Potts, C.N., Sevastjanov, S.V., Strusevich, V.A., Van Wassenhove, L.N., and Zwaneveld, C.M., “Two-stage assembly scheduling problem: complexity and approximation”, Operations Research, 43 (2) (1995) 346-355.
Hsu, W.N., “Approximation algorithms for the assembly line crew scheduling problem”, Mathematics of Operations Research, 9 (3) (1984) 376-383.
Chong, K.E., Omar, M.K., and Bakar, N.A., “Solving assembly line balancing problem using genetic algorithm with heuristics treated initial population”, Proceedings of The World Congress on Engineering, 2 (2008) 1273-1277.
Al-Anzi, F.S., and Allahverdi, A., “A hybrid tabu search heuristic for the two-stage assembly scheduling problem”, International Journal of Operations Research, 3 (2) (2006) 106-119.
Webster, S., and Azizgolu, M., “Dynamic programming algorithm for scheduling parallel machines with family setup time”, Computers and Operations Research, 28 (2) (2001) 127-137.
Ishibuchi, H., Yamamoto, N., Murata, T., and Tanaka, H., “Genetic algorithms and neighborhood search algorithms for fuzzy flowshop scheduling problems”, Fuzzy Sets and Systems, 67 (1) (1994) 81-100.
Seda, M., “Mathematical model for flow job and job shop problems”, World Academy of Science, Engineering and Technology, 18 (3) (2007) 331-342.
Dorigo, M., and Caro, D.G., “The ant colony optimization meta-heuristic”, New Ideas in Optimization, McGraw-Hill, London, UK, (1999) 11-22.
Dorigo, M., and Stutzle, T., “Ant colony algorithms for quadratic assignment problem”, New Ideas in Optimization, McGraw-Hill, London, UK, 1999.
Colorni, A., Dorigo, M., Maniezzo, V., and Trubian, M., “Ant system for job shop scheduling”, Belgian Journal of Operations Research, Statistics and Computer Science, 34 (1) (1994) 39-53.
Rajendran, C., and Ziegler, H., “Ant colony algorithms for permutation flowshop scheduling to minimize makespan and total flowtime of jobs”, European Journal of Operational Research, 155 (2) (2004) 426-438.
Heinonen, J., and Pettersson, F., “Job-shop scheduling and visibility studies with a hybrid ACO algorithm”, Applied Mathematics and Computation, 187 (3) (2007) 989-998.
Huang, K., and Liao, C., “Ant colony optimization combined with tabu search for the job shop scheduling problem”, Computers and Operations Research, 35 (4) (2008) 1038-1046.
Eswaramurthy, V.P., and Tamilarasi, A., “Hybridizing tabu search with ant colony optimization for solving job shop scheduling problems”, International Journal of Advance Manufacturing Technology, 40 (2008) 1004-1015.
Surekha, P., and Sumathi, S., “Solving fuzzy based job shop scheduling problems using GA and ACO”, Journal of Emerging Trends in Computing and Information Sciences, 1 (2) (2010) 95-102.
Ponnambalam, S.G., Jawahar, N., and Girish, B.S., “An ant colony optimization algorithm for flexible job shop scheduling problem”, New Advanced Technologies, 4 (2010) 73-94.
Dorigo, M., and Gambardella, L.M., “Ant colonies for the traveling salesman problem”, Biosystems, 43 (1997) 73-81.
Zhang, J., Hu, X., Tan, X., Zhong, J.H., and Huang, Q., “Implementation of an ant colony optimization technique for job shop scheduling problem”, Transactions of the Institute of Measurement and Control, 28 (1) (2006) 93-108.
Liouane, N., Saad, I., Hammadi, S., and Borne, P., “Ant systems and local search optimization for flexible job shop scheduling production”, International Journal of Computers, Communications and Control, 2 (2) (2007) 174-184.
Mladenovic, N., Todosijevic, R., and Urosevic, D., “Two level general variable neighborhood search for attractive traveling salesman problem”, Yugoslav Journal of Operations Research, 23 (1) (2012) 19-30.
Sevkli, M., and Aydin, M., “Variable neighborhood search algorithm for job shop scheduling problems”, Evolutionary Computation in Combinatorial Optimization, 3906 (2006) 261-271.
Zhang, G., Gao, L., Li, X., and Li, P., “Variable neighborhood genetic algorithm for the flexible job shop scheduling problem”, Intelligent Robotics and Applications, 5315 (2008) 503-512.
Liao, C., and Cheng, C., “Variable neighborhood search for minimizing single machine weighted earliness and tardiness with common due date”, Computers and Industrial Engineering, 52 (4) (2007) 404-413.
Patkar, S., Poojari, C., and Porwal, P., “An investigation into approximate solutions for deterministic and stochastic multi-dimensional sequencing”, Brunel University, Archive, Brunel, 2005.
Mladenovic, N., and Hansen, P., “Variable neighborhood search”, Computers and Operations Research, 24 (11) (1997) 1097-1100.
Hansen, P., Mladenovic, N., Brimberg, J., and Moreno-Perez, J.A., “Variable neighborhood search”, Handbook of Metaheuristics, 2nd edition (Gendreau and Potvin Eds), International Series in Operations Research & Management Sciences, 146, Kluwer, (2010) 61–86.
Brimberg, J., Hansen, P., and Mladenovic, N., “Attraction probabilities in variable neighborhood search”, 4OR, 8 (2010) 181-194.
Mladenovic, N., Urosevic, D., and Dionisio Perez-Brito, “Variable neighborhood search for Minimum Linear Arrangement Problem”, Yugoslav Journal of Operations Research, 26 (1) (2016) 3-16.
Todosijevic, R., Hanafi, S., Lazic, J., and Mladenovic, N., “Variable and Single Neighborhood Diving for MIP Feasibility”, Yugoslav Journal of Operations Research, 26 (2) (2016) 131-157.
Fisher, H., and Thompson, G.L., “Probabilistic learning combinations of local job-shop scheduling rules”, J.F. Muth, G.L. Thompson (eds.), Industrial Scheduling, Prentice Hall, Englewood Cliffs, New Jersey, 1963.
Lawrence, S., “Resource constrained project scheduling: an experimental investigation of heuristic scheduling techniques (Supplement)”, Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, Pennsylvania, 1984.
Storer, R.H., Wu, S.D., and Vaccari, R., “New search spaces for sequencing instances with application to job shop scheduling”, Management Science, 38 (1992) 1495-1509.
Taillard, E., “Benchmarks for basic scheduling problems”, European Journal of Operational Research, 64 (1993) 278-285.
Yamada, T., and Nakano, R., “A genetic algorithm applicable to large-scale job-shop instances”, R. Manner, B. Manderick (eds.), Parallel instance solving from nature 2, North-Holland, Amsterdam, 1992, 281-290.
Downloads
Published
Issue
Section
License
Copyright (c) 2017 YUJOR
This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
