No-idle time Scheduling of Open shops: Modeling and Meta-heuristic Solution Methods

Naderi, Bahman; Roshanaei, Vahid

doi:10.22034/2014.1.04

No-idle time Scheduling of Open shops: Modeling and Meta-heuristic Solution Methods

Document Type : Research Paper

Authors

Bahman Naderi ¹
Vahid Roshanaei ²

¹ Department of Industrial Engineering, Faculty of Engineering, University of Kharazmi, Tehran, Iran

² Department of Industrial Engineering, University of Toronto, Toronto, Canada

10.22034/2014.1.04

Abstract

In some industries as foundries, it is not technically feasible to interrupt a processor between jobs. This restriction gives rise to a scheduling problem called no-idle scheduling. This paper deals with scheduling of no-idle open shops to minimize maximum completion time of jobs, called makespan. The problem is first mathematically formulated by three different mixed integer linear programming models. Since open shop scheduling problems are NP-hard, only small instances can be solved to optimality using these models. Thus, to solve large instances, two meta-heuristics based on simulated annealing and genetic algorithms are developed. A complete numerical experiment is conducted and the developed models and algorithms are compared. The results show that genetic algorithm outperforms simulated annealing.

Keywords

References

Abdelmaguid, T.F., Shalaby, M.A., Awwad, M.A., (2014). A tabu search approach forproportionate multiprocessor open shop scheduling. Computational Optimization and Applications, Vol. 58(1), pp. 187-203.

Andresen, M., Bräsel, H., Mörig, M., Tusch, J., Werner, F., Willenius, P., (2008). Simulated annealing and genetic algorithms for minimizing mean flow time in an open shop. Mathematical and Computer Modelling, Vol. 48, pp. 1279-1293.

Baraz, D., Mosheiov, G., (2008). A note on a greedy heuristic for flow-shop makespan minimization with no machine idle-time. European Journal of Operational Research, Vol. 184, pp. 810–813.

Balakrishnan, J., Cheng, C.H., Conway, D.G., Lau, C.M., (2003). A hybrid genetic algorithm for the dynamic plant layout problem. International Journal of Production Economics, Vol. 86, pp. 107–20.

Chen, Y., Zhang, A., Chen, G., Dong, J., (2013). Approximation algorithms for parallel open shop scheduling. Information Processing Letters, Vol. 113(7), pp. 220-224.

Chernykh, I., Kononova, A., Sevastyanova, S., (2013). Efficient approximation algorithms for the routing open shop problem. Computers and Operations Research, Vol. 40(3), pp. 841- 847.

Dai, M., Tang, D., Giret, A., Salido, M.A., Lid, W.D., (2013). Energy-efficient scheduling for a flexible flow shop using an improved genetic-simulated annealing algorithm. Robotics and Computer-Integrated Manufacturing, Vol. 29(5), pp. 418-429.

DengG., Gu, X., (2012). A hybrid discrete differential evolution algorithm for the no-idle permutation flow shop scheduling problem with makespan criterion. Computers and Operations Research, Vol. 39, pp. 2152–2160.

Dong, J., Zhang, A., Chen, Y., Yang, Q., (2013). Approximation algorithms for two-machine open shop scheduling with batch and delivery coordination. Theoretical Computer Science, Vol. 491, pp. 94-102.

El Houda Saadani, N., Guinet, A., Moall, M., (2005). A travelling salesman approach to solve the F/no-idle/Cmax problem. European Journal of Operational Research, Vol. 161, pp. 11–20.

Fatih Tasgetiren, M., Pan, Q.K., Suganthan, P.N., Buyukdagli, O., (2013). A variable iterated greedy algorithm with differential evolution for the no-idle permutation flowshop scheduling problem. Computers and Operations Research, Vol. 40, pp. 1729-1743.

Fatih Tasgetiren, M., Pan, Q.K., Suganthan, P.N., Oner, A., (2003). A discrete artificial bee colony algorithm for the no-idle permutation flowshop scheduling problem with the total tardiness criterion. Applied Mathematical Modelling, Vol. 37, pp. 6758–6779.

Goldansaz, S.M., Jolai, F., Zahedi Anaraki, A.H., (2013). A hybrid imperialist competitive algorithm for minimizing makespan in a multi-processor open shop. Applied Mathematical Modelling, Vol. 37(23), pp. 9603-9616.

Goncharov, Y., Sevastyanov, S., (2009). The flow shop problem with no-idle constraints: A review and approximation. European Journal of Operational Research, Vol. 196, pp. 450–456.

Kalczynski, P.J., Kamburowski, J., (2005). A heuristic for minimizing the makespan in noidle permutation flow shops. Computers and Industrial Engineering, Vol. 49, pp. 146–154.

Kolon, M., (1999). Some new results on simulated annealing applied to the job shop scheduling problem. European Journal of Operational Research, Vol. 113, pp. 123–136.

Naderi, B., Zandieh, M., Balagh, A.K.G., Roshanaei, V., (2009a). An improved simulated annealing for hybrid flowshops with sequence-dependent setup and transportation times to minimize total completion time and total tardiness. Expert Systems with Applications, Vol. 36, pp. 9625–9633.

Naderi, B., Zandieh, M., Fatemi Ghomi, S.M.T., (2009b). A study on integrating sequence dependent setup time flexible flow lines and preventive maintenance scheduling. Journal of Intelligent Manufacturing, Vol. 20, pp. 683–694.

Pan, Q.K., Ruiz, R., (2014). An effective iterated greedy algorithm for the mixed noidle permutation flowshop scheduling problem. Omega, Vol. 44, pp. 41-50.

Pan, Q.K., Wang, L., (2008). No-idle permutation flow shop scheduling based on a hybrid discrete particle swarm optimization algorithm. International Journal of Advanced Manufacturing Technology, Vol. 39, pp. 796–807.

Toledo, C.F.M., Oliveira, R.R.R., Franca, P.M., (2013). A hybrid multi-population genetic algorithm applied to solve the multi-level capacitated lot sizing problem with backlogging. Computers and Operations Research, Vol. 40, pp. 910-919.

Wang, Y.Z., (2002). An application of genetic algorithm methods for teacher assignment problems. Expert Systems with Applications, Vol. 22, pp. 295–302.

Zhang, D., Liu, Y., M’Hallah, R., Leung, S.C.H., (2010). A simulated annealing with a new neighborhood structure based algorithm for high school timetabling problems. European Journal of Operational Research, Vol. 203, pp. 550–558.