An Integer Linear Programming Model for Machine Scheduling

摘要

In this paper we offer an integer linear programming model which is capable of characterizing the problem. We feel it is of interest to present the model as (i) it exhibits there is a single model that encompasses a wide variety of machine scheduling situations, (ii) the linear format establishes, the existence of a finite algorithm which monotonically seeks an optimum solution to such sequencing problems, (iii) although the model is new of very limited computational interest, future developments in integer linear programming and methods for efficiently handling ''secondary constraints" may make numerical solutions of particular problems possible, and (IV) there is an indication of the possibility of constructing special algorithms to exploit the structure of certain of the “classical” scheduling problems.