Browsing by Author "Kononov, A. V."

Now showing 1 - 3 of 3

Customer order scheduling to minimize the number of late jobs
(2007-12-01)
Lin, B. M. T.
;
Kononov, A. V.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
In the order scheduling problem, every job (order) consists of several tasks (product items), each of which will be processed on a dedicated machine. The completion time of a job is defined as the time at which all its tasks are finished. Minimizing the number of late jobs was known to be strongly NP-hard. In this note, we show that no FPTAS exists for the two-machine, common due date case, unless P = NP. We design a heuristic algorithm and analyze its performance ratio for the unweighted case. An LP-based approximation algorithm is presented for the general multicover problem. The algorithm can be applied to the weighted version of the order scheduling problem with a common due date. (c) 2006 Elsevier B.V. All rights reserved.
Minimizing machine assignment costs over Delta-approximate solutions of the scheduling problem P parallel to C-max
(2019-11-12)
Kononov, A. V.
;
Kovalyov, M. Y.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
Bi-criteria lexicographical minimization problems with the makespan as the primary objective and the total machine assignment costs as the secondary objective have been recently introduced to the scheduling research, and polynomial time (r + 1, 1)-approximation algorithms have been suggested for their solution, where 1 < r < 2 is the performance ratio of an approximation algorithm for P parallel to C-max. We improve these results by presenting a polynomial time (1.5r - 1, 1)-approximation algorithm for the additive cost type. Then, we introduce a problem of minimizing the total machine assignment cost over the Delta-approximate solutions of the makespan minimization problem. We prove that this new problem is strongly NP-hard and pseudo-polynomially non-approximable in general. A polynomial time approximation algorithm with a guaranteed approximation ratio is presented for the additive cost type and bounded ratio between the maximal and minimal machine costs. An O (mn(2k)) time dynamic programming algorithm is also presented, where k is the fixed number of distinct job processing times. (C) 2019 Elsevier B.V. All rights reserved.
On relocation problems with multiple identical working crews
(2006-12-01)
Kononov, A. V.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
The relocation problem was formulated from a public housing project. In its basic form, a set of buildings needed to be torn down and erected by a single working crew. Given a fixed budget, the relocation problem seeks to determine a feasible reconstruction sequence of the old buildings. This problem has been shown to be mathematically equivalent to the classical two-machine flowshop of makespan minimization. In this paper, we consider a variant where multiple working crews are available for the redevelopment project. Most of our results center on the situations where all buildings require the same redevelopment time. We first present a strong NP-hardness proof for the case with two working crews. Then, we give a negative result about the approximability of the studied problem. Approximation algorithms and associated performance-ratio analysis are designed for the cases with unbounded as well as bounded numbers of machines. (c) 2006 Elsevier B.V. All rights reserved.