Title: Parallel Branch & Bound Algorithm for Makespan Optimal Scheduling in Flow Shops With Multiple Processors
Abstract: The term flow shop with multiple processors (FSMP) or hybrid flow shop characterizes a generalization of the flow shop with one or more identical machines at any processing stage. A scheduling algorithm for this kind of production facility consists of allocating the jobs to the machines at each stage and, for each machine, sequencing the allocated jobs. Possible objectives of job scheduling can be minimzing the makespan, the mean flow time, or any other regular measure of performance. The branch & bound algorithm presented in this paper minimizes the makespan, i. e. the maximum completion time required to process all jobs. Although the minimum makespan scheduling problem in the FSMP environment is NP-hard [3], this paper shows that instances of small to moderate scale can be solved in a reasonable amount of time. In particular, this is true if the computing performance of massively parallel systems is used to solve such problems.
Publication Year: 1998
Publication Date: 1998-01-01
Language: en
Type: book-chapter
Indexed In: ['crossref']
Access and Citation
Cited By Count: 3
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot