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

Myoung-Ju Park (), Byung-Cheon Choi () and Jibok Chung
Additional contact information
Myoung-Ju Park: Department of Industrial and Management Systems Engineering, Kyung Hee University, 1732, Deogyeong-daero, Giheung-gu, Yongin-si, Kyunggi-do 17104, Korea
Byung-Cheon Choi: Department of Business Administration, Chungnam National University, 79 Daehangno, Yuseong-gu, Daejeon 305-704, Korea
Jibok Chung: Department of Retail Management, Kongju National University, 54 Daehak-ro, Yesan-eup, Yesan-gun, Chungcheongnam-do 32439, Korea

Asia-Pacific Journal of Operational Research (APJOR), 2021, vol. 38, issue 06, 1-20

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.

Keywords: Scheduling; time–cost tradeoff; computational complexity; chain precedence graph; product development project; continuous knapsack problem (search for similar items in EconPapers)
Date: 2021
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595921500123
Access to full text is restricted to subscribers

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wsi:apjorx:v:38:y:2021:i:06:n:s0217595921500123

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595921500123

Access Statistics for this article

Asia-Pacific Journal of Operational Research (APJOR) is currently edited by Gongyun Zhao

More articles in Asia-Pacific Journal of Operational Research (APJOR) from World Scientific Publishing Co. Pte. Ltd.
Bibliographic data for series maintained by Tai Tone Lim ().