Single machine scheduling to meet due times under shutdown constraints

This paper considers a single machine scheduling with due time constraints, time zero constraints and shutdown constraints on the machine. The shutdown is a disruptive event such as holiday, breaks or machine maintenance, and has a prespecified period when the machine will be interrupted. No tardy jobs are allowed, and if a job is completed earlier than its due time, then the shop holds the job and incurs the holding cost for earliness. The starting times for all jobs should be non-negative and no jobs can be processed during the period of a shutdown. This paper proposes a heuristic algorithm which manipulates the starting and completion times of the shutdown period so as to minimize approximately the sum of the holding cost and the reduction cost in shutdown times.