A Flexible Flowshop Scheduling Problem with Machine Eligibility Constraint and Two Criteria Objective Function

Authors: Bita Tadayon, Nasser Salmasi

Abstract:

This research deals with a flexible flowshop scheduling problem with arrival and delivery of jobs in groups and processing them individually. Due to the special characteristics of each job, only a subset of machines in each stage is eligible to process that job. The objective function deals with minimization of sum of the completion time of groups on one hand and minimization of sum of the differences between completion time of jobs and delivery time of the group containing that job (waiting period) on the other hand. The problem can be stated as FFc / rj , Mj / irreg which has many applications in production and service industries. A mathematical model is proposed, the problem is proved to be NPcomplete, and an effective heuristic method is presented to schedule the jobs efficiently. This algorithm can then be used within the body of any metaheuristic algorithm for solving the problem.

Keywords: flexible flowshop scheduling, group processing, machine eligibility constraint, mathematical modeling.

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1059783

References:

[1] M. Pinedo, Scheduling Theory, Algorithms, and Systems. 3rd Edition, LLC, New York: Springer, 2008.
[2] R. Ruiz, C. Maroto, "A genetic algorithm for hybrid flowshops with sequence dependent setup times and machine eligibility," European Journal of Operational Research, vol. 169(3), pp. 781-800, 2006.
[3] MS. Salvador, "A solution to a special class of flow shop scheduling problems," In: Elmaghraby SE, (Eds.), Symposium of the Theory of Scheduling and Applications, Berlin: Springer, 1973, pp. 83-9.
[4] I. Ribas, R. Leisten, JM. Framinan, "Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective," Computers & Operations Research, vol. 37, pp. 1439-54, 2010.
[5] R. Ruiz, JA.Vázquez-Rodríguez, "The hybrid flow shop scheduling problem," European Journal of Operational Research, vol. 205, pp. 1- 18, 2010.
[6] CT. Tseng, CJ. Liao, "A particle swarm optimization algorithm for hybrid flowshop scheduling with multiprocessor tasks," International Journal of Production Research, vol. 46(17), pp. 4655-70, 2008.
[7] R. Ruiz, FS. Serifoglu, T. Urlings, "Modeling realistic hybrid flexible flowshop scheduling problems," Computers & Operations Research, vol. 35(4), pp. 1151-75, 2008.
[8] T. Sawik, "An exact approach for batch scheduling in flexible flow lines with limited intermediate buffers," Mathematical and Computer Modeling, vol. 36(4-5), pp. 461-71, 2002.
[9] H. Allaoui, A. Artiba, "Integrating simulation and optimization to schedule a hybrid flow shop with maintenance constraints," Computers and Industrial Engineering, vol. 47(4), pp. 431-50, 2004.
[10] JL. Cheng, Y. Karuno, H. Kise, "A shifting bottleneck approach for a parallel machine flowshop scheduling problem," Journal of the Operations Research Society of Japan, vol. 44(2), pp. 140-56, 2001.
[11] SC. Graves, "A review of production scheduling," Operations Research, vol. 29(4), pp. 646-75, 1981.
[12] A. Reisman, A. Kumar, J. Motwani, "Flowshop scheduling/sequencing research: a statistical review of the literature, 1952-1994," IEEE Transactions on Engineering Management, vol. 44(3), pp. 316-29, 1997.