摘要
为了提高供应链体系中企业的生产效率,降低生产和运输成本,针对钢铁企业生产与产品配送特点,提出了并行机生产与成批配送协调调度问题.并行机上加工完成的订单以组批的方式配送到相应的客户,每批配送的订单需要考虑运输时间和运输费用,目标为将总完工时间与配送费用之和最小化.通过对问题的最优解进行分析,利用程序划分和动态规划方法,提出了伪多项式时间算法.结果表明,伪多项式时间算法可以成为解决该问题的全多项式时间近似策略.
In order to improve the production efficiency and decrease the production and delivery cost of companies in the supply chain,a coordinated scheduling problem in both production and batch delivery of parallel machines was proposed aiming at the production and delivery features of products in the iron and steel companies. The orders processed and completed on the parallel machines were delivered to the corresponding customers in batch mode. The transportation time and cost need to be considered in each batch of deliveried order,and the objective is to minimize the sum of total completion time and delivery cost. Through the analysis on the optimal solution for the problem,a psudo-polynomial time algorithm was proposed with both procedure partition and dynamic programming methods. The results show that the pseudo-polynomial time algorithm can be served as a full polynomial time approxination strategy for solving the problem.
出处
《沈阳工业大学学报》
EI
CAS
北大核心
2015年第3期324-328,共5页
Journal of Shenyang University of Technology
基金
国家自然科学基金资助项目(71101097)
辽宁省高等学校优秀人才支持计划项目(LJQ2012017)
辽宁省科学事业公益研究基金资助项目(2012004003)
关键词
并行机
成批配送
协调
全多项式时间近似策略
动态规划
程序划分
伪多项式时间
复杂性
parallel machine
batch delivery
coordination
full polynomial time approximation strategy
dynamic programming
procedure partition
pseudo-polynomial time
complexity
