Sequencing a hybrid two-stage flowshop with dedicated machines

2002/01/01 by Fouad Riane, Abdelhakim Artiba, Salah E. Elmaghraby · 3 citations
Engineering · #Scheduling and Optimization Algorithms #Assembly Line Balancing Optimization #Advanced Manufacturing and Logistics Optimization

paper · doi:10.1080/00207540210159536

Abstract

We treat the n -job, two-stage hybrid flowshop problem with one machine in the first stage and two different machines in parallel in the second stage. The objective is to minimize the makespan. We demonstrate that the problem is NP-complete. We formulate a dynamic program, which is beyond our grasp for problems of more than 15 jobs. Our search for heuristic approaches led to the adoption of the Johnson sequence, which motivated two of the three approaches: dynamic programming and sequence-and-merge. The third approach, the greedy heuristic, was included as example of an elementary heuristic.

Cited by

• A new complexity proof for the two-stage hybrid flow shop scheduling problem with dedicated machines
• Two-stage flow shop scheduling with dedicated machines
• Review and classification of hybrid flow shop scheduling problems from a production system and a solutions procedure perspective

Related

• A new complexity proof for the two-stage hybrid flow shop scheduling problem with dedicated machines
• Two-stage flow shop scheduling with dedicated machines
• Exploiting Promising Sub-Sequences of Jobs to solve the No-Wait Flowshop Scheduling Problem
• Resource-dependent process times in hybrid flexible flowshops
• A Novel Hybrid Algorithm for Permutation Flow Shop Scheduling