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.

Optimal interval scheduling with a resource constraint

N. Bianchessi;
2014

Abstract

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.
Scheduling; Fixed job scheduling; Resource allocation; Complexity; Branch and price; Heuristics
Settore INF/01 - Informatica
Settore MAT/09 - Ricerca Operativa
Article (author)
File in questo prodotto:
File Dimensione Formato  
Optimal-interval-scheduling-with-a-resource-constraint_COR-14.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 1.81 MB
Formato Adobe PDF
1.81 MB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/609751
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 21
  • ???jsp.display-item.citation.isi??? 21
social impact