Search

This paper reviews the flowshop-sequencing research since 1954 that has been devoted to the static deterministic case in which n jobs are to be processed through a shop in which the processing times at each stage are fixed. The paper then comments on NP-completeness, the selection of criteria for optimization, and the lack of applications of this work in industry. Finally, it draws some conclusions about the possible future of sequencing research and the lessons that this area's work has to teach the rest of operations research.

A flowshop sequencing problem having an ordered processing time matrix is defined. Job and machine characteristics resulting in processing time relationships that have logical and practical bases are discussed. An optimizing solution procedure for a special class of ordered matrix problem is presented along with proof of optimality.

In the past two decades researchers in the field of sequencing and scheduling have analyzed several priority dispatching rules through simulation techniques. This paper presents a summary of over 100 such rules, a list of many references that analyze them, and a classification scheme.

We consider an n job, one machine scheduling problem in which all jobs have a common due date. The objective is to determine the optimal value of this due date and an optimal sequence to minimize a total penalty function. This penalty function is based on the due date value and on the earliness or the lateness of each job in the selected sequence. We present a polynomial bound scheduling algorithm for the solution of this problem along with the proof of optimality, a numerical example and discuss some extensions.

The problem studied is that of two-machine job shop sequencing where some jobs are processed first on machine 1 and then on machine 2, while the remaining jobs are processed in the reverse order. The objective is to determine an ordered sequence which minimizes the total processing time, subject to some specified lag time constraints. A rule is given for determining two different sequences for the two machines which represent an optimal solution.