THE VALUE OF LOOKAHEAD INFORMATION IN SCHEDULING UNIT LENGTH JOBS ON PARALLEL MACHINES TO MINIMIZE THE EXPECTED MAKESPAN

摘要：

We study the value of lookahead information in a stochastic online-list scheduling problem of n jobs on a set of m multipurpose machines with unit processing times to minimize the expected makespan.There are kdifferent job types, the probability of each type in known and each job type is restricted to be processed on a unique subset of machines.Classically,in online-list scheduling, the scheduler has all the information about the next job to be scheduled,while there is uncertainty about all other is uncertainty about all other jobs in the list not yet scheduled.We extend this classical case to include lookahead abilities,i.e., at each decision point the scheduler has all the information about the next h jobs in the list.We use dynamic programming to find an optimal solution, and through experimental studies we obtain insight into the conditions that make the lookahead information more valuable.

关键词： Multipurpose machine scheduling lookahead information online algorithms eligibility constraint stochastic dynamic programming.

作者: M.Mandelbaum D.Shabtay

作者单位: Department of Computer Science and Engineering,York University,Toronto,Ontario,Canada Department of Industrial Engineering and Managemetn,Ben-Gurion University of the Negev,Beer-Sheva,Is

会议类型: 国际会议

会议名称: 第二十届国际生产研究大会

会议地点: 上海

会议语种:英文

页码: 1-6

在线出版日期: 2009-08-02（万方平台首次上网日期，不代表论文的发表时间）