在线以及半在线排序调度问题研究

《在线以及半在线排序调度问题研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、上海交通大学博士后研究报告题目：英文题目：姓名：研究方向：博士后编号：合作导师：提交日期：在线以及半在线排序调度问题研究Onlineandsemi—onlineschedulingproblems曹茜专业：管理科学与工程生产计划与排序调度85263万国华职称：教授2012年5月上海交通大学(上海)上海交通大学博十后研究报告第i页摘要螂煳本文主要研究了两台平行机在线以及半在线排序调度问题，其中工件或者订单按照一个给定列表的顺序依次到达，我们要将列表中的工件或者订单按照某种规则安排到这两台平行机上使得所有工件或所有订单的最大完工时间最小，即我们的目标是最小化时间表长。本文第二章考虑

2、了四个关于两台同型机的已知订单部分信息的在线排序调度问题。第一个问题考虑己知每个订单的总加工时间都为T的问题，对订单数b22，我们得到了问题的下界为兰，并设计了一个最优算法A1；对b≥3，我们得到了下界为；，并设计了一个最优算法A2。第二个问题考虑已知6个订单按照总加工时间非增序到达的问题，当b≥2时，得到了问题的下界为；，因此Ls算法是最优的。第三个问题考虑已知每个订单中的最大工件加工时间且都相同的问题，当b≥2时，我们获得了问题的下界为2，并设计了一个最优算法A3。第四个问题考虑己知6个订单按照每个订单中最大工件加工时间非增序到达的问题，当b≥2时，我们获得了问题的下界为≥

3、，并设计了一个最优算法A4。第三章考虑了三个己知组合信息的两台同型机半在线排序调度问题。第一个问题考虑已知工件按加工时间的非增序到达且所有工件的加工时间在区间[1，t]((￡≥1))内的问题，我们给出了问题的下界为兄=Ⅳ：m。，a2x，3，⋯{min4N+3，裂))，并证明-fLS算法在1≤t<害时是最优的。第二个问题考虑己知最大工件的加工时间t且所有工件的加工时间在区间[1，t]((亡≥1))内的问题，我们给出了问题的下界为12。然后又对3st<2设计了一个最优算法P，Js。第三个问题考虑已知最优解值和最大工件的加工时间pm∞的

4、问题，我们得到了问题的下界为2，并设计了一个竞，．．寸．一4，m丁¨而班一Ⅲ生即一卜

5、海交通大学博七后研究报告第ii页争比也为：的最优算法OM。第四章考虑了三个与缓冲区有关的两台同型机半在线排序调度问题。第一个问题考虑已知最大工件尺寸且带～个长度为k(忌≥1)的缓冲区的问题，我们给出了问题的下界为g，同时设计了一个竞争比为；的算法。第二个问题考虑已知工件按照加工时间非增序到达且带一个长度为1的缓冲区的两台同型机半在线排序调度问题，我们得到了问题的下界为；。第三个问题考虑已知工件加工时间有界且带一个长度为1的缓冲区的两台同型机半在线排序调度问题，我们给出了问题的一个下界max卜{

6、刍半)，m叫刍半)jm叫；半)>，同时对1≤t≤；设计了～个竞争比为maX{警，；)的算法BB，且该算法在半≤t≤墨2是最优的。第五章考虑了所有工件加工时间是有界的两台同类机半在线排序调度问题，，目标同样是最小化时间表长。我们首先对问题证明了一些下界，并研究TLS算法的竞争比。首先我们在对任意s和亡得到上s算法的竞争比为min{料，了s+l，￡)，结合我们给出的下界可知Ls算法在s≥盟世学±业且亡≥寿时是最优的，竞争比为了s+l；在N≤s≤N+lJ

7、．1≤t≤min{s_-与，寿)时是最优的，竞争比为t；在1≤s≤址2丛且t≥虿l+s时是最优的，竞争比为百2s+Tl。然后我们又

8、对LS算法进行深入分析，得至IJLS算法在max{鹆将，舞器㈦≤；2axt—丽耳Tj矿，两了可百订i口，∑‘∑；和maX{坐鼍憋茜磐案署罟掣，丙sN+-，N一。+Ⅳs，1．≤t≤min。2s(2NⅣ++I，)一-22。NⅣ-1-，芬等)是最优的。进一步，我们证明了其在s≤N+1且t2未箬帚b时的竞争比为半，并在盟堑乒巫≤s≤N+1_Emax{未箬器，由)≤￡≤寿时是最优的。最后我们设计了两个改进的算法，在1．325≤s≤生乎且s

9、．206且．s≤t≤min{2s一1，瓣2(s2-1))时的竞争比为s，也达到了最优。关键词：排序调度，同犁机，同类机，在线，半在线上海交通大学博十后研究报告第iii页AbstractThispapermainlyinvestigatesonlineandsemi—onlineschedulingproblemsontwoparallelmachines，wherewearegivenalistofthejobsortheordersthataretobeassignedonebyoneto