טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentHakim Shay
SubjectHigh Multiplicity Scheduling Problem with Flexible
Resources and General Precedence
DepartmentDepartment of Industrial Engineering and Management
Supervisors Professor Penn Michal
Mr. Masin Michael
Full Thesis textFull thesis text - English Version


Abstract

The High Multiplicity Scheduling Problem with Flexible Resources and General Precedence (MSP-FRGP) is a generalization of Job Shop scheduling (JS) and Resource-Constrained Project Scheduling Problems (RCPSP). In MSP-FRGP each operation, with known processing time, is processed by a single resource from its subset of resources that can execute it. The aim is to assign operations to resources and to order the operations on the resources so that the process will terminate in the smallest amount of time under the precedence relations and the resource availabilities constraints. MSP-FRGP is NP-hard since job shop is known to be NP-hard and it is a special case of MSP-FRGP. The problem has many practical applications in the industry, service applications and others.


We present the LP Synchronization Algorithm (LPSA) which is an LP-based polynomial time, in the size of the output, asymptotically optimal approximation scheme for the high multiplicity non-preemptive version of the problem, in which multiple instances of each operation are to be processed. Our LPSA is a dispatching rule for the MSP-FRGP that imitates the fractional solution of the linear relaxation of a Mixed Integer Linear Programing formulation of the problem. The solution obtained by LPSA satisfies the MSP-FRGP constraints. In addition, a heuristic method inspired by this approximation algorithm is presented and some numerical experiments are presented as well. As shown in the numerical experiments, our heuristic delivers solutions of quality as obtained by Masin and Raviv method and delivers substantially better solutions than the FSA method for standard job shop problems of moderate multiplicity.