论文部分内容阅读
This paper studies the batch sizing scheduling problem with earliness and tardiness penalties which is closely related to a two-level supply chain problem.In the problem,there are K customer orders,where each customer order consisting of some unit length jobs has a due date.The jobs are processed in a common machine and then delivered to their customers in batches,where the size of each batch has upper and lower bounds and each batch may incur a fixed setup cost which can also be considered a fixed delivery cost.The goal is to find a schedule which minimizes the sum of the earliness and tardiness costs and the setup costs incurred by creating a new batch.The authors first present some structural properties of the optimal schedules for single-order problem with an additional assumption(a):The jobs are consecutively processed from time zero.Based on these properties,the authors give a polynomial-time algorithm for single-order problem with Assumption(a).Then the authors give dynamic programming algorithms for some special cases of multiple-order problem with Assumption(a).At last,the authors present some structural properties of the optimal schedules for single-order problem without Assumption(a) and give a polynomial-time algorithm for it.
This paper studies the batch sizing scheduling problem with earliness and tardiness penalties which is closely related to a two-level supply chain problem. The problem, there are K customer orders, where each customer order constitutes some unit length jobs has a due date The jobs are processed in a common machine and then delivered to their customers in batches, where the size of each batch has upper and lower bounds and each batch may incur a fixed setup cost which can also be considered a fixed delivery cost. is to find a schedule which minimizes the sum of the earliness and tardiness costs and the setup costs incurred by creating a new batch. The authors first present some structural properties of the optimal schedules for single-order problems with an additional assumption (a): The jobs are sequentiallyly processed from time zero. Based on these properties, the authors give a polynomial-time algorithm for single-order problem with Assumption (a). Then the authors give dynamic prog ramming algorithms for some special cases of multiple-order problem with Assumption (a). At last, the authors present some structural properties of the optimal schedules for single-order problem without Assumption (a) and give a polynomial-time algorithm for it.