Naslov
Some improvements in a cutting plane/branch and bound algorithm

Autori
Šorić, Kristina

Vrsta, podvrsta i kategorija rada
Sažeci sa skupova, sažetak, znanstveni

Izvornik
7th International Conference on Operational Research / Scitovski, Rudolf ; Hunjak, Tihomir - Osijek : Hrvatsko društvo za operacijska istraživanja (CRORS), 1998, 24-25

Skup
7th International Conference on Operational Research KOI'98

Mjesto i datum
Rovinj, Hrvatska, 30.09.1998. - 02.10.1998

Vrsta sudjelovanja
Predavanje

Vrsta recenzije
Nije recenziran

Ključne riječi
single machine scheduling; mixed 0-1 programming problem; valid inequalities; cutting plane/branch and bound algorithm

Sažetak
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

Izvorni jezik
Engleski

Znanstvena područja
Ekonomija

POVEZANOST RADA