A dynamic programming algorithm for scheduling problems on earliness award and tardiness penalty with time-dependent processing time  

作　　者：余英 孙世杰 何龙敏 

机构地区：[1]Department of Mathematics, College of Sciences, Shanghai University, Shanghai 200444, P. R. China

出　　处：《Journal of Shanghai University(English Edition)》2008年第3期204-209,共6页上海大学学报（英文版）

摘　　要：In this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total weighted earliness award and tardiness penalty. Our aim is to find an optimal schedule so as to minimize the objective function. As the problem is NP-hard, some properties and polynomial time solvable cases of this problem are given. A dynamic programming algorithm for the general case of the problem is provided.In this paper, a single-machine scheduling model with a given common due date is considered. Job processing time is a linear decreasing function of its starting time. The objective function is to minimize the total weighted earliness award and tardiness penalty. Our aim is to find an optimal schedule so as to minimize the objective function. As the problem is NP-hard, some properties and polynomial time solvable cases of this problem are given. A dynamic programming algorithm for the general case of the problem is provided.

关 键 词：scheduling SINGLE-MACHINE linear decreasing processing time EARLINESS TARDINESS 

分 类 号：O22[理学—运筹学与控制论]