engleski

A Cutting Plane Algoritm for Single Machine Scheduling Problem

A model for real time control of flexible manufacturing system is considered. In this model, a 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 swithch 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 the finite horizont, we define this problem as mixed 0-1 programming problem. In order to strength the formulation, we consider its LP relaxation in an enlarged space of variables. By projecting this polyhedra into the space of 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. We also give a polynomial separation algorithm for the resulting polythope. At the end we report some computational results that have the objective to estimate empirically the reduction in the integrality gap (the gap between the optimal value of the original problem and its LP relaxation), both before and after addition of valid inequalities. Also, we give and compare the CPU times of the cutting plane/branch and bound algorithm applied directly to the original problem. We solved five 6-jobs instances of the proble, five 8-jobs instances and five 10-jobs instances. The results show that the resulted valid inequalities are effective in reducing the integrality gap for all the instances considered. In all cases, these inequalities reduced the gap for 50%. It comes out that for smaller problem instances it is better to use branch and bound directly after solving the LP relaxation of the problem, with no aditional constraints added because the CPU processing time is shorter than the CPU processing time for the cutting plane algorithm. But, as the number of jobs increases, the difference between these solution times increases too and it comes out that it is better to use cutting plane/branch and bound procedure. For 8-jobs instances the CPU time is reduced for approximately 13% and for 10-jobs instances 44%.

single machine scheduling; mixed 0-1 programming problem; valid inequalities; cutting plane algorithm

nije evidentirano