본문 바로가기
  • Home

A time-cost tradeoff problem with multiple interim assessments under the precedence graph with two chains in parallel

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2018, 23(3), pp.85-92
  • DOI : 10.9708/jksci.2018.23.03.085
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science
  • Received : January 30, 2018
  • Accepted : February 28, 2018
  • Published : March 30, 2018

Choi Byung-Cheon 1 Yun-Hong Min 2

1충남대학교
2인천대학교

Accredited

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.

Citation status

* References for papers published after 2022 are currently being built.