zbMATH — the first resource for mathematics

A cutting plane algorithm for the single machine scheduling problem with release times. (English) Zbl 0768.90040
Combinatorial optimization. New frontiers in theory and practice, Proc. NATO ASI, Ankara/Turkey 1990, NATO ASI Ser., Ser. F 82, 63-83 (1992).
[For the entire collection see Zbl 0752.00053.]
The authors develop a mixed integer programming formulation for a single machine scheduling problem with job release times. The objective function analysed is the weighted sum of job starting times. As a relaxation the associated model with identical release times is used and the authors provide valid inequalities for the general problem.
The authors present a solution approach based on this formulation using a combination of cutting planes and branch-and-bound. The computational results of a first implementation for problems with up to 30 jobs indicate that the efficiency of the approach dramatically decreases when the problem size increases. But the authors mention some improvements to overcome this disadvantage of the present algorithm.

90B35 Deterministic scheduling theory in operations research
90C11 Mixed integer programming
90-08 Computational methods for problems pertaining to operations research and mathematical programming