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

Resumen

In this work we 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 work 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 than the total number of variables; (2) For some types of objectives (e.g., makespan minimizing), each incumbent solution allows for a problem reduction without eliminating any better solution; (3) Initial feasible solutions can be found, by means of an heuristic procedure, without great difficulty. The three mentioned characteristics allow for a modification in the traditional using of the branch-and-bound methods and, hence, increase the problem dimensions that could be dealt with at a reasonable computer effort. Computational experience on a broad set of real-life problems is reported.