Developing a Lagrangian Relaxation Method for Flexible Flowshop Scheduling Problem

Document Type : Research Paper

Authors

1 Babol University of Technology

2 Tarbiat Modares University

Abstract

Flexible flow shop scheduling problem (FFS) with unrelated parallel machines contains sequencing in flow shop where, at any stage, there exists one or more unrelated parallel machines. The objective consists of minimizing the maximum completion time. A new Lagrangian relaxation (LR) method is developed to solve the candidate problem. To solve the sub-problems in LR, we use two approaches such as, simplicity of sub-problems and dominance rules. The results show that the both approaches can achieve the near-optimal solution in reasonable time; but there is no significant difference between them. On the other side, simplicity of sub-problems can achieve the solution in reasonable time.

Keywords

Main Subjects

References

[1]   Quadt, D., Kuhn, H. (2007). A taxonomy of flexible flow line scheduling procedures. European Journal of Operational Research, 178:686–698.
[2]   Shahvaria, O., Salmasi, N., Logendran, L., Abbasi, B. (2012). An efficient tabu search algorithm for flexible flow shop sequence-dependent group scheduling problems, International Journal of Production Research, 50(15): 4237–4254.
[3]   Wittrock, R.J. (1988). An Adaptable Scheduling Algorithm for Flexible Flow Lines. Operations Research, 36: 445–453.
[4]   Agnetis, L., Pacifici, A., Rossi, F., Lucertini, M., Nicoletti, S., Nicolo, F. (1997). Scheduling of Flexible Flow Shop in an Automobile Assembly Plant. European Journal of Operation Research, 97(2):348–362.
[5]   Adler, L., Fraiman, N., Kobacker, E., Pinedo, M., Plotnicoff, J.C., Wu, T.P. (1993). BPSS: a Scheduling Support System for the Packaging Industry. Operations Research, 41: 641–648.
[6]   Moursli, O., Pochet, Y. (2000). A branch-and-bound algorithm for the hybrid flowshop, International Journal of Production Economics, 64: 113–25.
[7]   Yang Y., Kreipl, S., Pinedo, M. (2000). Heuristics for minimizing total weighted tardiness in flexible flowshops, Journal of Scheduling, 3: 71–88.
[8]   Fattahi, P., Hosseini, S.M.H., Jolai, F., Tavakkoli-Moghaddam, R. (2014). A branch and bound algorithm for hybrid flow shop scheduling problem with setup time and assembly operations, Applied Mathematical Modelling, 38: 119–134;
[9]   Riane, F., Artibas, A., Elmaghraby, S.E. (1998). A hybrid three stage flow shop problem: efficient heuristics to minimize makespan, European Journal of Operations Research, 109: 321–329.
[10]    Linn, R., Zhang., W. (1999) Hybrid flow shop scheduling: a survey, Computers and Industrial Engineering, 37: 57–61.
[11]    Tang, L., Xuan, H., Liu, J. (2006). A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time, Computers & Operations Research 33: 3344–3359
[12]    Liu, G.D., Luh, P.B. (1997). Scheduling permutation flow shops using the Lagrangian relaxation technique. Annals of Operations Research, 70: 171–89.
[13]    Luh, P.B., Hoitomt, D.J. (1993). Scheduling of manufacturing systems using the Lagrangian relaxation technique, IEEE Transaction on Automatic Control, 38(7): 1066–1079.
[14]    Chang, S.C., Liao, D.Y., Hsieh, F.S (1991). Scheduling flexible flow shops of no setup cost by a lagrangian relaxation and network flow approach, Interactional Conference on Robotics and Automation.
[15]    Irohara, T. (2010). Lagrangian relaxation algorithms for hybrid flow-shop scheduling problems with limited buffers. Biomedical Soft Computing and Human Sciences, 15(1): 21-28.
[16]    Sun, X., Noble, J.S. (1999). An Approach to Job Shop Scheduling with Sequence-Dependent Setups. Journal of Manufacturing Systems, 18(6).
[17]    Liu, C.Y., Chang, S.C. (2000). Scheduling Flexible Flow Shops with Sequence-Dependent Setup Effects, IEEE transaction on robotics and automation, 16(4): 408-419.
[18]    Nahavandi, N., Asadi Gangraj, E. (2014). A New Lower Bound for Flexible Flow Shop Problem with unrelated parallel machines, International Journal of Industrial Engineering & Production Research, 25(1): 65-70.
[19]    Salmasi, N., Logendran, L., Skandari, M.R. (2010). Total flow time minimization in a flowshop sequence-dependent group scheduling problem, Computers & Operations Research 37: 199 – 212.
Journal of Industrial Engineering Research in Production Systems
Volume 3, Issue 6 - Serial Number 6
Fall and Winter 2016
February 2016
Pages 121-131

Files

Share

How to cite

Statistics