Scheduling two projects with controllable processing times in a single-machine environment

  • PDF / 433,725 Bytes
  • 10 Pages / 595.276 x 790.866 pts Page_size
  • 40 Downloads / 197 Views

DOWNLOAD

REPORT


Scheduling two projects with controllable processing times in a single-machine environment Byung-Cheon Choi1 · Myoung-Ju Park2

© Springer Science+Business Media, LLC, part of Springer Nature 2020

Abstract We consider two single-machine scheduling problems in which two competing projects share one common resource. Each project has multiple interim assessments, and its own jobs are ordered completely. A tardy job incurs a tardiness penalty cost which can be avoided by compressing some jobs, which requires an additional cost. The performance measure of each project is the total tardiness penalty cost plus the total compression cost. The first problem minimizes the weighted sum of the performance measures of two projects, and the second problem minimizes the performance measure of one project with a constraint on that of the other. We show that the first problem is solvable in strongly polynomial time and the second is weakly NP-hard. Furthermore, we analyze how the computational complexity of each problem changes if the number of projects is more than two. Keywords Scheduling · Two-agent sequencing · Computational complexity

1 Introduction We consider two single-machine scheduling problems with two competing projects. For each project, • The jobs are ordered completely, which implies that the precedence graph is a chain; • Each job has its own due date and a tardiness penalty cost is occurred when it is tardy, that is, it is completed after its due date; • The tardiness penalty can be avoided by compressing the processing times of some jobs, which induces an additional cost; • The performance measure (PM) is the total tardiness penalty cost plus the total compression cost.

B

Myoung-Ju Park [email protected] Byung-Cheon Choi [email protected]; [email protected]

1

School of Business, Chungnam National University, 99 Daehak-ro, Yuseong-gu, Daejeon 34134, Korea

2

Department of Industrial and Management Systems Engineering, Kyung Hee University, 1732, Deogyeong-daero, Giheung-gu, Yongin-si, Kyunggi-do 17104, Korea

The first problem minimizes the weighted sum of the PMs of two projects, and the second problem minimizes the PM of one project subject to the other project’s PM not exceeding a given threshold. Note that, if a single project exists, then our problem is reduced to a time–cost tradeoff problem (TCTP) with multiple interim assessments, which was introduced by Choi and Chung (2014) and Choi and Park (2015). See Falk and Horowitz (1972); Ford and Fulkerson (1962); Fulkerson (1961); Kelley (1961) for the traditional TCTP with a single assessment. The motivation of our problems is from the situation such that a single-person software company simultaneously manages several projects ordered by others, and has no choice but to deal with one at a time due to resource constraints. Multiple interim assessments have been planned throughout each project, and some penalty occurs, if the project is not progressed to the appointed level at each interim assessment. The company can avoid the penalty by allocating