Article ID: | iaor20083020 |
Country: | Netherlands |
Volume: | 53 |
Issue: | 3 |
Start Page Number: | 420 |
End Page Number: | 432 |
Publication Date: | Oct 2007 |
Journal: | Computers & Industrial Engineering |
Authors: | Geunes Joseph, Yang Bibo |
Keywords: | heuristics |
We consider single-resource scheduling when candidate jobs may be accepted (producing job-specific profit) or rejected. Our solution approaches seek to maximize the profitability of the resulting schedule under job-specific tardiness costs and reducible processing times (at a cost). We present an algorithm that maximizes schedule profit for a given sequence of jobs, along with two heuristic approaches for generating good job sequences. A set of computational tests on randomly generated problem instances demonstrates the relative effectiveness of our proposed heuristic approaches.