研究一类优化交货期窗口的两阶段供应链排序问题. 优化交货期窗口是指交货期窗口的开始与结束时刻是决策变量, 不是输入常量. 两阶段是指工件先加工, 后运输: 加工阶段是一台加工机器逐个加工工件；运输阶段是无限台车辆分批运输完工的工件. 工件的开始运输时刻与完工时刻之差定义为工件的储存时间, 且有相应的储存费用. 若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻, 则有相应的提前(延误)惩罚费用. 目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和. 针对单位时间的延误惩罚费用不超过单位时间的储存费用、单位时间的储存费用不超过单位时间的提前惩罚费用的情形, 给出了时间复杂性为O(n^{8})的动态规划算法.

This paper mainly addresses a two-stage supply chain scheduling problem in which jobs have an assignable common due window. The due window need to be determined, because the start and completion time of the window is a variable instead of a constant. A job which is processed completely by the machine need to be dispatched with batch to customer by many vehicles, and a job will incur a holding cost if its completion time is earlier than its dispatch date. Each job will incur an early (tardy) penalty if it is early (tardy) with respect to the common due window under a given schedule. The objective is to find the optimal size and location of the window, the optimal dispatch date for each job, as well as an optimal job sequence to minimize a cost function based on earliness, tardiness, holding time, window location, window size, and batch delivery. We consider the case where the unit cost of tardiness is not more than the unit cost of holding time, and the unit cost of holding time is not more than the unit cost of earliness. We provide an O(n^{8}) dynamic programming algorithm for this case.