engleski

A cutting plane algorithm for a single machine scheduling problem

Each of N part types (production families or items) is to be processed on a single machine. The part types arrive into buffer in front of the machine at every unit of time at specified rates. The machine can process a finite number of part types at specified rates, but only one part type can be processed at any given time. Each switch from one type to another requires setup time. The objective is to schedule the part types in the snese that the required demand is met and the average work backlog in the system is minimal. Assuming a finite horizon, we define this problem as a mixed 0-1 programming problem. In order to strengthen the formulation, we consider its LP relaxation in an enlarged space of variables. By projecting this polyhedron into the space on the original variables we obtain new valid inequalities for the original problem that are then used as cutting planes in a cutting plane/branch and bound algorithm. At the end we report some computational results that have the objective of empirically estimating the reduction in the integrality gap (the gap between the optimal values of the original problem and its linear programming relaxation). Also, we give and compare the CPU times of the cutting plane/branch and bound algorithm proposed in this paper and the branch and bound algorithm applied directly to the original problem.

single machine scheduling problem ; mixed 0-1 programming problem ; valid inequalities ; branch and bound/cutting plane algorithm

nije evidentirano