机器带不可用时间限制的简单线性恶化供应链排序问题

发布时间：2018-04-15 09:33

  本文选题：简单线性恶化 + 不可用时间限制　； 参考：《运筹学学报》2016年04期

【摘要】：研究的单机供应链排序问题中,机器有一个不可用时间限制,工件的加工时间与恶化率及其开工时间有关,且工件的加工不可恢复.一个或多个完工工件可组成一个发送批由车辆发送给客户,且在机器不可用时间限制之前完工的工件必须在限制开始之时或之前完成发送.问题的目标是最小化总发送时间与总发送费用之和.证明问题是NP-难的,提出了伪多项式时间的动态规划算法.进一步,在确定问题目标函数值的上界及下界之后,设计了一个完全多项式时间近似方案(FPTAS).
[Abstract]:In the single machine supply chain scheduling problem, the machine has an unusable time limit, the processing time of the workpiece is related to the deterioration rate and the starting time, and the processing of the workpiece is not recoverable.One or more completed artifacts may form a sending batch to be sent to the customer by the vehicle, and the work completed before the machine is unavailable time limit must be sent at or before the beginning of the limit.The goal of the problem is to minimize the sum of total transmission time and total transmission cost.To prove that the problem is NP-hard, a pseudo polynomial time dynamic programming algorithm is proposed.Furthermore, after determining the upper and lower bounds of the value of the objective function of the problem, a complete polynomial time approximation scheme is designed.
【作者单位】： 上海工业大学文理学部;华东理工大学理学院;
【基金】：国家自然科学基金青年项目(No.11601316) 上海第二工业大学青年教师培养科研项目(No.201513)
【分类号】：O223

【相似文献】

相关期刊论文 前5条

1 马英;左春荣;杨善林;;带不可用时间段和恶化加工时间的单机调度[J];系统工程学报;2010年03期

2 马英;杨善林;储诚斌;;带不可用时间段的部分可续型单机最大完工时间调度[J];系统工程理论与实践;2009年04期

3 马英;左春荣;杨善林;;带不可用时间段的两台同类机加权完工时间和调度[J];中国科学技术大学学报;2009年06期

4 王海明;刘吉红;王庆磊;;带不可用时间段的不允许等待柔性流水排序问题[J];兰州大学学报(自然科学版);2007年01期

5 ;[J];;年期

相关博士学位论文 前1条

1 范静;带不可用时间段的若干单机供应链排序问题的算法研究[D];华东理工大学;2015年

，

本文编号：1753564