Browsing by Author "Kovalyov, M. Y."

Now showing 1 - 3 of 3

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.
Scheduling for fabrication and assembly in a two-machine flowshop with a fixed job sequence
(2014-06-01)
Hwang, F. J.
;
Kovalyov, M. Y.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper studies a problem of scheduling fabrication and assembly operations in a two-machine flowshop, subject to the same predetermined job sequence on each machine. In the manufacturing setting, there are n products, each of which consists of two components: a common component and a unique component which are fabricated on machine 1 and then assembled on machine 2. Common components of all products are processed in batches preceded by a constant setup time. The manufacturing process related to each single product is called a job. We address four regular performance measures: the total job completion time, the maximum job lateness, the total job tardiness, and the number of tardy jobs. Several optimality properties are presented. Based upon the concept of critical path and block schedule, a generic dynamic programming algorithm is developed to find an optimal schedule in O(n(7)) time.
Total completion time minimization in two-machine flow shop scheduling problems with a fixed job sequence
(2012-02-01)
Hwang, F. J.
;
Kovalyov, M. Y.
;
Lin, B. M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper addresses scheduling n jobs in a two-machine flow shop to minimize the total completion time, subject to the condition that the jobs are processed in the same given sequence on both machines. A new concept of optimal schedule block is introduced, and polynomial time dynamic programming algorithms employing this concept are derived for two specific problems. In the first problem, the machine-2 processing time of a job is a step increasing function of its waiting time between the machines, and a decision about machine-1 idle time insertion has to be made. This problem is solved in O(n(2)) time. In the second problem, the jobs are processed in batches and each batch is preceded by a machine-dependent setup time. An O(n(5)) algorithm is developed to find an optimal batching decision. (C) 2011 Elsevier B.V. All rights reserved.