The Block Structure of Linear Programming Solutions to a Single Machine Scheduling Problem

This paper investigates the structure of linear programming solutions to a single machine scheduling problem. We prove an extension of Smith’s rule, a property of schedules that are vertex solutions to the underlying feasible region and perform some computational experiments. The presented results will show the relevance of the socalled block structure in these linear programming solutions.