Research Reports from the Department of Operations
Document Type
Report
Publication Date
1-1-1972
Abstract
This research considers the most general type of "network" flow shop in which jobs pass through each of m > 2 stages, where the ith stage is composed of ni ≥ 1 identical processors. Jobs are processed on one processor at each stage in ascending order of stage numbers and the objective is minimization of makespan. The class of shops considered includes those where in-process inventory is prohibited and the sequence of jobs processed on a particular processor is required to be a subsequence of the jobs entering the shop; without these additional constraints, algorithmic solutions are available only for the so-called "simple" flow shop, i.e., ni = 1 for all i. Originally designed for the scheduling of nylon polymerization, the algorithm presented here for this special class of scheduling problems has numerous applications, especially in the chemical processes and petro-chemical production areas. An algorithm is first given for the case ni = 1, i = 1,2,...,m, by using a model of the Traveling Salesman Problem type. Modeled as a directed network, the more general problem is solved via a branch-and-bound methodology; Dynamic Programming is employed to solve an imbedded subproblem. Several useful extensions are introduced into the algorithm. These include positive transfer, setup, and teardown times, restricted transfer between stages, restricted job/processor assignments, stochastic processing times, arrival dates, and due dates.
Keywords
Operations research, Dynamic programming, Mathematical optimization, Industrial engineering, Algorithms, Production scheduling, Branch and bound algorithms, Chemical processes--Mathematical models
Publication Title
Technical Memorandums from the Department of Operations, School of Management, Case Western Reserve University
Issue
Technical memorandum no. 255
Rights
This work is in the public domain and may be freely downloaded for personal or academic use
Recommended Citation
Salvador, Michael S., "A Solution to a Special Class of Flow Shop Scheduling Problems" (1972). Research Reports from the Department of Operations. 528.
https://commons.case.edu/wsom-ops-reports/528