Single-machine scheduling with release times, deadlines, setup times, and rejection

Single-machine scheduling where jobs have a penalty for being late or for being rejected altogether is an important (sub)problem in manufacturing, logistics, and satellite scheduling. It is known to be NP-hard in the strong sense, and there is no polynomial-time algorithm that can guarantee a constant-factor approximation (unless P=NP). We...

A practical dynamic programming based methodology for aircraft maintenance check scheduling optimization

This paper presents a practical dynamic programming based methodology to optimize the long-term maintenance check schedule for a fleet of heterogeneous aircraft. It is the first time that the long-term aircraft maintenance check schedule is optimized, integrating different check types in a single schedule solution. The proposed methodology...