Browsing by Author "Fang, Kuei-Tang"

Now showing 1 - 3 of 3

A branch-and-bound algorithm for makespan minimization in differentiation flow shops
(2013-12-01)
Liu, Yen-Cheng
;
Fang, Kuei-Tang
;
Lin, Bertrand
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This article considers a differentiation flow-shop model, where the jobs are divided into various categories, each of which consists of two stages of operations. All products should be processed first on the single common machine at stage 1. At the second stage, each individual product proceeds to a dedicated machine according to its type. The problem of makespan minimization under the setting with two product types is known to be strongly NP hard. This article considers an arbitrary number of job types by developing a lower bound and two dominance rules, based upon which branch-and-bound algorithms are designed. Computational experiments are carried out to examine the performance of the proposed properties. The statistics show that the proposed properties can substantially reduce the computing efforts required for finding optimal solutions.
Parallel-machine scheduling to minimize tardiness penalty and power cost
(2013-01-01)
Fang, Kuei-Tang
;
Lin, Bertrand M. T.
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
Traditional research on machine scheduling focuses on job allocation and sequencing to optimize certain objective functions that are defined in terms of job completion times. With regard to environmental concerns, energy consumption becomes another critical issue in high-performance systems. This paper addresses a scheduling problem in a multiple-machine system where the computing speeds of the machines are allowed to be adjusted during the course of execution. The CPU adjustment capability enables the flexibility for minimizing electricity cost from the energy saving aspect by sacrificing job completion times. The decision of the studied problem is to dispatch the jobs to the machines as well as to determine the job sequence and processing speed of each machine with the objective function comprising of the total weighted job tardiness and the power cost. We give a formal formulation, propose two heuristic algorithms, and develop a particle swarm optimization (PSO) algorithm to effectively tackle the problem. Since the existing solution representations do not befittingly encode the decisions involved in the studied problem into the PSO algorithm, we design a tailored encoding scheme which can embed all decisional information in a particle. A computational study is conducted to investigate the performances of the proposed heuristics and the PSO algorithm. (C) 2012 Elsevier Ltd. All rights reserved.
Single-machine scheduling with supporting tasks
(2015-08-01)
Kononov, Alexander V.
;
Lin, Bertrand M. T.
;
Fang, Kuei-Tang
;
資訊管理與財務金融系註：原資管所+財金所
;
Department of Information Management and Finance
This paper investigates a single-machine scheduling problem with a set of supporting tasks and a set of jobs. Each job is preceded by a subset of supporting tasks, that is, the job cannot start its processing until all of its supporting tasks are finished. The objective functions are defined solely in job completion times. We discuss the complexities of several special cases for the number of late jobs and the total weighted completion time. This study adds new complexity results to the two standard objective functions under precedence constraints. (C) 2015 Elsevier B.V. All rights reserved.