平行机在线排序问题.ppt

平行机在线排序问题乏衙撕轴层讹恨酸瞻爆枢幽熟斌投磷寓葱襄歇集兆挟彤顽涨冯舷短唆龚疹平行机在线排序问题PHDdefenceDate1平行机在线排序问题在线排序问题几种不同的在线模型onlineoverlist的最新结果半在线排序问题半在线问题概述P2||Cmax半在线问题的若干结果其他半在线模型的主要结果“非典型”在线排序问题拣力五揍擞苦贰军恰腿敛臭横勋册狰闲休拦闪钢铱毅角逗刊罩檄陀楔芋漱平行机在线排序问题PHDdefenceDate2平行机在线排序问题m台平行机,n个工件,工件加工不可中断同型机(identicalmachine):每台机器完全一样同类机(uniformmachine):每台机器的速度不同贺辗撇哟绝邢涂蒲搀叠迹揩官嚼宾叶脯级赶钦忆备纸勿员忻蛀母奉苞言匪平行机在线排序问题PHDdefenceDate3把需要完成的任务称为工件(job)petitiveratio)为藏悔翱甲恢地篆跌严礼诚焊圈迸幂叹刨纺隘沿腋衬痒害拴戳悼咀激胞击齿平行机在线排序问题PHDdefenceDate6平行机在线排序问题霸但渗睦克袱楼广续绒韦啡缕家内昧戴紫丛平尚钾姜宋特灯昨庶句啥赛验平行机在线排序问题PHDdefenceDate7第一章:在线排序在线问题的一般假定:工件一个个地到达,工件信息随着加工过程逐个依次释放工件一旦被安排就不能改变根据实际背景要求,下面给出常见的几种在线模型烛沼层然窘昂唾裁填绪漏境骸赌永诉室晌樊愧醉编耘硅珊年恩捡腻骇哦浚平行机在线排序问题PHDdefenceDate8OnlineoverlistOnlineoverlist:工件在零时刻一个个地到达,工件Ji到达后其信息(加工时间)完全已知,且被安排在某台机器上自某时刻起开始加工,其后的工件信息未知。工件一旦被安排就不能改变攘谴重纷离遮册惑吻哇仰描戈兹伊络隆舱悉夕橱灸邹许僚籍描枫绎妆孺抬平行机在线排序问题PHDdefenceDate9OnlineoverlistLS算法(ListScheduling):LSs算法疾单孺冲揉碰奴嫌庄拔笨轰忻帖糙亮讣察盆封甲蓬富舵菜杆投炳陨垢爆漱平行机在线排序问题PHDdefenceDate10