Abstract
The present paper studies the single machine, no-idle-time scheduling problem with a weighted quadratic earliness and tardiness objective. We investigate the relationship between this problem and the assignment problem, and we derive two lower bounds and several heuristic procedures based on this relationship. Furthermore, the applicability of the time-indexed integer programming formulation is investigated. The results of a computational experiment on a set of randomly generated instances show (1) the high-quality results of the proposed heuristics, (2) the low optimality gap of one of the proposed lower bounds and (3) the applicability of the integer programming formulation to small and medium size cases of the problem.
| Original language | English |
|---|---|
| Pages (from-to) | 1819-1828 |
| Number of pages | 10 |
| Journal | Computers and Operations Research |
| Volume | 40 |
| Issue number | 7 |
| DOIs | |
| State | Published - Jul 2013 |
| Externally published | Yes |
Keywords
- Assignment problem
- Dynamic programming
- Scheduling
- Single machine
- Time-indexed formulation