Two-machine job shop scheduling with optional job rejection
- Resource Type
- Original Paper
- Authors
- Chen, Ren-Xia; Li, Shi-Sheng
- Source
- Optimization Letters. :1-26
- Subject
- Scheduling
Job-shop
Rejection
Approximation algorithm
- Language
- English
- ISSN
- 1862-4472
1862-4480
We investigate a two-machine job shop scheduling problem with optional job rejection. The target is to look for a feasible schedule for the set of accepted jobs so that the sum of the makespan of the accepted jobs and the total penalty of the rejected jobs is minimized. We propose an exact pseudo-polynomial dynamic programming algorithm, a greedy 5+12ee-1NPO(n2)-approximation algorithm, an LP-based 5+12ee-1NPO(n2)-approximation algorithm, and a fully polynomial time approximation scheme to solve it. We demonstrate that the proportionate case is 5+12ee-1NPO(n2)-hard and provide an 5+12ee-1NPO(n2)-time algorithm for the agreeable case.