Online scheduling & project scheduling
Paulus, Jacob Jan (2009) Online scheduling & project scheduling. thesis.

PDF
1MB 
Abstract:  This thesis presents new and improved scheduling algorithms for a number of scheduling problems. The first part of the thesis deals with two onlinelist scheduling problems, both with the objective to minimize the makespan. In these problems, the jobs arrive one by one and the decision maker has to irrevocably schedule the arriving job before the next job becomes known. In the second part, a new solution methodology for the timeconstrained project scheduling problem is developed, and a decomposition method for the timeconstrained project scheduling problem with adjacent resources is presented. The first online problem considered, is onlinelist scheduling of parallel jobs with the objective to minimize the makespan, and some of its special cases. In these problems there is a set of identical machines to process a set of parallel jobs. In contrast to the jobs in classical machine scheduling problems, parallel jobs require a number of machines simultaneously for their processing. For this problem, a 6.6623competitive online algorithm and a lower bound of 2.43 on the competitive ratio of any online algorithm are presented. Both results are also applicable to the online orthogonal strip packing problem. Besides the tight lower bound of 2 on the competitive ratio of the problem with exactly two machines, also improved online algorithms for the case with exactly three machines and the semionline case where jobs appear in nonincreasing order of machine requirement are given. The second online problem covered, is the onlinelist batch scheduling problem with the objective to minimize the makespan. In this problem, there is one machine with a given batch capacity that processes the jobs in a parallel batching manner. Parallel batching means that all jobs in one batch receive processing at the same time. A complete classification of the tractability of this online problem is given; with respect to the competitive ratio an optimal online algorithm for any capacity of the batching machine is presented. The second part of this thesis presents a new scheduling approach for scheduling with strict deadlines on the jobs. This approach is applied to the timeconstrained project scheduling problem. In this problem there is a set of resources, each with its own capacity, and a set of jobs requiring a specific amount of each of the resources during its processing. Additionally, there are precedence relations between the jobs and each job has a deadline. To be able to meet the deadlines in this problem, it is possible to work in overtime or hire additional capacity in regular time or overtime. In the developed two stage heuristic, the key step lies in the first stage where partial schedules are constructed. In these partial schedules, jobs may be scheduled for a shorter duration than required. The goal is to create a schedule in which the usage of overtime and extra hiring is low. The proposed method tries to prevent a pile up of costs toward the deadlines by including all jobs partially before addressing the bottlenecks. Computational tests are preformed on modified resourceconstrained project scheduling benchmark instances. Many instances are solved to optimality, and lead only to a small increase of costs if the deadline is substantially decreased. Finally, the timeconstrained project scheduling problem is considered under the addition of a new type of constraint, namely an adjacent resource constraint. An adjacent resource constraint requires that the units of the resource assigned to a job have to be adjacent. On top of that, adjacent resources are not required by single jobs, but by job groups. The additional complexity introduced by adding adjacent resources to the project scheduling problem, plays an important role both for the computational tractability and the algorithm design when solving the problem. The developed decomposition method separates the adjacent resource assignment from the rest of the scheduling problem. Once the job groups are assigned to the adjacent resource, the scheduling of the jobs can be done without considering the adjacent resource. The presented decomposition method forms a first promising approach for the timeconstrained project scheduling problem with adjacent resources and may form a good basis to develop more elaborated methods. 
Item Type:  Thesis 
Research Group:  
Link to this item:  http://purl.utwente.nl/publications/60453 
Official URL:  http://dx.doi.org/10.3990/1.9789036527538 
Export this item as:  BibTeX EndNote HTML Citation Reference Manager 
Repository Staff Only: item control page