On the single-processor scheduling problem with time restrictions

Abstract

This paper presents a time-indexed mixed integer programming formulation for the single-processor scheduling problem with time restrictions that has been formulated at first by Braun et al. in [1]. The problem is as follows. A set of n independent jobs are simultaneously available for processing at the beginning of the planning horizon, and their processing times are fixed and known in advance. The jobs have to be processed non-preemptively on a single processor that can handle only one job at a time. Furthermore, during any time period of length α > 0 the number of jobs being executed is less than or equal to a given integer value B ≥ 2. The objective is to minimize the completion time of the last job in the optimal sequence (i.e. the makespan). To our knowledge, this is the first time that a mathematical model is given to solve the single-processor scheduling problem with time restrictions exactly. The performance of the model is tested by running it on randomly generated instances. The computational analysis shows that the proposed model, without any valid cuts, performs considerably well for small instances and a relatively large value of the integer B.