A linear time approximation scheme for scheduling unbounded batch machines with delivery times and inclusive processing set restrictions

Abstract

We consider the problem of scheduling jobs with delivery times and inclusive processing set restrictions on unbounded batch machines to minimize the maximum delivery completion time, which is equivalent to minimizing the maximum lateness from the optimization viewpoint. We develop a polynomial time approximation scheme for this strongly NP-hard problem that runs in linear time for any fixed accuracy requirement.

Keywords

• scheduling
• unbounded batch machines
• inclusive processing set restrictions
• maximum delivery completion time
• polynomial time approximation scheme