Accession Number:

AD0657193

Title:

ON SOME SEQUENCING PROBLEMS

Descriptive Note:

Research rept.

Corporate Author:

CARNEGIE INST OF TECH PITTSBURGH PA GRADUATE SCHOOL OF INDUSTRIAL ADMINISTRATION

Personal Author(s):

Report Date:

1967-07-01

Pagination or Media Count:

44.0

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.

Subject Categories:

  • Operations Research
  • Manufacturing and Industrial Engineering and Control of Production Systems

Distribution Statement:

APPROVED FOR PUBLIC RELEASE