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

A Kind of Logistic Scheduling under Open Shop Machines

作　　者：陈荣军[1] 许明辉[2] 唐国春[3] 

机构地区：[1]常州工学院数学系,江苏常州213002 [2]武汉大学经济与管理学院,湖北武汉430072 [3]上海第二工业大学管理工程研究所,上海201209

出　　处：《武汉大学学报（理学版）》2011年第2期137-140,共4页Journal of Wuhan University:Natural Science Edition

基　　金：国家自然科学基金(70731160015);江苏省自然科学基金(yw06037)资助项目

摘　　要：研究了一个两阶段物流排序问题,即第一阶段工件在自由作业机器上加工,第二阶段这些被加工过的工件以某种运输方式分批运送到预先指定的目的地.目标是极小化工件带权送到时间与运输费用总和.将动态规划与组合优化方法结合,在假设工件加工时间与权满足"一致性"条件下,利用动态规划算法,构造了性能比不超过2 m的多项式时间近似算法;对于一般情形,用传统排序问题的算法构造了多项式时间近似算法,并分析算法性能比.We study a general two-stage logistic scheduling problem, in which jobs of different impor- tance 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 trans- portation modes. Our objective is to minimize the sum of weighted job delivery time and total transporta- tion cost. For the problem under an assumption that jobs weights are agreeable, we use dynamic program- ming 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 worstcase performance analysis.

关 键 词：排序 自由作业 分批 运输 性能比 

分 类 号：O224[理学—运筹学与控制论]