储存时间有上限的两阶段供应链排序问题

摘要

研究一类储存时间有上限的两阶段供应链排序问题.两阶段是指工件先加工,后运输:加工阶段是一台加工机器逐个加工工件;运输阶段是无限台车辆分批运输完工的工件.工件的运输完成时刻与完工时刻之差定义为工件的储存时间,且有相应的储存费用,且任意工件的储存时间都不超过某一常数.若工件的运输完成时刻早于(晚于)交货期窗口的开始(结束)时刻,则有相应的提前(延误)惩罚费用.目标是极小化总提前惩罚费用、总延误惩罚费用、总储存费用、总运输费用以及与交货期窗口有关的费用之和.先证明该问题是NP-难的,后对单位时间的储存费用不超过单位时间的延误惩罚费用的情形给出了伪多项式时间算法.%We investigate a two-stage supply chain scheduling problem in which jobs have the holding time which is limited by a constant.A job which is processed completely by the machine needs to dispatch 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 provide the proof of NP-hard for the problem.Then,we consider the case where the unit cost of holding time is not more than the unit cost of tardiness and give a pseudo-polynomial time algorithm for this case.