Browsing by Author "Kononov, Alexander V."

Now showing 1 - 3 of 3

Minimizing the total weighted completion time in the relocation problem
(2010-04-01)
Kononov, Alexander V.
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper studies the minimization of total weighted completion time in the relocation problem on a single machine. The relocation problem, formulated from an area redevelopment project, can be treated as a resource-constrained scheduling problem. In this paper, we show four special cases to be NP-hard in the strong sense. Problem equivalence between the unit-weighted case and the UET (unit-execution-time) case is established. For two further restricted special cases, we present a polynomial time approximation algorithm and show its performance ratio to be 2.
Relocation scheduling subject to fixed processing sequences
(2016-04)
Lin, Bertrand M. T.
;
Hwang, F. J.
;
Kononov, Alexander V.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This study addresses a relocation scheduling problem that corresponds to resource-constrained scheduling on two parallel dedicated machines where the processing sequences of jobs assigned to the machines are given and fixed. Subject to the resource constraints, the problem is to determine the starting times of all jobs for each of the six considered regular performance measures, namely, the makespan, total weighted completion time, maximum lateness, total weighted tardiness, weighted number of tardy jobs, and number of tardy jobs. By virtue of the proposed dynamic programming framework, the studied problem for the minimization of makespan, total weighted completion time, or maximum lateness can be solved in time, where and are the numbers of jobs on the two machines. The simplified case with a common job processing time can be solved in time. For the objective function of total weighted tardiness or weighted number of tardy jobs, this problem is proved to be NP-hard in the ordinary sense, and the case with a common job processing length is solvable in time. The studied problem for the minimization of number of tardy jobs is solvable in time. The solvability of the common-processing-time problems can be generalized to the m-machine cases, where .
Single-machine scheduling with supporting tasks
(2015-08-01)
Kononov, Alexander V.
;
Lin, Bertrand M. T.
;
Fang, Kuei-Tang
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper investigates a single-machine scheduling problem with a set of supporting tasks and a set of jobs. Each job is preceded by a subset of supporting tasks, that is, the job cannot start its processing until all of its supporting tasks are finished. The objective functions are defined solely in job completion times. We discuss the complexities of several special cases for the number of late jobs and the total weighted completion time. This study adds new complexity results to the two standard objective functions under precedence constraints. (C) 2015 Elsevier B.V. All rights reserved.