Single-machine scheduling with periodic due dates to minimize the total earliness and tardy penalty |
| |
Authors: | Choi Byung-Cheon Park Myoung-Ju |
| |
Institution: | 1.School of Business, Chungnam National University, 99 Daehak-ro, Yuseong-gu, Daejeon, 34134, Korea ;2.Department of Industrial and Management Systems Engineering, Kyung Hee University, 1732, Deogyeong-daero, Giheung-gu, Yongin-si, Kyunggi-do, 17104, Korea ; |
| |
Abstract: | We consider a single-machine scheduling problem such that the due dates are assigned to each job depending on its order, and the lengths of the intervals between consecutive due dates are identical. The objective is to minimize the total penalty for the earliness and tardiness of each job. The early penalty proportionally increases according to the earliness amount, while the tardy penalty increases according to the step function. We show that the problem is strongly NP-hard, and furthermore, polynomially solvable if the two types of processing times exist. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|