## Abstract

We consider a single-machine scheduling problem such that the due date is assigned not to a specific job, but to a job position, with identical intervals between consecutive due dates. We refer to the job as a large job if its processing time is greater than the interval, and as a small job, otherwise. The objective is to minimize the sum of the earliness and tardiness of each job. We analyze how the computational complexity changes depending on the number of large jobs, denoted n_{l}. First, we show that problems with n_{l}∈{3,4,…,n−1} and n_{l}∈{0,1,n} are NP-hard and polynomially solvable, respectively, where n is the number of jobs. Note that the computational complexity of the case with n_{l}=2 is open. Then, we show that, when idle time is not allowed, problems with n_{l}∈{1,2,…,n−1} and n_{l}∈{0,n} are NP-hard and polynomially solvable, respectively. Furthermore, we develop a heuristic for the problem with no idle time and verify its extremely good performance through numerical experiments.

Original language | English |
---|---|

Pages (from-to) | 31-52 |

Number of pages | 22 |

Journal | Discrete Applied Mathematics |

Volume | 314 |

DOIs | |

Publication status | Published - 15 Jun 2022 |

### Bibliographical note

Publisher Copyright:© 2022 Elsevier B.V.

## Keywords

- Computational complexity
- Generalized due dates
- Scheduling