Document Type : Article

**Author**

Babol Noshirvani University of Technology; Babol; Iran

**Abstract**

This research addresses scheduling problem of *n* jobs on a Hybrid Flow Shop (HFS) with unrelated parallel machines in each stage. A monolithic mixed integer linear programming (MILP) model is presented to minimize the maximum completion time (makespan). As the research problem is shown to be strongly NP-hard, a Lagrangian relaxation (LR) algorithm is developed to handle the HFS scheduling problem. We design two approaches, simplification of subproblems and dominance rules, to solve the subproblems which are generated in each iteration. For evaluation purposes, numerical experiments with small and large size problems are randomly generated with up to 50 jobs and four stages. The experimental results show that the Lagrangian relaxation approaches outperform the MILP model with respect to CPU time. Furthermore, from the results, it can be conclude that the simplification of subproblems shows slightly better solutions in comparison with dominance rules to solve the subproblems.

**Keywords**

**Main Subjects**

1. Liao, C.J., Tjandradjaja, E., and Chung, T.P. An

approach using particle swarm optimization and bottleneck

heuristic to solve hybrid

ow shop scheduling

problem", Appl. Soft Comput., 12, pp. 1755-1764

(2012).

2. Agnetis, L., Pacici, A., Rossi, F., Lucertini, M.,

Nicoletti, S., and Nicolo, F. Scheduling of

exible

ow

shop in an automobile assembly plant", Eur. J. Oper.

Res., 97(2), pp. 348- 362 (1997).

3. Adler, L., Fraiman, N., Kobacker, E., Pinedo, M.,

Plotnico, J.C., and Wu, T.P. BPSS: a scheduling

support system for the packaging industry", Oper. Res,

41, pp. 641-648 (1993).

4. Shahvari, O., Salmasi, N., Logendran, L., and Abbasi,

B. An ecient tabu search algorithm for

exible

ow

shop sequence dependent group scheduling problems",

Int. J. Prod. Res., 50, 15, pp. 4237-4254 (2012).

5. Moursli, O. and Pochet, Y. A branch and- bound

algorithm for the hybrid

owshop", Int. J. Prod. Econ.,

64, pp. 113-25 (2000).

6. Liu, C.Y. and Chang, S.C. Scheduling

exible

ow

shops with sequence-dependent setup eects", IEEE

Transaction on Robotics and Automation, 16(4), pp.

408-419 (2000).

7. Fattahi, P., Hosseini, S.M.H., Jolai, F., and Tavakkoli-

Moghaddam, R.A. Branch and bound algorithm for

hybrid

ow shop scheduling problem with setup time

and assembly operations", Appl. Math. Model, 38, pp.

119-134 (2014).

8. Riane, F., Artibas, A., and Elmaghraby, S.E. A hybrid

three stage

ow shop problem: ecient heuristics

to minimize makespan", Eur. J. Oper. Res., 109, pp.

321-329 (1998).

E. Asadi-Gangraj/Scientia Iranica, Transactions E: Industrial Engineering 25 (2018) 3765{3775 3775

9. Linn, R. and Zhang, W. Hybrid

ow shop scheduling:

a survey", Comput. Ind. Eng., 37, pp. 57-61 (1999).

10. Marichelvam, M.K., Prabaharan, T., Yang, X., and

Geetha, M. Solving hybrid

ow shop scheduling

problems using bat algorithm", Int. J. Logist Econ

Glob, 5(1), pp. 15-29 (2013).

11. Jolai, F., Ase, H., Rabiee, M., and Ramezani, P.

Bi-objective simulated annealing approaches for nowait

two-stage

exible

ow shop scheduling problem",

Scientia Iranica, 20(3), pp. 861-872 (2013).

12. Marichelvam, M.K., Prabaharanb, T., and Yang, X.S.

Improved cuckoo search algorithm for hybrid

ow

shop scheduling problems to minimize makespan",

Appl. Soft Comput., 19, pp. 93-101 (2014).

13. Jolai, F., Tavakkoli-Moghaddam, R., Rabiee, M., and

Gheisariha, E. An enhanced invasive weed optimization

for makespan minimization in a

exible fowshop

scheduling problem", Scientia Iranica, 21(3), pp. 1007-

1020 (2014).

14. Tang, L., Xuan, H., and Liu, J. A new Lagrangian

relaxation algorithm for hybrid

owshop scheduling to

minimize total weighted completion time", Comput.

Oper. Res., 33, pp. 3344-3359 (2006).

15. Liu, G.D. and Luh, P.B. Scheduling permutation

ow shops using the Lagrangian relaxation technique",

Ann. Oper. Res., 70, pp. 171-89 (1997).

16. Luh, P.B. and Hoitomt, D.J. Scheduling of manufacturing

systems using the Lagrangian relaxation

technique", IEEE Transaction on Automatic Control,

38(7), pp. 1066-1079 (1993).

17. Chang, S.C., Liao, D.Y., and Hsieh, F.S. Scheduling

exible

ow shops of no setup cost by a Lagrangian

relaxation and network

ow approach", Interactional

Conference on Robotics and Automation (1991).

18. Irohara, T. Lagrangian relaxation algorithms for

hybrid

ow-shop scheduling problems with limited

buers", Biomed. Fuzzy Hum. Sci., 15(1), pp. 21-28

(2010).

19. Sun, X. and Noble, J.S. An approach to job

shop scheduling with sequence- dependent setups", J.

Manuf. Syst., 18(6), 416-430 (1999).

20. Emami, S., Sabbagh, M., and Moslehi, Gh. A Lagrangian

relaxation algorithm for order acceptance and

scheduling problem: a globalized robust optimisation

approach", Int. J. Comput. Integ. Manuf., 29(5), pp.

535-560 (2016). DOI: 10.1080/0951192X.2015.1068452.

21. Shishebori, D., Youse Babadi, A., and Noormohammadzadeh,

Z. A Lagrangian relaxation approach to

fuzzy robust multi-objective facility location network

design problem", Scientia Iranica, 25(3), pp. 1750-

1767 (2018).

22. Nahavandi, N. and Asadi Gangraj, E. A new lower

bound foe

exible

ow shop scheduling problem with

unrelated parallel machines", Int. J. Ind. Eng. Prod.

Res., 25(1), pp. 65-70 (2014).

23. Augusto, V., Xie, X., and Perdomo, V. Operating

theatre scheduling using Lagrangian relaxation", Eur.

J. Ind. Eng., 2(2), pp. 172-189 (2008).

24. Smith, J.C. and Sonuc, S.B. An introduction to

integer and large-scale linear optimization, wireless

network design", Int. Ser. in Oper. Res. Manag. Sci.,

158, pp. 65-97 (2011).

25. Lenstra, J.K., Rinnooy Kan, A.H.G., and Bruker, P.

Complexity of machine scheduling problems", Annals

of Discrete Mathematics, 1, pp. 343-62 (1977).

26. Salmasi N., Logendran, R., and Skandari, M.R. Total

FLow time minimization in a

ow shop sequencedependent

group scheduling problem", Computers &

Operations Research, 37, pp. 199-212 (2010).

27. Polyak, B.T. Introduction to optimization", Optimization

Software, Inc., New York (1987).

Transactions on Industrial Engineering (E)

November and December 2018Pages 3765-3775