Name
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 s"j, a fixed finish time f"j, a resource requirement r"j, and a value v"j. 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1016/j.cor.2014.06.002 | Computers and Operations Research |
Keywords | Field | DocType |
scheduling,branch and price,fixed job scheduling,resource allocation,complexity,heuristics | Mathematical optimization,Job shop scheduling,Interval scheduling,Scheduling (computing),Branch and price,Resource allocation,Heuristics,Start time,Mathematics | Journal |
Volume | Issue | ISSN |
51 | 1 | 0305-0548 |
Citations | PageRank | References |
3 | 0.42 | 15 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Enrico Angelelli | 1 | 291 | 20.58 |
| Nicola Bianchessi | 2 | 236 | 13.72 |
| Carlo Filippi | 3 | 168 | 13.77 |