基于退化效应的两台机器流水作业可拒绝排序

发布时间：2018-03-23 22:10

  本文选题：排序　切入点：流水作业　出处：《运筹学学报》2017年02期

【摘要】：考虑了工件具有退化效应的两台机器流水作业可拒绝排序问题,其中工件的加工时间是其开工时间的简单线性增加函数.每个工件或者被接收,依次在两台流水作业机器上被加工,或者被拒绝但需要支付一个确定的费用.考虑的目标是被接收工件的最大完工时间加上被拒绝工件的总拒绝费用之和.证明了问题是NP-难的,并提出了一个动态规划算法.最后对一种特殊情况设计了多项式时间最优算法.
[Abstract]:In this paper, we consider the problem that two machines with degenerative effect have the problem of rejection and ordering of flow jobs, in which the processing time of the workpiece is a simple linear increase function of its starting time, and each workpiece is either received or received. In turn, they are processed on two flow machines, The goal is the maximum completion time of the received workpiece plus the sum of the total rejection cost of the rejected workpiece. It proves that the problem is NP-hard. A dynamic programming algorithm is proposed, and a polynomial time optimal algorithm is designed for a special case.
【作者单位】： 曲阜师范大学数学科学学院;
【基金】：国家自然科学基金(No.11201259) 教育部博士点基金(Nos.20123705120001,20123705110003) 山东省自然科学基金(Nos.ZR2015GZ009,ZR2014AM012,ZR2014AM021) 曲阜师范大学科研奖励基金(No.xkj201516)
【分类号】：O223
，

本文编号：1655405