工件带就绪时间的单机供应链排序问题

SUPPLY CHAIN SCHEDULING WITH JOBS' RELEASE TIMES ON A SINGLE MACHINE

研究工件带就绪时间的单机供应链排序问题,即工件到达后按何种顺序在机器上加工,并将完工工件如何由运输工具发送给客户,使得生产费用与发送费用总和最少.这里,每个工件的生产费用为工件的发送时刻,多个工件可组成一批一次发送给客户,发送费用与发送次数成正比.对于工件允许中断加工的问题,基于SRPT规则给出多项式时间的动态规划算法求解最优序;对于工件不允许中断加工的问题,证明问题是强NP难的,并提出了性能比为2的近似算法.

This paper is concerned with the supply chain scheduling problem integrated production and distribution operations. Each job is first processed on a single machine, then is delivered to the customer directly by one vehicle available, with other jobs as one shipment. The objective is to minimize the total cost including production cost and distribution cost in the processing stage and the delivering stage. Production cost of every job is measured by the time when the job is delivered to the customer in a shipment. The distribution costs are proportional to the delivery times. If jobs can be suspended during processing stage, it can be solved by dynamic programming polynomially based on SRPT rule. If jobs are not permitted to be suspended, the problem is strongly NP-hard, and an approximation algorithm with the worst performance 2 is presented.