Scheduling with Capacities: Machines, Jobs, and Time


Student thesis: Doctoral Thesis

View graph of relations


Related Research Unit(s)


Awarding Institution
Award date29 Aug 2018


The rapid development of modern industry depends on effective organization and efficient utilization of information and resources. A good plan not only improves operational efficiency but also saves time. We work on the scheduling problem with capacities in different aspects.

Firstly, the widely studied topic in scheduling is about how to schedule the jobs with a fixed amount of machines in a highly efficient way, while the assessment of the efficiency is based on the weighted completion time of the jobs. We explore the worst cases of a greedy algorithm (Largest-Ratio-First algorithm) and investigate the structure of the worst cases. Based on the greedy algorithm, we propose a polynomial time approximation scheme (PTAS). Also we give a dynamic programming approach for a special case where the job weight is proportional to its processing time. The results in this category can be applied to both real machines such as high-performance computer clusters and the machines in production lines.

The second aspect of scheduling is about the precedence order of jobs or activities. We focus on the scenario where a special job must be triggered when a fixed amount of tasks have finished on a single machine, while the objective is to minimize the weighted completion time. Our main contribution is a fully polynomial time approximation scheme (FPTAS). This work has applications in machine maintenance where the special job can be regarded as the maintenance job.

At last, we focus on time-dependent periodic resources in scheduling where the resource is only effective within a fixed amount of time once being started, e.g. the machine runs in high precision for a certain period of time after being calibrated. In this calibration scheduling model, the major concern is how to allocate the minimum necessary calibrations on parallel machines so as to complete all jobs with respect to their timing constraints. We consider jobs of unit processing time and propose a dynamic programming approach, as well as a PTAS with resource augmentation of the machines. In addition, we consider another two variants on single machine with a limited budget of the number of calibrations that are allowed to be performed. In the first variant, we work on the objective of minimizing total weighted completion time.

In the second variant, we introduce time slot cost into the model in which each unit-time is associated with a certain cost and the objective is to minimize the total cost of the time slots that have been used to schedule jobs. For both variants, we give the optimal solution via dynamic programming approach.

    Research areas

  • scheduling, dynamic programming, approximation algorithm, PTAS, weighted completion time