| 基于退化效应的两台机器流水作业可拒绝排序 |
| |
| 引用本文： | 苗翠霞,孟凡晓.基于退化效应的两台机器流水作业可拒绝排序[J].运筹学学报,2017,21(2):66-72. |
| |
| 作者姓名： | 苗翠霞 孟凡晓 |
| |
| 作者单位： | 1. 曲阜师范大学数学科学学院, 山东 曲阜 273165; |
| |
| 基金项目： | 国家自然科学基金(No.11201259), 教育部博士点基金(Nos.20123705120001, 20123705110003), 山东省自然科学基金(Nos. ZR2015GZ009, ZR2014AM012, ZR2014AM021), 曲阜师范大学科研奖励基金(No.xkj201516) |
| |
| 摘 要： | 考虑了工件具有退化效应的两台机器流水作业可拒绝排序问题,其中工件的加工时间是其开工时间的简单线性增加函数.每个工件或者被接收,依次在两台流水作业机器上被加工,或者被拒绝但需要支付一个确定的费用.考虑的目标是被接收工件的最大完工时间加上被拒绝工件的总拒绝费用之和.证明了问题是NP-难的,并提出了一个动态规划算法.最后对一种特殊情况设计了多项式时间最优算法.
|
| 关 键 词： | 排序 流水作业 退化效应 可拒绝 NP-难 |
| 收稿时间： | 2017-03-28 |
Two-machine flow-shop scheduling with deterioration and rejection |
| |
| MIAO Cuixia,MENG Fanxiao.Two-machine flow-shop scheduling with deterioration and rejection[J].OR Transactions,2017,21(2):66-72. |
| |
| Authors: | MIAO Cuixia MENG Fanxiao |
| |
| Institution: | 1. School of Mathematical Sciences, Qufu Normal University, Qufu 273165, Shandong, China |
| |
| Abstract: | In this paper, we consider the two-machine flow-shop scheduling with deterioration and rejection, in which each job's processing time is simple linear increasing function of its starting time. A job is either accepted and processed on the two machines in a flow-shop system, or rejected with a certain penalty having to be paid. The objective is to minimize the sum of the makespan of the accepted jobs plus the total penalty of the rejected jobs. We show that the problem is NP-hard and present a dynamic programming algorithm. Furthermore, we propose an optimal schedule for one special case. |
| |
| Keywords: | scheduling flow-shop deterioration rejection NP-hard |
| 本文献已被 CNKI 等数据库收录！ |
| 点击此处可从《运筹学学报》浏览原始摘要信息 |
| 点击此处可从《运筹学学报》下载免费的PDF全文 |
|
