두 개의 병렬체인으로 표현되는 우선순위 그래프에서 중간 평가가 있는 시간-비용 프로젝트 문제
A time-cost tradeoff problem with multiple interim assessments under the precedence graph with two chains in parallel
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
We consider a project scheduling problem in which the jobs can be compressed by using additional resource to meet the corresponding due dates, referred to as a time-cost tradeoff problem. The project consists of two independent subprojects of which precedence graph is a chain. The due dates of jobs constituting the project can be interpreted as the multiple assessments in the life of project. The penalty cost occurs from the tardiness of the job, while it may be avoided through the compression of some jobs which requires an additional cost. The objective is to find the amount of compression that minimizes the total tardy penalty and compression costs. Firstly, we show that the problem can be decomposed into several subproblems whose number is bounded by the polynomial function in , where is the total number of jobs. Then, we prove that the problem can be solved in polynomial time by developing the efficient approach to obtain an optimal schedule for each subproblem.
Abstract
We consider a project scheduling problem in which the jobs can be compressed by using additional resource to meet the corresponding due dates, referred to as a time-cost tradeoff problem. The project consists of two independent subprojects of which precedence graph is a chain. The due dates of jobs constituting the project can be interpreted as the multiple assessments in the life of project. The penalty cost occurs from the tardiness of the job, while it may be avoided through the compression of some jobs which requires an additional cost. The objective is to find the amount of compression that minimizes the total tardy penalty and compression costs. Firstly, we show that the problem can be decomposed into several subproblems whose number is bounded by the polynomial function in , where is the total number of jobs. Then, we prove that the problem can be solved in polynomial time by developing the efficient approach to obtain an optimal schedule for each subproblem.
참고문헌 (16)
- C. Artigues, "Resource- Constrained Project Scheduling" (2008), Wiley
- E.B. Berman, "Resource allocation in a PERT network under continuous activity time-cost function", Management Science, 10, pp.734~745 (1964)[DOI]
- J. Bell, "Beauty is in the eye of the beholder: Establishing a fair and equitable value for embryonic high-tech enterprises", Venture Capital Journal, 40, pp.33~34 (2000)
- Peter Brucker, "Resource-constrained project scheduling: Notation, classification, models, and methods", European Journal of Operational Research, 112(1), pp.3~41 (1999), Elsevier BV[DOI]
- Byung-Cheon Choi, "Complexity results for the linear time–cost tradeoff problem with multiple milestones and completely ordered jobs", European Journal of Operational Research, 236(1), pp.61~68 (2014), Elsevier BV[DOI]
- Byung-Cheon Choi, "A continuous time–cost tradeoff problem with multiple milestones and completely ordered jobs", European Journal of Operational Research, 244(3), pp.748~752 (2015), Elsevier BV[DOI]
- 최병천, "Some Special Cases of a Continuous Time-Cost Tradeoff Problem with Multiple Milestones under a Chain Precedence Graph", MSFE, 22(1), pp.5~12 (2016), 한국경영과학회[DOI]
- E.L. Demeulemeester, "Project scheduling - A research handbook" (2002), Kluwer Academic
- D. R. Fulkerson, "A Network Flow Computation for Project Cost Curves", Management Science, 7(2), pp.167~178 (1961), Institute for Operations Research and the Management Sciences (INFORMS)[DOI]
- James E. Falk, "Critical Path Problems with Concave Cost-Time Curves", Management Science, 19(4-part-1), pp.446~455 (1972), Institute for Operations Research and the Management Sciences (INFORMS)[DOI]
- James E. Kelley, "Critical-Path Planning and Scheduling: Mathematical Basis", Operations Research, 9(3), pp.296~320 (1961), Institute for Operations Research and the Management Sciences (INFORMS)[DOI]
- L. R. Lamberson, "Optimum Time Compression in Project Scheduling", Management Science, 16(10), pp.B-597~B-606 (1970), Institute for Operations Research and the Management Sciences (INFORMS)[DOI]
- John Moussourakis, "Project Compression with Nonlinear Cost Functions", Journal of Construction Engineering and Management, 136(2), pp.251~259 (2010), American Society of Civil Engineers (ASCE)[DOI]
- W.A. Sahlmann, "Insights from the ventures capital model of project governance", Business Economics, 29, pp.35~41 (1994)
- J. Weglarz, "Project scheduling - Recent models algorithms and applications" (1999), Kluwer Academic
- Jan Węglarz, "Project scheduling with finite or infinite number of activity processing modes – A survey", European Journal of Operational Research, 208(3), pp.177~205 (2011), Elsevier BV[DOI]