Single machine scheduling to minimize the absolute maximum lateness with shortening job processing times

Abstract

In this paper we consider a single machine scheduling problem with shortening job processing times. The objective is to find a schedule that minimizes the absolute maximum lateness, where the due dates of jobs are a common due date for all jobs. For the cases of common due date is a given constant and a variable, we show that the problem can be solved in polynomial time, respectively.

Keywords:

• Scheduling
• Single machine
• Time-dependent processing time
• Absolute maximum lateness