具有可变配送费用和固定配送时刻的单机排序问题

摘要

研究了单机环境下生产与配送的协同排序问题.有多个工件需要在一台机器上进行加工,加工完的工件需要分批配送到一个客户.每批工件只能在固定的几个配送时刻出发,不同的配送时刻对应着不同的配送费用.我们的目标是找到生产与配送的协同排序,极小化排序的时间费用与配送费用的加权和.研究了排序理论中主要的四个目标函数,构建了单机情况下的具体模型,分析了问题的复杂性,对于配送费用单调非增的情况给出了它们的最优算法.%This paper considers a coordination scheduling of production and delivery on a single machine.A customer places some jobs to a manufacturer at the planning horizon.Processed jobs are delivered in batches to their customer.Each batch can dispatch to its customer at some fixed delivery dates,and different delivery dates corresponding to different delivery cost.The objective is to find a coordinated production-and-delivery schedule to minimize the weighted sum of the scheduling cost and delivery cost.We consider four main objective functions in scheduling theory,construct the models in single machine environment,analyze the problem complexity and give optimal algorithms to solve the problems under the constraint that the delivery cost are non-increasing with respect to time.