平行机物流排序的近似算法  

Approximation Algorithms of Logistics Scheduling under Parallel Machines

作　　者：陈荣军[1] 唐国春[2] 

机构地区：[1]常州工学院数学系,常州213002 [2]上海第二工业大学管理工程研究所,上海201209

出　　处：《应用数学学报》2011年第6期1046-1055,共10页Acta Mathematicae Applicatae Sinica

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

摘　　要：本文研究一个两阶段物流排序问题,即第一阶段工件在平行机上加工,在第二阶段这些被加工过的工件以某种运输方式分批运送到预先指定的目的地.优化的目标是使工件带权送到的时间与运输费用的总和为最小.应用动态规划及组合优化方法,分别研究"满足一致性条件"和一般情形下该问题的多项式时间近似算法,并分析算法的性能比.In this paper, we study a general two-stage scheduling problem, in which jobs of different importance are processed by parellel 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 times and total transportation cost. For the problem under agreeable and general cases, we use dynamic programming and combinatorial method to provide heuristic Mgorithms with worst-case performance analysis, respectively.

关 键 词：排序 平行机 分批 运输 算法 

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