An analysis tableau and algorithm for flow-shop makespan minimization

Abstract

An analysis tableau suitable for investigating flow-shop attributes is presented in detail 1. Geometric properties, inherent within the tableau, are employed using graph theory concepts in developing a heuristic algorithm for makespan minimization. Computer implementation of this algorithm revealed promising results when compared with several state of-the-art heuristic algorithms.

The tableau can be conceived as a three-dimensional matrix with the first two indices consisting of job numbers (rows) and machine numbers (columns). The third index is used to distinguish processing times and accumulative makespan values. The matrix is as informative as the Gantt Chart and yet offers additional advantages when considering the flow-shop problem, such as:

1. Provides an instructional tableau format which is organized, systematic, and directly amenable for hand or digital-computer calculations, 2. Depicts computational contingencies for accumulative makespan values (individual job due-dates as well as flow-shop makespan), 3. Depicts machine and job dominances, 4. Allows for sensitivity analysis {effects of processing times upon accumulative makespan values), 5. Identifies critical-processing times, 6. Reveals where external improvements would be cost effective, 7. Representation is easily modified for job permutations, 8. Representation is not limited to small flow-shops (low number of jobs and/or machines), 9. Allows for additional insight when investigating heuristics, and 10. Can be used as an instructional- , managerial- , and/or a research- tool for analyzing flow-shop attributes.

The tableau allows a macro-sensitivity analysis of the entire flow-shop. Specifically, the maximum increase in various processing times, without increasing the flow-shop make span, can be determined. This analysis utilizes graphical representations (segments and nodes) in matrix (tableau). Graphical representation is a convenient means for preserving the history of how each accumulative makespan value was mathematically generated. Concepts such as: partial-paths and critical-paths in conjunction with regions-of-influence are discussed in order to determine the interrelationship between the accumulative makespan values and the processing times, for a specific job sequence.