|本期目录/Table of Contents|

[1]马春磊,胡觉亮,蒋义伟.带有装卸服务器的三台平行机排序问题的LS算法[J].浙江理工大学学报,2019,41-42(自科一):122-126.
 MA Chunlei,HU Jueliang,JIANG Yiwei.LS algorithm for scheduling three parallel machines with loading and unloading server[J].Journal of Zhejiang Sci-Tech University,2019,41-42(自科一):122-126.
点击复制

带有装卸服务器的三台平行机排序问题的LS算法()
分享到:

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

卷:
第41-42卷
期数:
2019年自科一期
页码:
122-126
栏目:
出版日期:
2018-12-15

文章信息/Info

Title:
LS algorithm for scheduling three parallel machines with loading and unloading server
文章编号:
1673-3851 (2019) 01-0122-05
作者:
马春磊胡觉亮蒋义伟
浙江理工大学理学院,杭州 310018
Author(s):
MA Chunlei HU Jueliang JIANG Yiwei
School of Sciences, Zhejiang Sci-Tech University, Hangzhou 310018, China
关键词:
平行机排序服务器最坏情况界makespanLS算法
分类号:
O233
文献标志码:
A
摘要:
针对一个装载服务器和一个卸载服务器的情形,研究三台平行机上的排序问题。每个工件在加工前需要由装载服务器安装到机器上,加工结束后由卸载服务器进行卸载。装载和卸载时间均为单位时间,目标是极小化最大完工时间。该问题是NP难问题,因此采用经典的List scheduling(LS)算法进行求解。通过引入块的概念对LS排序的结构进行分析,进而证明了LS算法的最坏情况界至多为17/9。

参考文献/References:

[1] Koulamas C. Scheduling two parallel semiautomatic machines to minimize machine interference[J]. Computers and Operations Research,1996,23(10):945-56.
[2] Ganesharajah T, Hall N, Sriskandarajah, C. Design and operational issues in AGVserved manufacturing systems[J]. Annals of Operations Research,1998,76(1):109-154.
[3] Dawande M, Geismar H, Sethi S, et al. Sequencing and scheduling in robotic cells:Recent developments[J]. Journal of Scheduling,2005,8(5):387-426.
[4] Kim M Y, Lee Y H. MIP models and hybrid algorithm for minimizing the makespan of parallel machines scheduling problem with a single server[J]. Computers and Operations Research,2012,39(11):2457-2468.
[5] Kravchenko S, Werner F. Parallel machine scheduling problems with a single server[J]. Mathematical and Computer Modelling,1997,26(12):1-11.
[6] Hall N, Potts C, Sriskandarajah C.Parallel machine scheduling with a common server[J]. Discrete Applied Mathematics,2000,102(3):223-243.
[7] Brucker P, DhaenensFlipo C, Knust S,et al. Complexity results for parallel machine problems with a single server[J]. Journal of Scheduling,2002,5(6):429-457. 
[8] Jiang Y, Dong J, Ji M. Preemptive scheduling on two parallel machines with a single server[J]. Computers & Industrial Engineering,2013,66(2):514-518. 
[9] Cheng T C E, Kravchenko S A, Lin B M T. Preemptive parallelmachine scheduling with a common server to minimize makespan[J]. Naval Research Logistics,2017,64(5):388-398.
[10] Hamzadayi A, Yildiz G. Event driven strategy based complete rescheduling approaches for dynamic m identical parallel machines scheduling problem with a common server[J]. Computers & Industrial Engineering,2016,91:66-84.

备注/Memo

备注/Memo:
收稿日期: 2018-06-08
网络出版日期: 2018-10-08
基金项目: 国家自然科学基金项目(11471286,11571013)
作者简介: 马春磊(1990-),男,河南叶县人,硕士研究生,主要从事运筹与组合优化理论方面的研究
通信作者: 蒋义伟,E-mail:ywjiang@zjgsu.edu.cn
更新日期/Last Update: 2019-03-13