供应链管理中的一类分批调度问题  

The Supply Chain Scheduling Problem with Transportation and Batching

作　　者：朱洪利[1] 王迅娣[1] 张玉忠[1] 

机构地区：[1]曲阜师范大学运筹与管理学院,山东省日照市276826

出　　处：《曲阜师范大学学报（自然科学版）》2010年第4期41-44,共4页Journal of Qufu Normal University(Natural Science)

基　　金：国家自然科学基金(10671108);教育部博士点基金项目(20070446001)

摘　　要：研究了一类集成配送和加工的供应链调度问题.在配送阶段,由多辆运输工具将工件从仓储区运送到批处理机进行深加工;在加工阶段,工件在批处理机上成批加工,批加工费用固定.目标函数是极小化最大完工时间和总加工费用之和.证明了该问题是NP-难的,并对该问题的一类特殊情形给出了多项式时间算法.This paper investigates a supply chain scheduling problem,which integrates transportation and production.In the transportation stage,all the jobs are transported from the holding area to the batching machine by several vehicles.In the production stage,the batching machine processes some jobs as a batch which occurs a fixed processing cost.The objective is to minimize the makespan and total processing cost.We prove that it is NP-hard,and we provide a polynomial time algorithm for a special case of the problem.

关 键 词：分批排序 供应链调度 复杂性 NP-HARD 多项式时间算法 

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