An earliness and tardiness stochastic scheduling problem on a batch processor

For an earliness and tardiness stochastic scheduling problem on a batch processor, let processing time of various batches be independent identically distributed; the due dates of various jobs be independent, and independent of the processing time of various batches; the objective is to minimize the expected total earliness and tardiness of jobs. When processing times and due dates are random variables exponentially distributed with known rates, several properties of the optimal schedule are found; based on these properties, an algorithm using dynamic programming to find the optimal solution is proposed, the time complexity of the algorithm is O(n²B²)(B<n), thus the problem under such condition is polynomially solvable.