Scheduling about a given common due date to minimize mean squared deviation of completion times

作     者：Weng, XH Ventura, JA 

作者机构：PENN STATE UNIVDEPT IND & MANAGEMENT SYST ENGNUNIVERSITY PKPA 16802 

出 版 物：《EUROPEAN JOURNAL OF OPERATIONAL RESEARCH》 (欧洲运筹学杂志)

年 卷 期：1996年第88卷第2期

页      面：328-335页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：production scheduling minimizing mean squared deviation dynamic programming exact algorithm 

摘      要：In this paper the problem of minimizing the mean squared deviation (MSDP) of job completion times about a given common due date in n-job, single-machine scheduling is considered. The release times for all jobs are assumed to be zero. No polynomial time algorithms have been found to identify an optimal solution to MSDP. For the tightly restricted version of MSDP, no even pseudo-polynomial time algorithms have been found to identify an optimal solution. We present some dominance properties for MSDP based on which a pseudo-polynomial dynamic programming algorithm which is an extension of the dynamic programming algorithm proposed by Lee, Danusaputro and Lin is presented to optimally solve the tightly restricted version of MSDP. Computational results show that the proposed dynamic programming algorithm can optimally solve tightly restricted instances of MSDP with up to 100 jobs in less than two seconds.