Iterative relaxation-based heuristic for the single-processor scheduling problem with time restrictions.
Résumé
Recently, the single-processor scheduling problem with time restrictions was investigated by several researchers, and worst-case analysis and exact methods to solve this problem were provided. The studied problem has been formulated in 2013 as follows. A set of simultaneously available and independent jobs has to be scheduled, without preemption, on a single processor. We assume that the processing times of the jobs are deterministic and integers, and that the processor is always available. Moreover, this processor cannot process more than one job at any time. In addition to these constraints, the time restrictions apply: during any time period of length α > 0 the number of jobs being executed is at most equal to a given integer value B. We consider the objective of minimizing the makespan. In the present paper, we extend a previous work on the problem. First, we consider a mathematical model based on assignment and positional variables in order to obtain an optimal solution in a short time for small to medium size instances. Then, we apply an iterative relaxationbased heuristic to deal with larger instances to build feasible solutions in reasonable CPU time. Our methods are evaluated and compared on randomly generated instances with 10 to 1000 jobs. The computational analysis shows that the mathematical model can be solved with an academic solver for instances with 100 jobs in reasonable time. Our heuristic method is competitive for these instances, and it provides solutions with a reasonable gap for larger ones with 500 and 1000 jobs.