You are here

Fixed job scheduling problem under spread time constraints


In a scheduling problem, a job is said to be fixed when its due date corresponds exactly to its release date plus its processing time. This work addresses the fixed job scheduling problem where processors are subject to spread time constraints, i.e., the amount of time spent between the starting time of the first job on a processor and the completion time of the last job on the same processor should not exceed a given duration. Existing exact approaches are tested on medium size instances. As large instances are clearly intractable with these approaches, a greedy heuristic and a grouping genetic algorithm are proposed. Computational results show the effectiveness of the proposed heuristics.

Problem description

The Fixed Job Scheduling problem (denoted FJS) is a particular case of interval scheduling problems: each job j has a weight wj , a ready time rj and a due date dj such that the job processing time is dj − rj. The weight is typically a measure of the gain earned by processing the corresponding job. These jobs are to be processed by parallel identical processors without preemption. FJS has two versions that differ in their objective functions. In the operational version, denoted OFJS, the number of available processors m is given and the problem is to select jobs for processing so as to maximize their total weight. In the tactical version, denoted TFJS, all the jobs have to be processed and the problem is to minimize m, the number of processors required for processing all the jobs regardless of their weight. Note that TFJS can easily be solved by finding the maximum cardinality set of overlapping jobs over time. This problem can be also addressed with additional constraints and applied to staff capacity planning in the field of aircraft maintenance. A similar problem arises when minimizing the number of operators in electronic chip design. In another variant, FJS is solved in the case of processors classes, and this has an impact on jobs gain. That case can be regarded as FJS with multi-purpose machines. Fixed Job Scheduling problems are more difficult to solve when spread time constraints have to be met. Spread time constraints can be stated as follows: the duration between the starting time and the completion time of any pair of jobs allocated to the same processor has to be less than or equal to a given duration T . This kind of constraints is appropriate for modeling work regulations: the bus driver scheduling problem is a typical application of FJS with spread time constraint. This word addresses the operational version of fixed job scheduling problem, denoted OFJSST.