Research on single-machine scheduling with position-dependent weights and past-sequence-dependent delivery times

Ji Bo Wang, Bo Cui, Ping Ji, Wei Wei Liu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

2 Citations (Scopus)


This article studies scheduling problems with past-sequence-dependent delivery times (denoted by psddt) on a single-machine, i.e., the delivery time of a job depends on its waiting time of processing. We prove that the total (discounted) weighted completion time minimization can be solved in O(nlog n) time, where n is the number of jobs, and the weight is a position-dependent weight. For common (denoted by con) and slack (denoted by slk) due-date assignment and position-dependent weights (denoted by pdw), we prove that an objective cost minimization is solvable in O(nlog n) time. The model (i.e., psddt and pdw) can also be extended to position-dependent (time-dependent) processing times.

Original languageEnglish
Pages (from-to)290-303
Number of pages14
JournalJournal of Combinatorial Optimization
Issue number2
Publication statusPublished - Feb 2021


  • Delivery time
  • Position-dependent weight
  • Scheduling
  • Single-machine

ASJC Scopus subject areas

  • Computer Science Applications
  • Discrete Mathematics and Combinatorics
  • Control and Optimization
  • Computational Theory and Mathematics
  • Applied Mathematics

Cite this