在製造系統上，工作站或機器以迴圈佈置方式進行之設施佈置
設計，因為具有高效率及低成本的優點，應用十分廣泛。在本研
究中，搬運機具沿著迴圈以單一方向繞行，將工件由輸入站搬運
，依加工順序將工件送至某一機器以進行加工，待完成所有加工
程序後再搬運至輸出站。系統中同時考慮單一與重複機台機器類
型，後者指某一機器類型包含多台相同機器，且各台機器有其產
能限制。本論文同時決定機器佈置位置及重複機台機器間工件運
送量分配，為一高度複雜的非線性整數最佳化問題。
本研究探討如何將此系統中所有的機器安排在一單向單迴圈的
佈置環境中，同時決定工件運送至機器之分配量，且維持機器加
工量不超過其產能上限，即必須決定機器間工件運送量之分配，
本研究針對此問題建構數學規劃模式，以工件總運送量搬運距離
成本最小化為目標，進而以理論證明目標函數可簡化為單位時間
內工件通過輸入/輸出站之總次數。
依據本佈置問題之特殊結構，本研究發現此單向單迴圈重複機
台佈置問題之特殊性質與機器佈置、工件分配之相關最佳性質，
並依據上述發現發展一啓發式演算法來決定佈置順序；首先，依
工件運送量矩陣建立一組起始佈置位置，再根據通過輸入/輸出
站之工件運送量最小化的原則分配工件及調整運送量矩陣，以決
定近似最佳或最佳之機器佈置位置與工件運送量。為比較本演算
法之求解品質與效率，進行演算實驗，針對機器總數小於等於10
台之小規模問題，發現以軟體求解之最佳解與啓發式求解之近似
最佳解的目標值差異，平均誤差小於百分之十，但啓發式之演算
效率遠較求解最佳解之演算效率為佳，其差距十分顯著；針對機
器總數大於10台之大規模問題，啓發式解與近似上界值之差異隨
重複機器數目增加而增加；整體而言，本演算法在求解品質與效
率上表現良好。

The layout configuration problem of workstations
with unique and identical machines in a unidirectional
unicyclic network is considered in this thesis. In
this unicyclic material handling system, the material
transporters carry the workpieces and depart from the
Input/Output station, traverse each workstation exactly
once by moving unidirectionally clockwise or
counterclockwise, and than return to the Input/Output
station. The workstations include two types of machines:
the single or unique machine where only one machine is
available, and the duplicate machine where more than one
identical machines are present in the system. The
capacity of each machine is assumed identical for each
of the duplicated machine type.
A mathematical programming model is formulated for
this layout problem. Both the location of each machine
at the unicyclic layout and the assignment of part to
each machine are determined. The minimization of material
handling cost is shown to be equivalent to the
minimization of the number of parts that have to pass
through the Input/Output station. Several new properties
of this difficult layout problem are established.
Due to the computational complexity of the layout
problem, a four-stage heuristic is developed to find
the location of machines and the assignment of parts
to each machine. It consists of layout construction,
allocation of parts to each machine, location refinement,
and local improvement. Computational experiments with
problem size up to 30 machines are tested, with a variety
of part and machine types. It appears that the solution
procedure is both efficient and effective for solving
the unidirectional unicyclic network problems.

中文文獻：
王思穎，雙向直線單排搬運環境佈置—考慮產能限制
之多類型重複機組，國立成功大學工業管理研究所碩士論文，
民國九十二年六月。

