Document Type : Original Article

Author

Department of Industrial Engineering, Yazd University, Yazd, Iran

Abstract

The parallel machine scheduling problem (PMSP) is one of the most difficult classes of problem. Due to the complexity of the problem, obtaining optimal solution for the problems with large size is very time consuming and sometimes, computationally infeasible. So, heuristic algorithms that provide near-optimal solutions are more practical and useful. The present study aims to propose a hybrid metaheuristic approach for solving the problem of unrelated parallel machine scheduling, in which, the machine and the job sequence dependent setup times are considered. A Mixed-Integer Programming (MIP) model is formulated for the unrelated PMSP with sequence dependent setup times. The solution approach is robust, fast, and simply structured. The hybridization of Genetic Algorithm (GA) with Ant Colony Optimization (ACO) algorithm is the key innovative aspect of the approach. This hybridization is made in order to accelerate the search process to near-optimal solution. After computational and statistical analysis, the two proposed algorithms are used to compare with the proposed hybrid algorithm to highlight its advantages in terms of generality and quality for short and large instances. The results show that the proposed hybrid algorithm has a very good performance as regards the instance size and provides the acceptable results.

Keywords

Arnaout, J., (2020). "A worm optimization algorithm to minimize the makespan on unrelated parallel machines with sequence-dependent setup times", Annals of Operations Research, Vol. 285, pp. 273–293.
Arnaout, J., Musa, R., and Rabadi, G., (2014). "A two-stage Ant Colony optimization algorithm to minimize the makespan on unrelated parallel machines—part II: enhancements and experimentations", Journal of Intelligent Manufacturing, Vol. 25, pp. 43–53.
Babaee T., E., Alinaghian, M., Rahmani Hosseinabadi, A. A., Bakhshi Sasi, M., and Kumar Sangaiah A., (2019). "An improved ant colony optimization for the multi-trip Capacitated Arc Routing Problem", Computers and Electrical Engineering, Vol. 77, pp. 457-470.
Babaee T., E., Goli, A. and Weber, G., (2020). "Fuzzy Mathematical Programming and Self-Adaptive Artificial Fish Swarm Algorithm for Just-in-Time Energy-Aware Flow Shop Scheduling Problem with Outsourcing Option", IEEE Transactions on Fuzzy Systems.
Bastos, C. E. N., and Resendo, L. C., (2020). "Two-step approach for scheduling jobs to non-related parallel machines with sequence dependent setup times applying job splitting", Computers & Industrial Engineering, Vol. 145.
Behnamian, J., Zandieh, M., and Fatemi Ghomi, S.M.T., (2009). "Parallel-machine scheduling problems with sequence-dependent setup times using an ACO, SA and VNS hybrid algorithm", Expert Systems with Applications, Vol. 36, pp. 9637–9644.
Ezugwu Absalom, E., Adeleke Olawale, J., and Viriri S., (2018). "Symbiotic organisms search algorithm for the unrelated parallel machines scheduling with sequence-dependent setup times", PLoS ONE, Vol. 13, No. 7.
Ezugwu Absalom, E., (2019). "Enhanced symbiotic organisms search algorithm for unrelated parallel machines manufacturing scheduling with setup times", Knowledge-Based Systems, Vol. 172, No. 15, pp. 15-32.
Fanjul-Peyro, L., Perea, F., and Ruiz, R., (2017). "Models and matheuristics for the unrelated parallel machine scheduling problem with additional resources", European Journal of Operational Research, Vol. 260, No. 2, pp. 482-493.
Fanjul-Peyro, L., and Ruiz, R., (2010). "Iterated greedy local search methods for unrelated parallel machine scheduling", European Journal of Operational Research, Vol. 207, No. 1, pp. 55–69.
Fanjul-Peyro, L., and Ruiz, R., (2011). "Size-reduction heuristics for the unrelated parallel machines scheduling problem", Computers & Operations Research, Vol. 38, No. 1, pp. 301–309.
Fanjul-Peyro, L., Ruiz, R., and Perea, F., (2019). "Reformulations and an exact algorithm for unrelated parallel machine scheduling problems with setup times", Computers and Operations Research, Vol. 101, pp. 173-182.
Gedik, R., Rainwater, C., Nachtmann, H., and Pohl, E., (2016). "Analysis of a Parallel Machine Scheduling Problem with Sequence Dependent Setup Times and Job Availability Intervals", European Journal of Operational Research, Vol. 251, No. 2, pp. 640-650.
Guinet, A., (1993). "Scheduling sequence-dependent jobs on identical parallel machines to minimize completion time criteria", International Journal of Production Research, Vol. 31, No. 7, pp. 1579-1594.
Hosseini, Seyed Mohammad Hassan, (2019). "A bi-objective model for the assembly flow shop scheduling problem with sequence dependent setup times and considering energy consumption", Journal of Industrial Engineering and Management Studies, Vol. 6, No. 2, pp. 44-64
Hu, Hongtao, Ng K. K. H. and Qin, Y., (2016). "Robust Parallel Machine Scheduling Problem with Uncertainties and Sequence-Dependent Setup Time", Scientific Programming.
Kim, J., Song, S., and Jeong, B., (2020). "Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times", International Journal of Production Research, Vol. 58, No. 6, pp. 1628-1643.
Lee, Ju-Y., Kim, Y., and Lee, T., (2018). "Minimizing Total Tardiness on Parallel Machines Subject to Flexible Maintenance", International Journal of Industrial Engineering: Theory, Applications and Practice, Vol. 25, No. 4, pp. 472-489.
Logendran, R., McDonell, B., and Smucker, B., (2007). "Scheduling unrelated parallel machines with sequence-dependent setups", Computers & Operations Research, Vol. 34, pp. 3420 – 3438.
Rabadi, G., Moraga, R. J., and Al-salem, A., (2006). "Heuristics for the unrelated parallel machine scheduling problem with setup times", Journal of Intelligent Manufacturing, Vol. 17, pp. 85–97.
Radhakrishnan, S., and Ventura, J. A., (2000). "Simulated annealing for parallel machine scheduling with earliness tardiness penalties and sequence-dependent set-up times", International Journal of Production Research, Vol. 38, No. 10, pp. 2233- 2252.
Santos Haroldo, G., Toffolo T´ulio, A.M., Silva Cristiano L.T.F. and Berghe G. V., (2016). "Analysis of stochastic local search methods for the unrelated parallel machine scheduling problem", International journal of Transaction in Operation Research.
Sayyah M., Larki, H., and Yousefikhoshbakht, M., (2016). "Solving the Vehicle Routing Problem with Simultaneous Pickup and Delivery by an Effective Ant Colony Optimization", Journal of Industrial Engineering and Management Studies, Vol. 3, No. 1, pp. 15 – 38.
Sels V., Coelho J., Dias António, M., and Vanhoucke, M., (2015). "Hybrid tabu search and a truncated branch-and-bound for the unrelated parallel machine scheduling problem", Computers & Operations Research, Vol. 53, pp. 107–117.
Sung, I., Nam, H., and Lee, T., (2013). "Scheduling Algorithms for Mobile Harbor: an Extended M-Parallel Machine Problem” ", International Journal of Industrial Engineering: Theory, Applications and Practice, Vol. 20, No. 1-2, pp. 211-224.
Tsai, C., and Wang, Y., (2015). "Efficient mixed integer programming formulations and dispatching rules for parallel machine scheduling with allowing machine idle times", International Journal of Industrial and Systems Engineering, Vol. 21, No. 3, pp. 320-333.
Vallada, E., and Ruiz, R., (2011). "A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times", European Journal of Operational Research, Vol. 211, No. 3, pp. 612–622.
Ying, K., and Cheng, H., (2010). "Dynamic parallel machine scheduling with sequence-dependent setup times using an iterated greedy heuristic", Expert Systems with Applications, Vol. 37, No. 4, pp. 2848– 2852.
Yepes-Borrero, J. C., Villa, F., Perea, F., and Caballero-Villalobos, J. P., (2019). “GRASP algorithm for the unrelated parallel machine scheduling problem with setup times and additional resources”, Expert Systems with Applications, Vol. 141.