A NOTE ON SINGLE-PROCESSOR SCHEDULING WITH TIME-DEPENDENT EXECUTION TIMES

作     者：CHEN, ZL 

作者机构：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.