Abstract
In this paper, we study a robust single-machine scheduling problem under four alternative optimization criteria: minimizing total completion time, minimizing total weighted completion time, minimizing maximum lateness, and minimizing the number of late jobs. We assume that job processing times are subject to uncertainty. Accordingly, we construct three alternative uncertainty sets, each of which defines job processing times that can simultaneously occur. The robust optimization framework assumes that, given a job schedule, a worst-case set of processing times will be realized from among those allowed by the uncertainty set under consideration. For each combination of objective function and uncertainty set, we first analyze the problem of identifying a set of worst-case processing times with respect to a fixed schedule, and then investigate the problem of selecting a schedule whose worst-case objective is minimal.
Original language | English (US) |
---|---|
Pages (from-to) | 575-592 |
Number of pages | 18 |
Journal | Journal of Scheduling |
Volume | 18 |
Issue number | 6 |
DOIs | |
State | Published - Dec 1 2015 |
Externally published | Yes |
Keywords
- Complexity
- Dynamic programming
- Integer programming
- Robust optimization
ASJC Scopus subject areas
- Software
- General Engineering
- Management Science and Operations Research
- Artificial Intelligence