Four single-machine scheduling problems involving due date determination decisions

Yunqiang Yin, Min Liu, Edwin Tai Chiu Cheng, Chin Chia Wu, Shuenn Ren Cheng

Research output: Journal article publicationJournal articleAcademic researchpeer-review

25 Citations (Scopus)

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 languageEnglish
Pages (from-to)164-181
Number of pages18
JournalInformation Sciences
Volume251
DOIs
Publication statusPublished - 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

Cite this