A cutting plane algorithm for a single machine scheduling problem

doi:10.1016/S0377-2217(99)00493-2

2000-12-01

PRE

Kristina Šorić *

DOI：10.1016/S0377-2217(99)00493-2

原文链接

原文求助

摘要

En 中文

Each of N part types (production families or items) is to be processed on a single machine. The part types arrive into the 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 sense 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 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 of 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. (C) 2000 Elsevier Science B.V. All rights reserved.

Keyword:

single machine scheduling

mixed 0-1 programming problem

valid inequalities

branch and bound/cutting plane algorithm