Skip to Main content Skip to Navigation
Conference papers

Mixed integer programming formulations for the single processor scheduling problem with time restrictions

Abstract : In the single-processor scheduling problem with time restrictions, n independent jobs have to be processed non-preemptively on a single processor that can handle only one job at a time, subject only to the following constraint: 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. This constraint reflects the condition that each job needs one of B additional resources for being processed and that a resource has to be renewed after the processing of a job has been finished. The jobs are simultaneously available for processing at the beginning of the planning horizon, and their processing times are fixed and known in advance. The objective is to minimize the completion time of the last job in the optimal sequence (i.e. the makespan). In a previous work it is shown that this problem is NP-hard when the value B is variable and a classical worst-case analysis of List Scheduling for this situation has been carried out. We present two mixed integer programming (MIP) formulations to solve the single-processor scheduling problem with time restrictions exactly. The first model is based on time indexed variables whereas the second is based on assignment and positional date variables. The performances of these models are tested by running them on randomly generated instances. Extensive computational studies show the effectiveness (in the number of problems solved) and efficiency (in computational time) of the assignment and positional date variables formulation for the randomly generated instances with up to n = 500 jobs, B = 10 number of resources and processing times out of the interval 1 up to 1000.
Document type :
Conference papers
Complete list of metadata
Contributor : Kathleen TORCK Connect in order to contact the contributor
Submitted on : Thursday, May 5, 2022 - 10:18:12 AM
Last modification on : Friday, May 6, 2022 - 3:38:42 AM


  • HAL Id : hal-03659548, version 1



Rachid Benmansour, Oliver Braun, Abdelhakim Artiba. Mixed integer programming formulations for the single processor scheduling problem with time restrictions. CIE 45: 2015 International Conference on Computers and Industrial Engineering, Oct 2015, Metz, France. ⟨hal-03659548⟩



Record views