Hybrid Flow Shop Scheduling Problems with Multiprocessor Tasks

Abstract:

Hybrid flow shop scheduling problems with multiprocessor tasks to minimize the makespan have been addressed and solved efficiently. Several approaches were used, including greedy methods and metaheuristics. In this paper, we proposed a mixed integer programming (MIP) model that can define explicitly and precisely the nature of a given problem. We also addressed a modified lower bound to obtain tighter bounds. Additionally, we propose different decoding methods and emphasize their importance in hybrid flow shop scheduling problems with multiprocessor tasks. By using existing test problems with n=5 in examining the proposed methods, many optimal solutions can be obtained as benchmarks for reference by the MIP model. Accordingly, the results are indicative of the influence of the decoding methods on the solutions to the hybrid flow shop problems with multiprocessor tasks.

• Periodical: Applied Mechanics and Materials (Volumes 110-116)
• Pages: 3914-3921
• DOI: https://doi.org/10.4028/www.scientific.net/AMM.110-116.3914
• Online since: October 2011
• Authors: Hui Mei Wang, Fuh Der Chou, Ful Chiang Wu, Meei Yuh Ku
• Keywords: Hybrid Flow Shop, Make Span, Multiprocessor Tasks

References

[1] C. Oğuz, M.F. Ercan, T.C.E. Cheng, and Y.F. Fung, Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop, European Journal of Operational Research, vol. 149, 2003, pp.390-403.

DOI: 10.1016/s0377-2217(02)00766-x

[2] K-C Ying and S-W Lin, Scheduling multistage hybrid flowshops with multiprocessor tasks by an effective heuristic, International of Journal Production Research, vol. 47, 2009, p.35253538.

DOI: 10.1080/00207540701871085

[3] C. Oğuz, Y. Zinder, V.H. Do, A. Janiak, and M. Lichtenstein, Hybrid flow-shop scheduling problems with multiprocessor task systems, European Journal of Operational Research, vol. 152, 2004, pp.115-131.

DOI: 10.1016/s0377-2217(02)00644-6

[4] C. Oğuz and M.F. Ercan, A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks, Journal of Scheduling, vol. 8, 2005, pp.323-351.

DOI: 10.1007/s10951-005-1640-y

[5] K-C Ying and S-W Lin, Multiprocessor task scheduling in multistage hybrid flow-shops: an ant colony system approach, International Journal of Production Research, vol. 44, 2006, pp.3161-3177.

DOI: 10.1080/00207540500536939

[6] F.S. Serifoglu and G. Ulusoy, Multiprocessor task scheduling in multistage hybrid flow-shops: A genetic algorithm approach, Journal of the Operational Research Society, vol. 55, 2004, pp.504-512.

DOI: 10.1057/palgrave.jors.2601716

[7] C-T Tseng and C-J Liao, A particle swarm optimization algorithm for hybrid flow-shop scheduling with multiprocessor tasks, International Journal of Production Research, vol. 46, 2008, pp.4655-4670.

DOI: 10.1080/00207540701294627

[8] C. Kahraman, O. Engin, I. Kaya, R.E. Ozturk, Multiprocessor task scheduling in multistage hybrid flow-shops: A parallel greedy algorithm approach, Applied Soft Computing, 2010, doi: 10. 1016/j. asoc. 2010. 03. 08.

DOI: 10.1016/j.asoc.2010.03.008

[9] A. Jouglet, C. Oğuz, and M. Sevaux, Hybrid flow-shop: a memetic algorithm using constraintbased scheduling for efficient search, Journal of Mathematical Modeling and Algorithms, vol. 8, 2009, pp.271-292.

DOI: 10.1007/s10852-008-9101-1

[10] H. -M. Wang, F. -D. Chou, F. -C. Wu, A simulated annealing for hybrid flow shop scheduling with multiprocessor tasks to minimize makespan, International Journal of Advanced Manufacturing Technology, 2010, doi 10. 1007/s00170-010-2868-z. Table 1 : The results for problems with n=5 from Oğuz and Ercan [4] Type A Type B (n, k) No. LB newLB MIP Earlier solutions This paper Best LB newLB MIP Earlier solutions This paper Best (5, 2) 1 337 337 337* 337* 337* 337* 162 179 225* 225* 225* 225.

DOI: 10.1007/s00170-010-2868-z

[2] 199 199 256* 256* 256* 256* 173 190 193* 193* 193* 193.

[3] 261 262 308* 308* 308* 308* 236 280 285* 285* 285* 285.

[4] 201 262 282* 282* 282* 282* 190 190 278* 278* 278* 278.

[5] 267 267 267* 267* 267* 267* 261 289 316* 316* 316* 316.

DOI: 10.1515/9783110335293.267

[6] 184 184 184* 184* 184* 184* 172 172 248* 248* 264 248.

DOI: 10.1037/13015-008

[7] 157 174 174* 177 174* 174* 287 288 343* 343* 343* 343.

[8] 315 315 315* 315* 315* 315* 162 179 225* 225* 225* 225.

DOI: 10.1093/nq/s7-ix.225.315c

[9] 203 226 241* 241* 241* 241* 141 173 201* 201* 201* 201.

[10] 235 281 306* 306* 306* 306* 171 191 221* 221* 221* 221* (5, 5) 1 404 430 439* 451 445 439* 370 370 464 464 464 464.

DOI: 10.1136/bmj.306.6875.464

[2] 403 420 522* 522* 522* 522* 306 325 375 375 389 375.

[3] 440 477 519* 519* 519* 519* 338 346 400* 400* 400* 400.

[4] 374 374 499* 503 503 499* 281 294 354 356 356 354.

[5] 458 458 499* 499* 499* 499* 341 341 449* 449* 449* 449.

DOI: 10.1017/9781108689687.010

[6] 355 371 449* 449* 449* 449* 369 386 470 470 470 470.

DOI: 10.1515/9783110432916-005

[7] 272 272 320* 320* 320* 320* 377 392 517 518 518 517.

[8] 440 440 472* 482 472* 472* 253 310 342 342 342 342.

[9] 359 359 445* 445* 459 445* 313 346 382* 406 404 382.

[10] 419 437 502* 502* 502* 502* 310 310 431* 431* 431* 431* (5, 8) 1 576 576 607* 644 607* 607* 527 540 612 612 612 612.

DOI: 10.1038/nj7008-612c

[2] 513 513 609* 629 625 609* 586 586 635 635 635 635.

[3] 529 529 550* 554 566 550* 559 600 644 644 644 644.

[4] 542 542 663* 695 667 663* 516 588 588* 588* 588* 588.

[5] 500 569 616 646 616 616 522 522 620* 645 645 620.

[6] 533 551 597* 624 624 597* 527 540 612 612 612 612.

[7] 474 474 583 606 583 583 471 488 579* 601 588 579.

[8] 621 621 686* 686* 686* 686* 432 443 472 484 484 472.

[9] 539 539 656* 656* 656* 656* 532 562 638 654 654 638.

[10] 524 553 600* 607 607 600* 511 511 599 599 599 599.