Single machine scheduling with earliness-tardiness and completion time penalties
This paper considers a single machine scheduling problem with a non-restrictive common due date.The objective is to minimize the sum of earliness,tardiness and completion time penalties.For the case in which the processing time of each job is independent of its position in a schedule,we show the properties of the optimal solution and present a polynomial algorithm.Moreover,for the case where the processing time of each job is related to its position in a schedule,by calculating their positional weights,the problem can be formulated as an assignment problem in polynomial time.And a polynomial algorithm is presented.
scheduling earliness tardiness position- dependent processing times
Yufang Zhao
School of Mathematics and Systems Science Shenyang Normal University Shenyang,Liaoning,110034,China
国际会议
2007 IEEE International Conference on Automation and Lofistics
山东济南
英文
2007-08-18（万方平台首次上网日期，不代表论文的发表时间）