A single machine scheduling problem to minimize total early work

作者：Ben Yehoshua Yoav; Mosheiov Gur^*

来源：Computers & Operations Research, 2016, 73: 115-118.

DOI：10.1016/j.cor.2016.03.010

• Scheduling
• Single machine
• Total early work
• Dynamic programming

We study a single machine scheduling problem, where the objective is minimum total early work. In this setting, a job is penalized according to the duration of the parts of the job completed prior to its due-date. First we prove that the problem is NP-hard. Then, based on a number of properties of an optimal schedule, we introduce a pseudo-polynomial dynamic programming algorithm, verifying NP-hardness in the ordinary sense. Our numerical tests indicate that the dynamic programming solves problems of hundreds of jobs in very reasonable time.

• 出版日期2016-9