Skip to Main content Skip to Navigation
Conference papers

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 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
Document type :
Conference papers
Complete list of metadata
Contributor : Mylène Delrue Connect in order to contact the contributor
Submitted on : Friday, May 6, 2022 - 11:54:56 AM
Last modification on : Saturday, May 7, 2022 - 3:35:07 AM




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⟩



Record views