ON SOME SEQUENCING PROBLEMS
Abstract
The (mxn) sequencing problem may be characterized as follows: There are m machines which can produce a piece consisting of n parts. Each part has a determined order in which it is processed through the machines. It is assumed that each machine cannot deal with more than one part at a time and that the processing required for each part can be accomplished only on one machine. The problem is to find the best production plan consisting in sequencing the different parts so as to make the whole amount of time from the beginning of work till the piece is completed the shortest possible. Such a plan is called an optimum one. In the first 4 sections of this paper, the problem (2xn) is solved for the (2xn) case in which the order in which parts come on the machine is not constrained by futher assumptions. The remainder of the paper then takes up: i, the (3xn) problem of Bellman-Johnson (viz. the technological processing order through the machine is the same for all parts), for several new special cases; ii, the 2xn problem of sequencing when delay times must also be considered; and, iii, some properties of an approximating method for solving (mxn) problems including a delineation of cases when the approximating method will yield optimal solutions.
Document Details
- Document Type
- Technical Report
- Publication Date
- Jul 01, 1967
- Accession Number
- AD0657193
Entities
People
- Wlodzimierz Szwarc
Organizations
- Carnegie Institute of Technology