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

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.

Authors:

• Bita Tadayon
• Nasser Salmasi

Keywords:

• flexible flowshop scheduling
• group processing
• machine eligibility constraint
• mathematical modeling.

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.