کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
475408 | 699303 | 2016 | 4 صفحه PDF | دانلود رایگان |
• We study a single machine scheduling problem where the objective is minimum total early work.
• A job is penalized according to the duration of its early part.
• We prove that the problem is NP-hard.
• A pseudo-polynomial dynamic programming algorithm is introduced.
• The DP algorithm can solve problems of hundreds of jobs in very reasonable time.
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.
Journal: Computers & Operations Research - Volume 73, September 2016, Pages 115–118