A New Project Scheduling Problem with Worker-Dependent Durations

Byung-Cheon Choi () and Jibok Chung
Additional contact information
Byung-Cheon Choi: School of Business, Chungnam National University, 99 Daehak-ro, Yuseong-gu, Daejeon 34134, South Korea
Jibok Chung: Department of Retail Management, Kongju National University, 54 Daehak-ro, Yesan-eup, Yesan-gun, Chungcheongnam-do 32439, South Korea

Asia-Pacific Journal of Operational Research (APJOR), 2025, vol. 42, issue 05, 1-12

Abstract: In this paper, we introduce a new project scheduling problem with multiple milestones and completely ordered activities. The characteristic of our problem lies in the activity durations, which are determined by the unique attributes of each activity and the worker assigned to it. The objective is to identify the optimal assignment of workers to activities that minimizes the weighted number of tardy activities. We show that the problem is strongly NP-hard by reducing it from the 3-partition problem even for two cases with a special structure of durations. Furthermore, we identify two cases that can be solved in polynomial time.

Keywords: Project scheduling; computational complexity; completely ordered activities (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595925500022
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:42:y:2025:i:05:n:s0217595925500022

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595925500022

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 ().