Browsing by Author "Huang, Hsiao-Lan"

Now showing 1 - 2 of 2

TALENT HOLD COST MINIMIZATION IN FILM PRODUCTION
(2017-01)
Cheng, Tai Chiu Edwin
;
Lin, Bertrand Miao-Tsong
;
Huang, Hsiao-Lan
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper investigates the talent scheduling problem in film production, which is known as rehearsal scheduling in music and dance performances. The first lower bound on the minimization of talent hold cost is based upon the outside-in branching strategy. We introduce two approaches to add extra terms for tightening the lower bound. The first approach is to formulate a maximum weighted matching problem. The second approach is to retrieve structural information and solve a maximum weighted 3-grouping problem. We make two contributions: First, our results can fathom the matrix of a given partial schedule. Second, our second approach is free from the requirement to schedule some shooting days in advance for providing anchoring information as in the other approaches, i.e., a lower bound can be computed once the input instance is given. The lower bound can fit different branching strategies. Moreover, the second contribution provides a state-of-the-art research result for this problem. Computational experiments con firm that the new bounds are much tighter than the original one.
Tight complexity analysis of the relocation problem with arbitrary release dates
(2011-08-12)
Sevastyanov, Sergey V.
;
Lin, Bertrand M. T.
;
Huang, Hsiao-Lan
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
The paper considers makespan minimization on a single machine subject to release dates in the relocation problem, originated from a resource-constrained redevelopment project in Boston. Any job consumes a certain amount of resource from a common pool at the start of its processing and returns to the pool another amount of resource at its completion. In this sense, the type of our resource constraints extends the well-known constraints on resumable resources, where the above two amounts of resource are equal for each job. In this paper, we undertake the first complexity analysis of this problem in the case of arbitrary release dates. We develop an algorithm, based on a multi-parametric dynamic programming technique (when the number of parameters that undergo enumeration of their values in the DP-procedure can be arbitrarily large). It is shown that the algorithm runs in pseudo-polynomial time when the number m of distinct release dates is bounded by a constant. This result is shown to be tight: (1) it cannot be extended to the case when m is part of the input, since in this case the problem becomes strongly NP-hard, and (2) it cannot be strengthened up to designing a polynomial time algorithm for any constant m > 1, since the problem remains NP-hard for m = 2. A polynomial-time algorithm is designed for the special case where the overall contribution of each job to the resource pool is nonnegative. As a counterpart of this result, the case where the contributions of all jobs are negative is shown to be strongly NP-hard. (C) 2011 Elsevier B.V. All rights reserved.