The single-processor scheduling problem with time restrictions: complexity and related problems (Q2304117)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The single-processor scheduling problem with time restrictions: complexity and related problems |
scientific article |
Statements
The single-processor scheduling problem with time restrictions: complexity and related problems (English)
0 references
6 March 2020
0 references
The authors consider the single machine scheduling problem without preemptions supposing that all feasible solutions are restricted to the schedules where any time interval of length \(\alpha\) can intersect at most \(B\) jobs. The purpose is to find a schedule with the minimal completion time. It is proved that the considered problem is binary NP-hard by giving a reduction from the two parallel machines scheduling problem with a single server and equal processing times. Two mixed integer programming models are developed: ``time-indexed'' and ``assignment and positional date variables''. The performance of both models is compared on instances of up to 50 jobs. It is shown that the second model can find optimal solutions for instances of up to 500 jobs for \(B=10\), \(\alpha =100\) with the CPU time limit of one hour.
0 references
scheduling
0 references
time restrictions
0 references
single processor
0 references
NP-hard
0 references
mixed integer programming
0 references
parallel machine scheduling with a single server
0 references
0 references
0 references
0 references