On the single-processor scheduling problem with time restrictions

Rachid Benmansour (1) , Oliver Braun (2) , Abdelhakim Artiba (1)

1 LAMIH - Laboratoire d'Automatique, de Mécanique et d'Informatique industrielles et Humaines - UMR 8201
2 Trier University of Applied Sciences

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 singleprocessor 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

Mots clés: "Completion time"; "Single processor scheduling"; "Time indexed formulation"; "Time restriction constraint"

Domaines: Informatique [cs]

Rachid Benmansour, Oliver Braun, Abdelhakim Artiba. On the single-processor scheduling problem with time restrictions. 2014 International Conference on Control, Decision and Information Technologies (CoDIT), Nov 2014, Metz, France. pp.242-245, ⟨10.1109/CoDIT.2014.6996900⟩. ⟨hal-03660827⟩