Journal
COMPUTERS & OPERATIONS RESEARCH
Volume 51, Issue -, Pages 268-281Publisher
PERGAMON-ELSEVIER SCIENCE LTD
DOI: 10.1016/j.cor.2014.06.002
Keywords
Scheduling; Fixed job scheduling; Resource allocation; Complexity; Branch and price; Heuristics
Ask authors/readers for more resources
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(i), and a value v. 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. (C) 2014 Elsevier Ltd. All rights reserved.
Authors
I am an author on this paper
Click your name to claim this paper and add it to your profile.
Reviews
Recommended
No Data Available