A Time-Cost Tradeoff Problem with Multiple Assessments and Release Times on a Chain Precedence Graph

Myoung Ju Park, Byung Cheon Choi, Jibok Chung

Research output: Contribution to journalArticlepeer-review

Abstract

We consider two variants of a time-cost tradeoff problem with multiple assessments on a chain precedence graph. Furthermore, each job can only be started after a release time, and a penalty cost is incurred when a job is not finished before its due date. The motivation is from the project such that a project owner can control the duration of each job and the support level of each project partner to avoid the penalty cost from the tardy jobs. We describe the penalty costs of the first and the second variants as the total weighted number of tardy jobs and the total weighted tardiness, respectively. These can be avoided by compressing the processing times or advancing the release times, which incurs a compression cost or release cost according to the linear and the piecewise constant functions, respectively. The objective is to minimize the total penalty, compression cost and release cost. In this paper, we propose the procedure based on the reduction to a shortest path problem, and show that the procedure can solve two variants in strongly polynomial time.

Original languageEnglish
Article number2150012
JournalAsia-Pacific Journal of Operational Research
DOIs
Publication statusAccepted/In press - 2021

Keywords

  • Scheduling
  • chain precedence graph
  • computational complexity
  • continuous knapsack problem
  • product development project
  • time-cost tradeoff

Fingerprint

Dive into the research topics of 'A Time-Cost Tradeoff Problem with Multiple Assessments and Release Times on a Chain Precedence Graph'. Together they form a unique fingerprint.

Cite this