Browsing by Author "Lin, Feng-Cheng"

Now showing 1 - 3 of 3

A two-machine flowshop problem with processing time-dependent buffer constraints-An application in multimedia presentations
(2009-04-01)
Lin, Feng-Cheng
;
Hong, Jen-Shin
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
To have a quality multimedia presentation through networks, its presentation lag needs to be controlled. One way to reduce the lag is to prefetch the media objects before their due dates. This paper explores techniques for optimizing the object sequence in a prefetch-enabled TV-like presentation. An optimal solution is the one with which the presentation lag is minimized. We formulate the problem into a two-machine flowshop scheduling problem with a single chain precedence constraint and a player-side buffer constraint. The player-side buffer is "processing time-dependent" and distinguished from the conventional item-based intermediate buffer constraints discussed in previous flowshop studies. We prove the problem to he strongly NP-hard. A branch and bound algorithm equipped with four lower bounds and an NEH-based upper bound is developed. The simulation results show that the average gaps between the overall lower bounds and the NEH-based upper bound are less than 3% for problems with a large buffer size, and less than 13% for problems with a small buffer size and high density of precedence constraints. For applications where the media objects are delivered through extremely busy servers with which only very restricted CPU resources can be allocated for computation, the CDS-based algorithm provides better sequences than the NEH-based algorithm. (C) 2008 Elsevier Ltd. All rights reserved.
Clarification of lower bounds of two-machine flow-shop scheduling to minimize total late work
(2019-07-03)
Blazewicz, Jacek
;
Chen, Xin
;
Lee, Richard C. T.
;
Lin, Bertrand M. T.
;
Lin, Feng-Cheng
Sequence optimization for media objects with due date constraints in multimedia presentations from digital libraries
(2012-03-01)
Lin, Feng-Cheng
;
Hong, Jen-Shin
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This study investigates sequence optimization of media objects in a multimedia presentation that is dynamically composed from digital libraries. Each media object can be associated with a due date. The aim is to schedule the media objects in a delay-prone network environment such that the overall presentation lag and the due date penalties of the media objects of presentations can be minimized. We formulate the sequencing problem with buffer constraints in the media player into a flowshop scheduling problem and present a reduction strategy with a branch and bound algorithm to derive optimal sequences. The algorithm can be applied in applications with up to a dozen objects to be scheduled. In addition, we propose a modified NEH-based heuristic algorithm which can provide approximate solutions with an average error rate of less than 4%. The computation-efficient heuristic, when deployed in applications with heavily loaded servers, can obtain near-optimal sequences for problems with more than a dozen objects. The proposed algorithms are embedded into a prototype system for providing digital library services. (c) 2012 Elsevier Ltd. All rights reserved.