Abstract
This paper considers single-machine scheduling problems with simultaneous consideration of due date assignment, past-sequence-dependent (p-s-d) delivery times, and position-dependent learning effects. By p-s-d delivery times, we mean that the delivery time of a job is proportional to the job's waiting time. Specifically, we study four variants of the problem: (i) the variant of total earliness and tardiness with common due date assignment (referred to as TETDC), (ii) the variant of total earliness and weighted number of tardy jobs with CON due date assignment (referred to as TEWNTDC), (iii) the variant of total earliness and weighted number of tardy jobs with slack due date assignment (referred to as TEWNTDS), and (iv) the variant of weighted number of tardy jobs with different due date assignment (referred to as WNTDD). We derive the structural properties of the optimal schedules and show that the variants TETDC, TEWNTDC and TEWNTDS are all polynomially solvable. Although the complexity status of the variant WNTDD is still open, we show that two special cases of it are polynomially solvable.
Original language | English |
---|---|
Pages (from-to) | 164-181 |
Number of pages | 18 |
Journal | Information Sciences |
Volume | 251 |
DOIs | |
Publication status | Published - 1 Dec 2013 |
Keywords
- Due date assignment
- Past-sequence-dependent delivery time
- Position-dependent learning effect
- Scheduling
ASJC Scopus subject areas
- Software
- Control and Systems Engineering
- Theoretical Computer Science
- Computer Science Applications
- Information Systems and Management
- Artificial Intelligence