Browsing by Author "CHENG, TCE"

Now showing 1 - 2 of 2

MINIMIZING THE MAKESPAN IN THE 3-MACHINE ASSEMBLY-TYPE FLOWSHOP SCHEDULING PROBLEM
(1993-05-01)
LEE, CY
;
CHENG, TCE
;
LIN, BMT
;
資訊工程學系
;
Department of Computer Science
This paper considers minimizing the makespan in the 3-machine assembly-type flowshop scheduling problem. After problem formulation, we present a proof to show that the general version of this problem is strongly NP-complete. We then discuss a few polynomially solvable cases of the problem and present the solution algorithms. Next, a branch and bound solution scheme is suggested. Finally, three heuristics to find approximate solutions to the general problem are proposed and their error bounds are analyzed.
OPTIMAL SCHEDULING IN FILM PRODUCTION TO MINIMIZE TALENT HOLD COST
(1993-12-01)
CHENG, TCE
;
DIAMOND, JE
;
LIN, BMT
;
資訊工程學系
;
Department of Computer Science
The problem of minimizing the cost due to talent hold days in the production of a feature film is considered. A combinatorial model is developed for the sequencing of shooting days in a film shoot. The problem is shown to be strongly NP-hard. A branch-and-bound solution algorithm and a heuristic solution method for large instances of the problem (15 shooting days or more) are developed and implemented on a computer. A number of randomly generated problem instances are solved to study the power and speed of the algorithms. The computational results reveal that the heuristic solution method is effective and efficient in obtaining near-optimal solutions.