1.
Ching-Fang Liaw
and Chelsea C. White, III., “A
heuristic search approach for solving a minimum path problem requiring arc cost
determination”, IEEE Transactions on
Systems, Man, and Cybernetics, Vol. 26, No. 5, p. 545-551, 1996.
-
present and analyze two generalization of algorithm A*, breadth-first A*
(BA*) and depth-first A* (DA*). Both
consider the problem of finding a minimum cost path from the start node to a
finite goal node set in an OR-graph, assuming that estimates of the optimal
costs from each node to the goal node set are given, estimates of all arc costs
are given, but the actual arc costs require determination.
DA* tends to determine a solution (not necessarily optimal) more rapidly
than BA*. Improved heuristics and
arc cost estimates tend to reduce node expansions and arc cost determination
steps for BA*, however, these results do not necessarily hold for DA*.
2.
Ching-Fang Liaw,
Bradley S. Stewart, and Chelsea C. White, III.,
“Multiobjective heuristic search in AND/OR graphs”, IEEE
Transactions on Systems, Man, and Cybernetics, Vol. 25, No. 11, p.
1513-1521, 1995.
-
develop and analyze a heuristic search algorithm that determines the
nondominated set of solution graphs for a multiobjective AND/OR graph. This algorithm, MOAO*, is a multiobjective generalization of
AO*. MOAO* uses sets of
vector-valued heuristic estimates to give guidance to the search. We show that MOAO* satisfies termination, completeness, and
admissibility conditions, generalizing results associated with AO*.
3.
Ching-Fang Liaw,
James Banders, and Chelsea C. White, III.,
“A decision support system for the bimodal dial-a-ride problem”, IEEE Transactions on Systems, Man, and Cybernetics, Vol. 26, No. 5,
pp 552-565, 1996.
-
design a decision support system (DSS) which automatically constructs
efficient paratransit vehicle routes and schedules for the bimodal dial-a-ride
problem. This DSS has been tested
using actual data from the Ann Arbor Transportation Authority in Ann Arbor,
Michigan. The results show that
this DSS produces an average increase of 10% in the number of requests that can
be accommodated and an average decrease of 10% in the number of paratransit
vehicles required, as compared to the manual results.
4.
Ching-Fang Liaw, “A Tabu search algorithm for the open shop scheduling
problem”, Computers and Operations
Research, Vol. 26, No. 2, p. 109-126, 1999
- present a local search algorithm based on the tabu search technique for the nonpreemptive open shop scheduling problem. Computational studies show that the algorithm finds extremely high quality solutions for both randomly generated problems and hard benchmarks.
5.
Ching-Fang Liaw, “An iterative improvement approach for the nonpreemptive
open shop scheduling problem”, European
Journal of Operational Research, Vol. 111, No. 3, p. 89-97, 1998.
-
present an efficient iterative improvement approach based on Benders‘
decomposition for the nonpreemptive open shop scheduling problem.
Computational experiment shows that most solutions found are within 1% of
lower bounds and hence demonstrate the potential of the approach to efficiently
schedule open shops of realistic size.
6.
Ching-Fang
Liaw,
“A branch-and-bound algorithm for the single machine earliness and
tardiness scheduling problem”, Computers and Operations Research, Vol. 26, p. 679-693, 1999.
- present a branch-and-bound algorithm incorporating lower and upper bounds and some dominance rules for solving the single machine earliness and tardiness scheduling problem. The lower bound is obtained based on a Lagrangian relaxation along with an efficient multiplier adjustment method. The upper bound is obtained using a two-phase procedure combining a priority dispatching rule with a local improvement procedure. Computational experiments show that the algorithm performs extremely well.
7.
Ching-Fang
Liaw,
“Applying simulated annealing to the open shop scheduling problem”, IIE
Transactions, Scheduling and Logistics, Vol. 31, No. 5, p. 457-465, 1999.
- present a local search algorithm based on the simulated annealing technique for the open shop scheduling problem. Computational results show that the maximum deviation from the lower bound is 1.19% and 1.71% for randomly generated problems and hard benchmarks, respectively.
8.
Ching-Fang
Liaw,
“A hybrid genetic algorithm for the open shop scheduling problem”, European
Journal of Operational Research, Vol. 124, p. 28-42, 1999.
- develop a hybrid genetic algorithm that incorporates a local improvement procedure based on tabu search into a genetic algorithm for solving the open shop scheduling problem. The incorporation of the local improvement procedure enables the algorithm to perform genetic search over the subspace of local optima. Computational results show that the algorithm is able to find an optimum solution for all but a tiny fraction of the test problems. Moreover, the algorithm significantly outperforms other existing methods in terms of solution quality.
9.
Ching-Fang
Liaw,
Chun-Yuan Cheng and Mingchih Chen , “The total completion time open shop
scheduling problem with a given sequence of jobs on one machine”, Computers and Operations Research (in press), 2000.
- address the total completion time open shop scheduling problem with a given sequence of jobs on one machine. This model belongs to a new class of shop scheduling problems under machine-dependent precedence constraints. A lower bound is derived based on the optimal solution of a relaxed problem in which the operations on every machine may overlap except for the machine with a given sequence of jobs. Both heuristic and branch-and-bound algorithms are proposed. Experimental results show that the heuristic is efficient for solving large-scaled problems, and the branch-and-bound algorithm performs well on small-scaled problems.
10.
廖經芳、林安祥，「開放工廠總加權延遲最小化排程問題之研究」，中國工業工程學刊（刊印中），2001.
-
本研究首先針對開放工廠總加權延遲最小化排程問題發展一啟發式解法，以迅速產生一完整的起始解，而後經由逐步搜尋的策略來改善起始解的品質。根據測試結果，本研究所發展之啟發式演算法，所得績效明顯優於文獻上現有之啟發式演算法；而經由逐步搜尋策略的改善後，更能進一步提昇其求解品質。最後，本研究亦發展一以分枝界限法為基礎之最佳解法，以求解小規模之問題，並填補開放工廠總加權延遲最小化排程問題在理論發展上之空缺。
11.
Ching-Fang
Liaw,
Yang-Kuei Lin, Chun-Yuan Cheng and Mingchih Chen , “Scheduling Unrelated
Parallel Machines to Minimize Total Weighted Tardiness”,
Computers and Operations Research (in review), 2001.
- consider the problem of scheduling a given set of independent jobs on unrelated parallel machines to minimize total weighted tardiness. Efficient lower and upper bounds are developed. The lower bound is based on the solution of an assignment problem, while the upper bound is obtained by a two-phase heuristic. A branch-and-bound algorithm that incorporates various dominance rules is presented. Computational experiments are conducted to demonstrate the performance of the proposed algorithms