Strategies for LP-based solving a general class of scheduling problems

In this work the authors describe some strategies that have been proved to be very efficient for solving the following type of scheduling problems: Assume a set of jobs is to be performed along a planning horizon by selecting one from several alternatives for doing so. Besides selecting the alternative for each job, the target consists of choosing the periods at which each component of the job will be done, such that a set of scheduling and technological constraints is satisfied. The problem is formulated as a large-scale pure 0-1 model. Three facts are observed: (1) The number of variables with nonzero value at each feasible solution is much smaller that the total number of variables; (2) for some types of objectives (e.g., makespan minimizing), each incumbent solution allows for a problem’s reduction without eliminating any better solution; (3) initial feasible solutions can be found, by means of an heuristic procedure, without great difficulty. The above three characteristics allow for a modification on the traditional using of the branch-and-bound methods and, hence, increase the problem’s dimensions that could be dealt with at a reasonable computing effort. Computational experience on a broad set of real-life problems is reported.