|本期目录/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
关键词:
平行机排序; 服务器; 最坏情况界; makespan; LS算法
分类号:
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.

相似文献/References:

[1]张娜,史佳炳,吴彪,等.基于Netty和Kafka的IOT终端服务系统设计方案[J].浙江理工大学学报,2020,43-44(自科二):240.
　ZHANG Na,SHI Jiabing,WU Biao,et al.Design scheme of IOT terminal server system based on Netty and Kafka[J].Journal of Zhejiang Sci-Tech University,2020,43-44(自科一):240.

备注/Memo

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