A Precedence Graph Algorithm for the Shop Scheduling Problem

Abstract

This paper is concerned with the development of a precedence graph algorithm for solving certain combinatorial problems. This algorithm is applied mainly to job-shop scheduling problems; however, the extension of its applicability can be demonstrated by considering project scheduling, travelling salesman and explosion problems. The algorithm employs linear graphs to construct the quantified precedence matrix, a powerful criterion to resolve the conflict between the tied operations, and the use of a quasi-Boolean procedure to evaluate the obtained sequence.

Considerable experimentation is conducted to evaluate the performance of the algorithm. Significant results pertaining to the quality of solution, the computation time and the number of iterations and conflicts encountered in obtaining a solution are given.