版权所有:内蒙古大学图书馆 技术提供:维普资讯• 智图
内蒙古自治区呼和浩特市赛罕区大学西街235号 邮编: 010021
作者机构:Department of Civil Engineering and Operations Research Princeton University Princeton NJ 08544 USA
出 版 物:《OPERATIONS RESEARCH LETTERS》 (Oper Res Lett)
年 卷 期:1995年第17卷第3期
页 面:127-129页
核心收录:
学科分类:1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学]
主 题:SCHEDULING SINGLE-PROCESSOR DYNAMIC PROGRAMMING POLYNOMIAL-TIME ALGORITHM
摘 要:We consider a single-processor scheduling model where the execution time of a task is a decreasing linear function of its starting time. The complexity of the problem of minimizing the number of late tasks remains unknown for a set of tasks with identical due dates. We present an O(n(2))-time dynamic programming algorithm for solving this problem.