Resource-constrained scheduling with hard due windows and rejection penalties. Issue 9 (1st September 2016)

• Record Type: Journal Article
• Authors: Garcia, Christopher
• Is Part Of: Engineering optimization. Volume 48:Issue 9(2016)
• Page Start: 1515
• Page End: 1528
• Publication Date: 2016-09-01
• Subjects: resource-constrained -- order acceptance -- evolutionary algorithm -- mixed-integer programming -- Meta-RaPS; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2015.1120298
• Languages: English
• ISSNs: 0305-215X

Abstract

Abstract : This work studies a scheduling problem where each job must be either accepted and scheduled to complete within its specified due window, or rejected altogether. Each job has a certain processing time and contributes a certain profit if accepted or penalty cost if rejected. There is a set of renewable resources, and no resource limit can be exceeded at any time. Each job requires a certain amount of each resource when processed, and the objective is to maximize total profit. A mixed-integer programming formulation and three approximation algorithms are presented: a priority rule heuristic, an algorithm based on the metaheuristic for randomized priority search and an evolutionary algorithm. Computational experiments comparing these four solution methods were performed on a set of generated benchmark problems covering a wide range of problem characteristics. The evolutionary algorithm outperformed the other methods in most cases, often significantly, and never significantly underperformed any method.