Min-Max Regret Version of the Linear Time–Cost Tradeoff Problem with Multiple Milestones and Completely Ordered Jobs

Byung-Cheon Choi and Myoung-Ju Park ()
Additional contact information
Byung-Cheon Choi: Department of Business Administration, Chungnam National University, 79 Daehangno, Yuseong-gu, daejeon 305-704, Korea
Myoung-Ju Park: Department of Industrial and Management Systems Engineering, Kyung Hee University, 1732, Deogyeong-daero, Giheung-gu, Yongin-si, Kyunggi-do 446-701, Korea

Asia-Pacific Journal of Operational Research (APJOR), 2015, vol. 32, issue 05, 1-16

Abstract: We consider a linear time–cost tradeoff problem with multiple milestones and uncertain processing times such that all jobs are completely ordered. The performance measure is expressed as the sum of total weighted number of tardy jobs and total crashing cost. The processing times uncertainty is described through two types of scenarios: discrete and interval scenarios. The objective is to minimize maximum deviation from optimality over all scenarios. For the discrete scenario case, we prove its NP-hardness, develop a pseudo-polynomial time approach, and present a polynomially solvable case. Finally, we show that the interval scenario case is also NP-hard.

Keywords: Project scheduling; time–cost tradeoff; uncertain processing times; computational complexity (search for similar items in EconPapers)
Date: 2015
References: View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.worldscientific.com/doi/abs/10.1142/S0217595915500396
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:32:y:2015:i:05:n:s0217595915500396

Ordering information: This journal article can be ordered from

DOI: 10.1142/S0217595915500396

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