具有预约到达时间的平行机在线排序问题研究  

On-line Scheduling of Jobs with Order Arrival Time and Hard Deadline on Two Parallel Identical Machines

作　　者：张显东[1] 吴克文[1] 王锦[1] 

机构地区：[1]复旦大学管理学院,上海200433

出　　处：《复旦学报（自然科学版）》2009年第6期708-712,共5页Journal of Fudan University：Natural Science

基　　金：国家自然科学基金重点资助项目(70432001)

摘　　要：以现代服务业预定系统中的实际问题为背景,研究了一类具有预约到达时间和最迟完工时间的在线排序问题;论证了两台机器时该问题的在线算法竞争比下界为2;在传统在线排序算法的基础上提出了针对该问题的在线贪婪算法,并分析了该算法的竞争比.On-line scheduling of independent jobs with order arrival time and hard deadlines is an extension of traditional on-line scheduling problems. Based on real booking systems in modern service industry, on-line scheduling of independent jobs with arbitrary order arrival time, job release times and hard deadlines on two parallel identical machines is studied. The upper bound of competitive ratios of on-line algorithms for the twomachine case is analyzed. An on-line greedy algorithm with a competitive ratio of 3 is presented.

关 键 词：在线排序 平行机排序 预约到达时间 最迟完工时间 

分 类 号：C93[经济管理—管理学]