自由作业下的一类物流排序

自由作业下的一类物流排序 A Kind of Logistic Scheduling under Open Shop Machines 陈荣军 CHEN Rongjun1 1 first-author 许明辉 XU Minghui2 2 唐国春 TANG Guochun3 3 常州工学院数学系 常州工学院数学系 Department of Mathematics,Changzhou Institute of Technology Department of Mathematics,Changzhou Institute of Technology 武汉大学经济与管理学院 武汉大学经济与管理学院 School of Economics and Management,Wuhan University School of Economics and Management,Wuhan University 上海第二工业大学管理工程研究所 上海第二工业大学管理工程研究所 Institute of Management Engineering,Shanghai Second Polytechnic University Institute of Management Engineering,Shanghai Second Polytechnic University 研究了一个两阶段物流排序问题,即第一阶段工件在自由作业机器上加工,第二阶段这些被加工过的工件以某种运输方式分批运送到预先指定的目的地.目标是极小化工件带权送到时间与运输费用总和.将动态规划与组合优化方法结合,在假设工件加工时间与权满足"一致性"条件下,利用动态规划算法,构造了性能比不超过2 m的多项式时间近似算法;对于一般情形,用传统排序问题的算法构造了多项式时间近似算法,并分析算法性能比. We study a general two-stage logistic scheduling problem,in which jobs of different importance are processed on open shop machines at the first stage and then,in the second stage,the completed jobs need to be batch delivered to various pre-specified destinations in one of a number of available transportation modes.Our objective is to minimize the sum of weighted job delivery time and total transportation cost.For the problem under an assumption that jobs weights are agreeable,we use dynamic programming and combinatorial optimization to provide a polynomial algorithm with performance ratio no more than 2m.For general case,we use classic scheduling algorithm to propose heuristic algorithm with worst-case performance analysis. 排序 自由作业 分批 运输 性能比 scheduling open shop batching transportation performance guarantee 10.14188/j.1671-8836.2011.02.016 O223 国家自然科学基金（70731160015）;江苏省自然科学基金（yw06037）资助项目 2011-02-01 2021-04-01 2 57