英文文獻：
Afentakis, P., 1989, A loop layout design problem
for flexible manufacturing systems. International Journal
of flexible Manufacturing systems, 1, 175-196.
Altinel, İ.K., and Öncan, T., 2005, Design of
unidirectional cyclic layouts. International Journal of
Production Research, 43(19), 3983-4008.
Aneke, N.A.G., and Carrie, A.S., 1986, A design
technique for the layout of multi-product flowlines.
International Journal of Production Research, 24(3), 471-481.
Armour, G.C., and Buffa, E.S., 1963, A heuristic
algorithm and simulation approach to relative location of
facilities. Management Science, 9(2), 294-309.
Bazaraa, M.S., 1975, Computerized layout design:
A branch and bound approach. AIIE Transactions, 7(4), 432-437.
Bazaraa, M.S., and Kirca, O., 1983, A
branch-and-bound-based heuristic for solving the QAP.
Naval Research Logistics Quarterly, 30, 287-304.
Bazaraa, M.S., and Sherali, M.D., 1980, On the
use of exact and heuristic cutting plane methods for the
quadratic assignment problem. Journal of Operations
Research Society, 33(1), 991-1003.
Burkard, R.E., and Bonninger, T., 1983, A heuristic
for quadratic Boolen program with application to quadratic
assignment problems. European Journal of Operational Research,
13, 374-386.
Burkard, R.E., and Stratman, K.H., 1978, Numerical
investigations on quadratic assignment problems. Naval
Research Logistic Quarterly, 25, 129-144.
Carrie, A.S., 1975, The layout of multi-product lines.
International Journal of Production Research, 13(6), 541-557.
Chanas, S., and Kobylanski, P., 1996, A new heuristic
algorithm for solving the linear ordering problem.
Computational Optimization and its Applications, 6, 191-205.
Cheng, R., and Gen, M., 1998, Loop layout design
problem in flexible manufacturing systems using genetic
algorithms. Computers and Industrial Engineering, 34(1),
53-61.
Diponegoro, A., and Sarker, B.R., 2003, Flow
distance reduction for a multi-product flowline with sets
of identical machines. European Journal of Operational
Research, 147, 591-612.
Foulds, L.R., Gibbons, P.B., and Giffin, J.W., 1985,
Facilities layout adjacency determination: An experimental
comparison of three graph theoretic heuristics. Operations
Research, 33(5), 1091-1106.
Foulds, L.R., and Robinson, D.F., 1976, A strategy
for solving the plant layout problem. Operations Research
Quarterly, 27(4), 845-855.
Gilmore, P.C., 1962, Optimal and suboptimal algorithm
for the quadratic assignment problem. Journal of the Society
for Industrial and Applied Mathematics, 10, 305-311.
Goetschalckx, M., 1992, An interactive layout
heuristic based on hexagonal adjacency graphs. European
Journal of Operational Research, 63, 304-321.
Hassan, M.M.D., and Hogg, G.L., 1987, A review of
graph theory application to the facilities layout problem.
Omega, 15(4), 291-300.
Heragu, S.S., and Kusiak, A., 1988, Machine layout
problem in flexible manufacturing systems. Operations
Research, 36(2), 258-268.
Ho, Y.C., and Moodie, C.L., 1998, Machine layout
with a linear single-row flow path in an automated
manufacturing system. Journal of Manufacturing systems,
17(1), 1-22.
Hollier, R.H., 1963, The layout of multi-product
lines. International Journal of Production Research, 2(1),
47-57.
Houhyar, A., and McGinnis, L.G., 1990, A heuristic
for assignment facilities to locations to minimize WIP
travel distance in a linear facility. International Journal
of Production Research, 28(8), 1485-1498.
Kaku, B.K., and Thompson, G.L., 1986, An exact
algorithm for the general quadratic assignment problem.
European Journal of Operational Research, 23, 382-390.
Kaufman, L., and Broeckx, F., 1978, An algorithm
for the quadratic problem using Benders’ decomposition.
European Journal of Operational Research, 2, 204-211.
Kiran, A.S., Unal, A.T., and Karabati, S., 1992,
A location problem on unicyclic networks: Balanced case.
European Journal of Operational Research, 62, 194-202.
Koopmans, T.C., and Beckman, M., 1957, Assignment
problem and the location of economic activities. Econometrica,
25, 53-76.
Kouvelis, P., Chiang, W.C., and Yu, G., 1995,
Optimal algorithms for row layout problems in automated
manufacturing systems. IIE Transactions, 27, 99-104.
Kouvelis, P., and Kim, M.W., 1992, Unidirectional
loop network layout problem in automated manufacturing
systems. Operations Research, 40(3), 533-550.
Kumar, K.R., Hadjinicola, G.C., and Lin, T.L.,
1995, A heuristic procedure for the single-row facility
layout problem. European Journal of Operational Research,
87(1), 65-73.
Kusiak, A., and Heragu, S.S., 1987, The facility
layout problem. European Journal of Operational Research,
29, 229-251.
Lawler, E.L., 1963, The quadratic assignment
problem. Management Science, 9, 586-599.
Lee, S.D., Huang, K.H., and Chiang, C.P., 2001,
Configuring layout in unidirectional loop manufacturing
systems. International Journal of Production Research,
39(6), 1183-1201.
Lee, R., and Moore, J.M., 1967, CORELAP-computerized
relationship layout planning. Journal of Industrial
Engineering, 18, 195-200.
Leung, J., 1992, A graph-theoretic heuristic for
designing loop-layout manufacturing systems. European
Journal of Operational Research, 57(2), 243-252.
Love, R.F., and Wong, J.W., 1976, Solving quadratic
assignment problem with rectilinear distances and integer
programming. Naval Research Logistics Quarterly, 23, 623-627.
Nearchou, A.C., 2006, Meta-heuristics from nature
for the loop layout design problem. International Journal
of Production Economics, 101, 312-328.
Potts, C.N., and Whitehead, J.D., 2001, Workload
balancing and loop layout in the design of a flexible
manufacturing system. European Journal of Operational
Research, 129(2), 326-336.
Sahni, S., and Gonzalez, T., 1976, P-complete
approximation problem. Journal of Associated Computing
Machinery, 23(3), 555-565.
Sarker, B.R., Wilhelm, W.E., and Hogg, G.L.,
1998, Locating sets of identical machines in a linear
layout. Annals of Operations Research, 77, 183-207.
Tam, K.Y., 1992, A simulated annealing algorithm
for allocation space to manufacturing cells. International
Journal of Production Research, 30, 63-87.
Tansel, B.C., and Bilen, C., 1998, Move based
heuristics for the unidirectional loop network layout
problem. European Journal of Operational Research, 108,
36-48.