Volume 4 Issue 2 pp. 191-202 Spring, 2013


An imperialist competitive algorithm for a bi-objective parallel machine scheduling problem with load balancing consideration


Mansooreh Madani-Isfahani, Ehsan Ghobadian, Hassan Irani Tekmehdash, Reza Tavakkoli-Moghaddam and Mahdi Naderi-Beni




In this paper, we present a new Imperialist Competitive Algorithm (ICA) to solve a bi-objective scheduling of parallel-unrelated machines where setup times are sequence dependent. The objectives include mean completion tasks and mean squares of deviations from machines workload from their averages. The performance of the proposed ICA (PICA) method is examined using some randomly generated data and they are compared with three alternative methods including particle swarm optimization (PSO), original version of imperialist competitive algorithm (OICA) and genetic algorithm (GA) in terms of the objective function values. The preliminary results indicate that the proposed study outperforms other alternative methods. In addition, while OICA performs the worst as alternative solution strategy, PSO and GA seem to perform better.




DOI: 10.5267/j.ijiec.2013.02.002

Keywords: Parallel machine scheduling; Genetic algorithm; Imperialist competitive algorithm; Load Balancing; Particle swarm optimization

References

References Allahverdi, A., Ng, C., Cheng, T., & Kovalyov, M. (2008).A survey of scheduling problems with setup times or costs.European Journal of Operational Research, 187, 985-1032.

Atashpaz-Gargari, E., & Lucas, E. C. (2007). Imperialist Competitive Algorithm: An algorithm for optimization inspired by imperialist competitive.IEEE Congress on Evolutionary Computation, Singapore, 4661-4667.

Cossari, A., Ho, J.C., Paletta, G., &Torres, A.J.R. (2012).A new heuristic for workload balancing on identical parallel machines and a statistical perspective on the workload balancing criteria, Computers and Operations Research, 39, 1382-1392.

Engelbrecht, A. P. (2007). Computational Intelligence: An Introduction, 2nd ed., Wiley.

Goldberg, D.E. (1989). Genetic Algorithms in Search, Optimization and Machine Learning. Addison Wesley Longman.

Haupt, R. L., & Haupt, S. E. (2004).Practical Genetic Algorithm.2nd ed., Wiley.

Ho, J.C., Tseng, T.L.B., Torres, A.J.R., Lopez, F.J. (2009).Minimizing the normalized sum of square for workload deviations on m parallel processors.Computers and Industrial Engineering, 56, 186-192.

Holland, J.H. (1975).Adaptation in Natural and Artificial Systems. University of Michigan Press, Ann Arbor.

Hoogeveen, H. (2005). Multicriteria scheduling. European Journal of Operational Research, 167, 592-623.

Javadi, B., Saidi-Mehrabad, Haji, A., Mahdavi, I., Jolai, F., & Mahdavi-Amiri, N. (2008).No-wait flow shop scheduling using fuzzy multi-objective linear programming.Journal of Franklin Institute, 345, 452-467.

Jolai, F., Rabiee, M., & Asefi, H. (2012). A novel hybrid meta-heuristic algorithm for a no-wait flexible flow shop scheduling problem with sequence dependent setup times.International Journal of Production Research, 50 (24), 7447-7466.

Karimi, N., Zandieh. M., & Najafi, A. A. (2011). Group scheduling in flexible flow shops: a hybridised approach of imperialist competitive algorithm and electromagnetic-like mechanism.International Journal of Production Research, 49 (6), 4965-4977.

Kennedy, J., & Eberhart, R.C. (1995).Particle swarm optimization.In: Proceedings of the 1995 IEEE International Conference on Neural Networks, 4, 1942-1948.

Keskinturk, T., Yildirim, M.B., & Barut, M. (2012). An ant colony optimization algorithm for load balancing in parallel machines with sequence-dependent setup times.Computers & Operations Research, 39, 1225-1235.

Lei, D. (2009). Multi-objective production scheduling: a survey.International Journal of Advanced Manufacturing Technology, 43(9-10), 926-938.

Lian, Z. (2010). A united search particle swarm optimization algorithm for multiobjective scheduling problem.Applied Mathematical Modelling, 34, 3518-3526.

Moradinasab, N., Shafaei, R., Rabiee, M., & Ramezani, P. (2012). No-wait two stage hybrid flowshop scheduling with genetic and adaptive imperialist competitive algorithms.Journal of Experimental & Theoretical Artificial Intelligence, DOI: 10.1080/0952813X.2012.682752.

Naderi-Beni, M., Tavakkoli-Moghaddam, R., Naderi, B., Ghobadian, E., & Pourrousta, A. (2012). A two-phase fuzzy programming model for a complex bi-objective no-wait flow shop scheduling. International Journal of Industrial Engineering Computations, 3, 617-626.

Nagar, A., Haddock, J., Heragu, S. (1995). Multiple and bicriteria scheduling: a literature survey. European Journal of Operational Research, 81, 88-104, DOI: 10.1016/0377-2217(93) E0140-S.

Ouazene, Y., Hnaien, F., Yalaoui, F., & Amodeo, L. (2011). The joint load balancing and parallel machine scheduling problem.Operations Research Proceedings 2010, DOI: 10.1007/978-3-642-2009-0_79, Springer_Verlag Berlin Heidelberg.

Pinedo, M.L. (2008). Scheduling, Algorithms, and Systems.3rd ed., Springer.

Raghavendra, B.V., & Murthy, A.N.N. (2011).Workload balancing in identical parallel machine scheduling while planning in flexible manufacturing system using genetic algorithm.ARPN Journal of Engineering and Applied Sciences, 6 (1).

Rajakumar, S., Arunachalam, V.P., & Selladurai, V. (2004). Workflow balancing strategies in parallel machine scheduling.International Journal of Advanced Manufacturing Technology, 23, 366-374, DOI: 10.1007/s00170-003-1603-4.

Rajakumar, S., Arunachalam, V.P., & Selladurai, V. (2006).Workflow balancing in parallel machine scheduling with precedence constraints using genetic algorithm.Journal of Manufacturing Technology Management, 17, 239-254.

Rajakumar, S., Arunachalam, V.P., & Selladurai, V. (2007).Workflow balancing in parallel machines through genetic algorithm.International Journal of Advanced Manufacturing Technology, 33, 1212-1221, DOI: 10.1007/s00170-006-0553-z.

Shokrollahpour, E., Zandieh, M., & Dorri, B. (2011).A novel imperialist competitive algorithm for bi-criteria scheduling of the assembly flowshop problem.International Journal of Production Research, 49 (11), 3087-3103.

Tavakkoli-Moghaddam, R., Taheri, F., Bazzazi, M., Izadi, M., & Sassani, F. (2009). Design of a genetic algorithm for bi-objective unrelated parallel machines scheduling with sequence-dependent setup times and precedence constraints.Computers and Operations Research, 36, 3224-3230.

T’Kindt, V., Billaut, J.C., & Proust, C. (2001).Solving a bicriteria scheduling problem on unrelated parallel machines occurring in the glass bottle industry.European Journal of OperationalResearch, 135, 42-49.

Vallada, E., & Ruiz, R. (2011). A genetic algorithm for the unrelated parallel machine scheduling problem with sequence dependent setup times.European Journal of Operational Research, 211, 612-622.

Varmazyar, M., & Salmasi, N. (2012).Sequence-dependent flow shop scheduling problem minimising the number of tardy jobs.International Journal of Production Research, 50 (20), 5843-5858.

Yuan, X. (2011).Multi-objective optimization of fuzzy parallel machines scheduling problem using nondominated genetic algorithms. Journal of Software, 6 (10).