We consider a scheduling problem where n jobs have to be carried out by m parallel identical machines. The attributes of a job j are a fixed start time sj, a fixed finish time fj, a resource requirement rj, and a value vj. Every machine owns R units of a renewable resource necessary to carry out jobs. A machine can process more than one job at a time, provided the resource consumption does not exceed R. The jobs must be processed in a non-preemptive way. Within this setting, we ask for a subset of jobs that can be feasibly scheduled with the maximum total value. For this strongly NP-hard problem, we first discuss an approximation result. Then, we propose a column generation scheme for the exact solution. Finally, we suggest some greedy heuristics and a restricted enumeration heuristic. All proposed algorithms are implemented and tested on a large set of randomly generated instances. It turns out that the column generation technique clearly outperforms the direct resolution of a natural compact formulation; the greedy algorithms produce good quality solutions in negligible time, whereas the restricted enumeration averages the performance of the greedy methods and the exact technique.
Optimal interval scheduling with a resource constraint / E. Angelelli, N. Bianchessi, C. Filippi. - In: COMPUTERS & OPERATIONS RESEARCH. - ISSN 0305-0548. - 51(2014), pp. 268-281.
|Titolo:||Optimal interval scheduling with a resource constraint|
|Parole Chiave:||Scheduling; Fixed job scheduling; Resource allocation; Complexity; Branch and price; Heuristics|
|Settore Scientifico Disciplinare:||Settore INF/01 - Informatica|
Settore MAT/09 - Ricerca Operativa
|Data di pubblicazione:||2014|
|Digital Object Identifier (DOI):||http://dx.doi.org/10.1016/j.cor.2014.06.002|
|Appare nelle tipologie:||01 - Articolo su periodico|
File in questo prodotto:
|Optimal-interval-scheduling-with-a-resource-constraint_COR-14.pdf||Publisher's version/PDF||Administrator Richiedi una copia|