Optimal scheduling strategies of jobs belonging to different classes on a single machine with variable processing times

A single machine is considered in this paper in order to determine the optimal service sequence of jobs belonging to different classes (each class consists of equivalent and indistinguishable - but for due-dates - jobs). This is accomplished by solving an optimization problem whose decision variables are those related to job sequencing, and whose objective is to minimize the overall weighted job tardiness. In addition, processing times for jobs belonging to a certain class may be variable (even though constrained by upper and lower bounds). Thus, decision variables include also such times, and the cost function takes into account the weighted extra cost for executing jobs at a higher speed than the nominal one. The optimization problem is solved through standard dynamic programming techniques, and optimal closed-loop decision strategies are determined.