A single machine scheduling problem with time windows and precedence constraints

This paper studies a scheduling problem in a single-machine environment. Each job has a processing time, a release date, a due date, a deadline and a weight representing the penalty per unit-time delay. Moreover, an acyclic graph representing the jobs’ precedence relations is given so that each job is executed after all completion times of its predecessors. Our goal is to schedule jobs to minimize the total weighted tardiness penalty. We present a branch and bound algorithm as well as an enhanced successive sublimation dynamic programming algorithm to solve the problem until optimality.status: publishe