Scheduling parallel processors: An integer linear programming based heuristic for minimizing setup time. (English) Zbl 0621.90039

The authors consider the scheduling of parallel processors in a make-to- stock environment with sequence setup costs. A new algorithm which formulates a series of 0-1 integer subproblems is proposed and contrasted with an earlier formulation by Dearing and Henderson. Parallels between the subproblem formulations and generalized networks are discussed. The efficiency and quality of the solutions provided is tested using previously published data for a loom assignment problem. The heuristic solution is evaluated against the optimal integer linear programming solution, and a rounded linear programming approximation to the optimal solution for several sample problems. Results indicate that the heuristic is efficient, provides near optimal solutions to production planning problems and requires significantly less computing capability than previously reported linear programming and integer linear programming approaches.
Reviewer: M.Savelsbergh


90B35 Deterministic scheduling theory in operations research
65K05 Numerical mathematical programming methods
90B30 Production models
90C10 Integer programming
90C05 Linear programming
Full Text: DOI