Minimizing flowtime and missed due-dates in single-machine sequencing

Given a set of simultaneously available jobs, each assigned a due-date, to be processed on a single machine, the problem is to find an optimal order to process the jobs that minimizes a penalty function. Since the effectiveness of a schedule is primarily evaluated on the basis of its effects on the WIP inventory and order delivery performance, we employ a bicriterion penalty function defined as the weighted sum of the flowtime and earliness and tardiness values of each job. This sequencing problem is shown to be NP-complete, so it is doubtful that a polynomial bound solution algorithm exists. In this paper, a dynamic programming (DP) formulation of the problem is presented and the optimal job sequence is determined by implicit enumeration in accordance with the DP optimality principle.