Strong NP-hardness of minimizing total deviation with generalized and periodic due dates |
| |
Abstract: | We consider a single-machine scheduling problem with generalized and periodic due dates such that each due date is assigned not to a specific job but to a position and the lengths of the intervals between consecutive due dates are identical. The objective is to minimize the total deviation, which is calculated as the sum of the earliness and tardiness of each job. We show that the problem is strongly NP-hard. We develop a heuristic and verify its performance via experiments. |
| |
Keywords: | Scheduling Generalized due dates Periodic due dates Logistics |
本文献已被 ScienceDirect 等数据库收录! |