engleski

Some computational results for a class of real time scheduling policies

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. 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 find a processing order which minimizes the weighted sum of start times. The problem is defined as a mixed 0-1 programming problem. In order to strengthen 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. The computational results from some earlier works, showed that the resulted valid inequalities were effective in reducing the integrality gap and CPU time.

Mixed 0-1 programming; LP relaxation; new valid inequalities; cutting plane; branch and bound

nije evidentirano