製造系統中機器的佈置方式直接影響到系統的效能，其中，直線單排佈置由於建構與控制容易的優點，廣泛被應用在機器佈置問題上。在本研究中，系統內包含多種類型的機器群組，當群組中有多台功能相同的機器時，稱之為重複機器，物料搬運設備以直線雙向進行工件運送，搬運系統依加工順序將工件由輸入站送至某一機器工作站，完成所有加工程序後再由輸出站送離此系統。本研究即在探討如何將系統中所有機器安排在一雙向直線單排的佈置環境，並同時進行機器間工件流量之分配，使得工件的總流量搬運距離成本最小。
本研究針對上述問題建構出一數學模式，同時考慮機器位置與機器間分配流量兩項決策變數，為一高難度的非線性最佳化問題。當同型機器數量唯一、且忽略輸入/輸出站到各機器工作站間的流量時，本模式可簡化成最原始的單排機器佈置問題。研究中發現直線單排佈置具有最小化總流量搬運距離成本與最小化總折返流量搬運距離成本之最佳方案相同的特性，根據此特性，在最小化總流量搬運距離成本下，發展出一啟發式演算法，以啟發式流量分配與網路分割法(cut approach)建立一組佈置方案，再以兩兩成對交換工件分配順序的方式進行起始解之改善，進而得到單排佈置及機器流量分配之近似最佳解。最後依機器總數大小分類，進行演算實驗比較，演算結果發現，當機器總數小於、等於十台，本演算法之演算時間隨工件數與總群組數增加略為增加，但在求解的品質上遠優於現有軟體的表現；當機器總數大於十台，演算法之成本與近似下界值之差異隨機器總數增加而增加，而與工件數和總群組數呈反向關係，不論問題大小，本演算法在求解上均十分有效率，平均較現有軟體快約數百倍以上。

Adolphson, D., Hu, T.C., 1973. Optimal linear ordering, SIAM Journal on Applied Mathematics 25 (3), 403-423.
Aneke, N.A.G., 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., 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., Kirca, O., 1983. A branch-and-bound-based heuristic for solving the QAP, Naval Research Logistics Quarterly 30, 287-304.
Bazaraa, M.S., 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.
Bozer, Y.A., Meller,R.D., and Erlebacher, S.J., 1994. An improvement-type layout algorithm for single and multiple-floor facilities, Management Science 40 (7), 918-932.
Braglia, M., 1996. Optimisation of a simulated-annealing-based heuristic for single row machine layout problem by Genetic Algorithm, International Transactions in Operational Research 3 (1), 37-49.
Burkard, R.E., 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., 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.
Deisenroth, M.P., Apple, J.M., 1972. A computerized plant layout analysis and evaluation technique, technical paper, Annual AIIE Conference, Norcross, GA.
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., 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., 1994. Machine layout problem in modern manufacturing facilities, International Journal of Production Research 32 (11), 2559-2584.
Hassan, M.M.D., Hogg, G.L., 1987. A review of graph theory application to the facilities layout problem, Omega 15 (4), 291-300.
Hassan, M.M.D., Hogg, G.L., 1989. On converting a dual graph into a block layout, International Journal of Production Research 27 (7), 1149-1160.
Heragu, S.S., Kusiak, A., 1988. Machine layout problem in flexible manufacturing systems, Operations Research 36 (2), 258-268.
Heragu, S.S., Kusiak, A., 1990. Machine layout: an optimization and knowledge-based approach, International Journal of Production Research 28 (4), 615- 635.
Heragu, S.S., Kusiak, A., 1991. Efficient models for the facility layout problem, European Journal of Operational Research 53 (1), 1-13.
Hicks, P.E., Cowan, T.E., 1976. CRAFT-M for layout rearrangement, Industrial Engineering, May, 30-35.
Ho, Y.C., 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.
Houshyar, A., McGinnis, L.F., 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., Thompson, G.L., 1986. An exact algorithm for the general quadratic assignment problem, European Journal of Operational Research 23, 382-390.
Karp, R.M., Held, M., 1967. Finite state processes and dynamic programming, SIAM Journal on Applied Mathematics 15 (3), 693-718.
Kaufman, L., Broeckx, F., 1978. An algorithm for the quadratic problem using Benders’ decomposition, European Journal of Operational Research 2, 204-211.
Koopmans, T.C., Beckman, M., 1957. Assignment problem and the location of economic activities, Econometrica 25, 53-76.
Kouvelis, P., Chiang, W., 1992. A simulated annealing procedure for single row layout problems in flexible manufacturing systems, International Journal of Production Research 30 (4), 717-732.
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., 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., 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, 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., Wong, J.W., 1976. Solving quadratic assignment problem with rectilinear distances and integer programming, Naval Research Logistics Quarterly 23, 623-627.
Luggen, W.W., 1991. Flexible manufacturing cells and systems, Prentice-Hall, Englewood Cliffs, NJ.
Meller, R.D., Bozer, Y.A., 1996. A simulated annealing algorithm for the facility layout problem, International Journal of Production Research 34, 1675-1692.

Meller, R.D., Gau, K.Y., 1996. The facility layout problem: Recent and emerging trends and perspectives, Journal of Manufacturing Systems 15 (5), 351-365.
Picard, J., Queyranne, M., 1981. On the one-dimensional space allocation problem, Operations Research 29 (2), 371-391.
Ponnambalam, S.G., Ramkumar, V., 2001. A Genetic Algorithm for the design of a single-row layout in automated manufacturing systems, International Journal of Advanced Manufacturing Technology.
Sahni, S., Gonzalez, T., 1976. P-complete approximation problem, Journal of Associated Computing Machinery 23(3), 555-565.
Sarker, B.R., Han, M.H., Hogg, G.L., and Wilhelm, W.E., 1991. Backtracking of jobs and machine location problems. In: White, J.A. and Pence, I.W. (Eds.), Progress in Material Handling and Logistics: Material Handling, Springer-Verlag, pp.117-141.
Sarker, B.R., Wilhelm, W.E., and Han, M.H., 1995. Backtracking of jobs in one-dimensional machine location problems, European Journal of Operational Research 85 (3), 593-609.
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.
Simmons, D.M., 1969. One-dimensional space allocation: An ordering algorithm, Operations Research 17 (5), 812-826.
Simmons, D.M., 1971. A further note on one-dimensional space allocation, Operations Research 19 (1), 249.
Sirinaovakul, B., Thajchayapong, P., 1994. A knowledge base to assist a heuristic search approach to facility layout, International Journal of Production Research 1 (32), 141-160.
Tam, K.Y., 1992. A simulated annealing algorithm for allocating space to manufacturing cells, International Journal of Production Research 30, 63-87.