Abstract
This paper investigates the classical preemptive parallel-machine scheduling problem of maximizing number of on-time jobs. While the problem is known to be NP-hard, no theoretical analysis of approximation algorithms exists in the literature. As part of the analysis, a new non-standard mixed integer formulation is developed. We propose heuristics based on different design strategies. These heuristics have asymptotically tight relative errors of 1/2. Experimental tests evaluate the computational performance of the procedures.
Original language | American English |
---|---|
Pages (from-to) | 413-431 |
Number of pages | 19 |
Journal | Journal of Scheduling |
Volume | 22 |
Issue number | 4 |
DOIs | |
State | Published - 15 Aug 2019 |
Keywords
- Heuristic performance analysis
- Mixed integer program
- Number of tardy jobs
- Parallel-machine scheduling
- Preemption