Naslov
Algoritmi ed euristiche per il problema di sequenziamento dei lavori su macchina singola
(Exact Algorithms and Heuristics for a Single Machine Scheduling Problem)

Autori
Šorić, Kristina

Vrsta, podvrsta i kategorija rada
Ocjenski radovi, doktorska disertacija

Fakultet
Dipartimento di matematica pura ed applicata

Mjesto
Padova, Italija

Datum
30.09

Godina
1997

Stranica
114

Mentor
Serafini, Paolo

Ključne riječi
algoritmo; euristica; sequenziamento dei lavori; macchina singola
(algorithm; heuristics; sequencing; scheduling; single machine)

Sažetak
Production planning and scheduling systems have a significant impact on the performance of manufacturing operations and, hence, have been the subject of extensive research. A question that has received considerable attention is how to develop a production scheduling for a facility that processes one product at a time and incurs a changeover cost whenever it switches from the manufacture of one product to another. Even though this scheduling problem is a simplified representation of the actual planning problem, it has become a prototypical model in the operations management literature because it captures the major cost tradeoffs to be made in developing a schedule in numerous contexts. In all these researches, pure 0-1 and integer programming problems are favorite topics for theoretical research and experimentation in operations research. Mixed integer programming problems have received less attention. This situation is unfortunate, since most applications involving integer variables are mixed integer programs and often mixed 0-1 programs. For the last 25 years the only general approach for solving this class of very hard problems has been branch-and-bound, based upon linear programming. In this work, an alternative approach is proposed. Cutting planes are used to reformulate and solve the problem using valid inequalities as cutting planes. Assuming the finite horizont, the polyhedral structure of the mixed 0-1 programming formulation of a single machine scheduling problem is studied. The objective is to minimize the work backlog. Also, some separation algorithms are proposed that give the violated inequalities. After detecting the violated inequalities, they can be used as cutting planes to strengthen the mixed 0-1 formulation of the problem. Two versions of this problem are studied. In the first one, the objective of minimizing the average workbacklog in the system is transformed in the objective of minimizing the sum of weighted start times. In the second one, the objective of minimizing the makespan is proposed. Besides, in this work two heuristics for solving the problem with objective to minimize the work backolg in the system are proposed. Applying the first one, the better upper bound on the total workbacklog than those available in the literature is obtained. Using the second one, the problem is transformed to a 0-1 programming problem which is a favorite topic for researches.

Izvorni jezik
Ita

Znanstvena područja
Ekonomija

POVEZANOST RADA