|本期目录/Table of Contents|

[1]胡觉亮,杨佳雯,苏晓彤,等.机器带周期性维护时段的加工与运输协同排序问题[J].浙江理工大学学报,2016,35-36(自科6):951-956.
　HU Jueliang,YANG Jiawen,SU Xiaotong,et al.Processing and Transportation Coordination Scheduling of Machine with Periodic Maintenance[J].Journal of Zhejiang Sci-Tech University,2016,35-36(自科6):951-956.
点击复制

机器带周期性维护时段的加工与运输协同排序问题()
分享到：

浙江理工大学学报[ISSN:1673-3851/CN:33-1338/TS]

卷:
第35-36卷
期数:
2016年自科6期
页码:
951-956
栏目:
出版日期:
2016-11-10

文章信息/Info

Title:
Processing and Transportation Coordination Scheduling of Machine with Periodic Maintenance
文章编号:
1673-3851 (2016) 06-0951-006
作者:
胡觉亮; 杨佳雯; 苏晓彤; 董建明
浙江理工大学理学院，杭州 310018
Author(s):
HU Jueliang;  YANG Jiawen;  SU Xiaotong;  DONG Jianming
School of Sciences, Zhejiang Sci-Tech University, Hangzhou 310018, China
关键词:
单台机; 维护时段; 不可恢复; 近似算法
分类号:
O224
文献标志码:
A
摘要:
研究了一类机器带周期性维护时段且完工工件需要运输的新型排序问题。在该问题中，机器需要进行周期性的维护，且被维护时段打断的工件加工不可恢复；工件具有不同的尺寸且工件的加工时间与物理尺寸大小具有一定的比例关系，每个维护时段内只允许加工一个批次的工件；加工完的工件需要由一辆带有容量限制的运输工具运往客户。算法的目标是极小化所有工件加工完成并运送到客户的时间。证明了该问题是强NPHard问题，设计了该问题的一个多项式时间近似算法，并证明了该算法的最坏情况界不大于5/3。

参考文献/References:

［1］ LEE C Y. Machine scheduling with an availability constraint［J］. Journal of Global Optimization,1996,9(3):395-416.
［2］ HE Y, JI M, CHENG T C E. Single machine scheduling with a restricted ratemodifying activity［J］. Naval Research Logistics,2005,52(4):361-369.
［3］ LEE C Y, LIMAN S D. Single machine flowtime scheduling with scheduled maintenance［J］. Acta Informatica,1992,29(4):375-382.
［4］ SADFI C, PENZ B, RAPINE C, et al. An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints［J］. European Journal of Operational Research,2005,161(1):3-10.
［5］ HE Y, ZHONG W Y, GU H K. Improved algorithms for two single machine scheduling problems［J］. Theoretical Computer Science,2006,363(3):257-265.
［6］ LOW C, MIN J, HSU C J, et al. Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance［J］. Applied Mathematical Modeling,2010,34(2):334-342.
［7］ YU X Y, ZHANG Y L, STEINER G. Single machine scheduling with periodic maintenance to minimize makespan revisited［J］. Journal of Scheduling,2014,17(3):263-270.
［8］ LEE J Y, KIM Y D. Minimizing the number of tardy jobs in a singlemachine scheduling problem with periodic maintenance［J］. Computers & Operations Research,2012,39(9):2196-2205.
［9］ LIAO C J, CHEN W J. Single machine scheduling with periodic maintenance and nonresumable jobs［J］. Computer & Operations Research,2003,30(9):1335-1347.
［10］ CHEN W J. Minimizing number of tardy jobs on s single Machine subject to periodic maintenance［J］. Omega,2009,37(3):591-599.

相似文献/References:

[1]胡觉亮,王焕男,蒋义伟.带时间延迟的极小化总完工时间的单机排序问题[J].浙江理工大学学报,2014,31-32(自科1):83.
　HU Jue liang,WANG Huan nan,JIANG Yi wei.Single Machine Sequencing Problem of Minimization of TotalCompletion Time with Time Delay[J].Journal of Zhejiang Sci-Tech University,2014,31-32(自科6):83.

备注/Memo

备注/Memo:
收稿日期： 2015-11-30
基金项目： 国家自然科学基金项目（11471286，11501512）；浙江理工大学科研启动经费项目（13062171-Y）
作者简介： 胡觉亮（1958-），男，浙江杭州人，教授，主要从事运筹学、组合优化方面的研究
通信作者： 董建明, E-mail：djm226@163.com
更新日期/Last Update: 2016-11-22