engleski

Some improvements in a cutting plane/branch and bound algorithm

Each of N part types (production falilies 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 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 processing order which minimizes the weighted sum of start times. The problem is defined as a mixed 0-1 programming problem. In order to stregthen 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. In some earlier work, we have given a polynomial separation algorithm and computational results. We solved five 6-jobs instances of the problem, five 8-jobs instances and five 10-jobs instances. The results showed that the resulted valid inequalities were effective in reducing the integrality gap for all the instances considered. In all cases, these inequalities reduced the gap for 50%. Also, for 8-jobs instances the CPU time is reduced for approximately 13% and for 10-jobs instances 44%. In this work, some new valid inequalities are added and the input parameters changed. This reduced the CPU time for approximately 70% regarding to original problem

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

nije evidentirano