生產或製造系統中，機器佈置方式的優劣直接影響了系統的效能，其中，線性單排佈置因建構簡單且容易控制的特性，廣泛被應用在實務系統上。在本研究中，系統內每個工作站即為一個加工站，工件或產品由輸入站進入系統到某一工作站加工，一直到完成全部所需之加工步驟最後送到輸出站，離開系統，加工過程中，工件在不同加工站之移動皆由物料搬運機具運送，而不同的工件有不同的加工或需求量，且不同工作站之間的單位搬運成本亦可不同。本研究即在探討如何安排所有工作站到此一線性單排佈置環境，使得工件總流量搬運距離或成本最小。
當工作站所佔寬度為等距時，本研究針對上述單排佈置問題提出一個數學規劃模式，利用圖形理論將本佈置問題轉化為對等之網路切割問題，其中安排任一線性位置後所建構之子網路，稱為定址網路(locale network)，並發現其對等網路問題之目標函數即為總搬運成本，由三個部分組成，一為輸入站至各個新工作站之總單位距離搬運成本，第二部分則是各個新工作站到輸出站之單位距離搬運成本，此二者在單位距離搬運成本為已知的情況下可視為常數，第三則是所有相鄰佈置位置間(分段)之搬運成本的總合，而每個定址網路中的最小切割即為最小化每分段之搬運成本，依據此特性，發展網路切割解法(cut approach)，求解最小化總搬運成本之線性單排機器佈置問題。
當工作站所佔寬度不同，但其寬度可表示為最小工作站之整數倍時，本研究依據前述發現，延伸證明其線性單排機器佈置問題可轉化為對等之寬度等距之佈置問題並加以求解。針對上述兩個不同之線性單排機器佈置問題，使用本研究所發展出之網路切割法求解，在等距的情況下，其複雜度為Ο(n^3)，在不等距的情況下，複雜度則為Ο(n．(n')^2)，其中n為問題中之總工作站個數， n'則為不等距佈置問題拆解後之總工作站個數。

In this thesis, a cut approach is developed for the layout configuration problem of workstations in a single-row linear layout, where the distance between any two workstations can be identical or different. Raw material enters the bi-directional material handling system from input station, traverses to any workstations for processing, and finally departs from output station. The objective is to minimize the total material handling cost, where both forward and backtracking movements occur and the per-unit-distance material handling cost between workstations is different.
We show that the above equidistant linear layout problem is equivalent to the locale network problem by graph theory. Optimization of the linear layout problem is equivalent to minimize the sum of movement costs from input station to any workstation, two workstations in-between, and from any workstation to output station of each locale network. When the unit movement cost between any two workstations is known or fixed, the minimum cut, which has the minimum capacity in each locale network, is the corresponding optimal layout that minimizes the material handling cost. Based on these properties, a cut approach is developed to solve the linear layout problem.
The computational complexity of the cut approach to solve the equidistant linear layout problem is Ο(n^3), where n is the number of workstations in the layout problem. In addition, the non-equidistant linear layout problem can be transformed into an equidistant linear layout problem, and thus solved by the same cut approach. The computational complexity to solve the non-equidistant linear layout problem is Ο(n．(n')^2), where n' is the number of equivalent workstations in the transformed equidistant linear layout problem.

中文部分
王思穎，雙向直線單排班運環境佈置─考慮產能限制之多類型重複機組，國立成功大 學工業與資訊管理研究所碩士論文，民國九十二年六月。
英文部分
Adolphson, D., Hu, T. C., 1973. Optimal linear ordering, SIAM Journal on Applied Mathematics 25 (3), 403-423.
Anjos, M. F., Vannelli, A., 2008. Computing globally optimal solutions for single-row layout problems using semidefinite programming and cutting planes, INFORMS Journal on Computing 20 (4), 611-617.
Amaral, A. R. S., 2006. On the exact solution of a facility layout problem, European Journal of Operational Research 173, 508-518.
Amaral, A. R. S., 2009. A new lower bound for the single row facility layout problem, Discrete Applied Mathematics 157, 183-190.
Armour, G. C., Buffa, E. S., 1963. A heuristic algorithm and simulation approach to relative allocation of facilities, Management Science 9 (2), 294-300.
Azadivar, F., Wang, J., 2000. Facility layout optimization using simulation and genetic algorithms, International Journal of Production Research 38 (17), 4369-4383.
Balakrishnan, J. D., Cheng, C. H., Conway, D. G., and Lau, C. M., 2003. A hybrid genetic algorithm for the dynamic plant layout problem, International Journal of Production Economics 86 (2), 107-120.
Banerjee, P., Zhou, Y., 1995. Facilities layout design optimization with single loop material flow path configuration, International Journal of Production Research 33 (1), 183-203.
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.
Chiang, W. C., Kouvelis, P., 1996. An improved tabu search heuristic for solving facility layout design problems, International Journal of Production Research, 34 (9), 2565-2585.
Chung, J., Tanchoco, J. M. A., 2010. The double row layout problem, International Journal of Production Research 48 (3), 709-727.
Chwif, L., Pereira Barretto, M. R., and Moscato, L. A., 1998. A solution to the facility layout problem using simulated annealing, Computers in Industry 36(1-2), 125-132.
Corry, P., Kozan, E., 2004. Ant colony optimisation for machine layout problems, Computational Optimization and Applications 28 (3), 287-310.
Datta, D., Amaral, A. R. S., Figueira, J. R., 2011. Single row facility layout problem using a permutation-based genetic algorithm, European Journal of Operational Research 213, 388-394.
Drezner, Z., 1987. A heuristic procedure for the layout of a large number of facilities, Management Science 33 (7), 907-915.
Drira, A., Pierreval, H., and Hajri-Gabouj, S., 2007. Facility layout problems: a survey, Annual Reviews in Control 31, 255-267.
Garey, M. R., Johnson, D. S., 1979. Computers and intractability: A guide to the theory of NP-completeness, WH Freeman, San Francisco, New York.
Gilmore, P. C., 1962. Optimal and suboptimal algorithms for the quadratic assignment problem, Journal of the Society for Industrial and Applied Mathematics 10 (2), 305-313.
Hamann, T., Vernadat, F., 1992. The intra cell layout problem in automated manufacturing system, 8th International Conference on CAD, CAM, Robotics, and Factories of the Future, Metz, France.
Hassan, M. M. D., Hogg, G. L., and Smith, D. R., 1986. SHAPE: A construction algorithm for area placement evaluation, International Journal of Production Research 24 (5), 1283-1295.
Heragu, S. S., 1997. Facility design, PWS Publishing Company, Boston, MA.
Heragu, S. S., Kusiak, A., 1987. 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.
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.
Khalil, T. M., 1973. Facilities relative allocation technique (FRAT), International Journal of Production Research 11 (2), 183-194.
Koopmans, T. C., Beckman, M., 1957. Assignment problems and the location of economic activities, Econometrica 25, 53-76.
Kim, J. G., Kim, Y. D., 1999. A branch and bound algorithm for locating input and output points of departments on the block layout, European Journal of Operational Research 23, 382-390.
Kim, C. B., Kim, S. S., and Foote, B. L., 1996. Assignment problems in single-row and double-row machine layouts during slow and peak periods, Computers & Industrial Engineering 30 (3), 411-422.
Kouvelis, P., Kim, M. W., 1992. Unidirectional loop network layout problem in automated manufacturing systems, Operations Research 40 (3), 533-550.
Kouvelis, P., Chiang, W. C., 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., 1996. Optimal and heuristic procedures for row layout problems in automated manufacturing systems, The Journal of the Operational Research Society 47 (6), 803-816.
Kouvelis, P., Chiang, W. C., and Yu, G., 1995. Optimal algorithms for row layout problems in automated manufacturing systems, IIE Transactions 27, 99 - 104.
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.
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, Y. H., Lee, M. H., 2002. A shape-based block layout approach to facility layout problems using hybrid genetic algorithm, Computers & Industrial Engineering 42 (2-4), 237-248.
Lee, R. C., Moore, J. M., 1967. CORELAP-computerized relationship layout planning, Journal of Industrial Engineering 18 (3), 195-200.
Lewis, W. P., Block, T. E., 1980. On the application of computer aids to plant layout, International Journal of Production Research 18 (1),11-20.
Love, R. F., Wong, J. Y., 1976. Solving quadratic assignment problems with rectangular 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.
Mir, M., Imam, M. H., 2001. A hybrid optimization approach for layout design of unequal-area facilities, Computers & Industrial Engineering 39 (1–2), 49-63.
Palubeckis, G., 2012. A branch-and-bound algorithm for the single-row equidistant facility layout problem, OR Spectrum 34 (1), 1-21.
Picard, J.-C., Queyranne, M., 1981. On the one-dimensional space allocation problem, Operations Research 29 (2), 371-391.
Picard, J.-C., Ratliff, H. D., 1978. A cut approach to the rectilinear distance facility location problem, Operations Research 26 (3), 422-433.
Rosenblatt, M. J., 1986. The dynamics of plant layout, Management Science 32 (1), 76-86.
Sahni, S., Gonzalez, T., 1976. P-complete approximation problems, Journal of Associated Computing Machinery 23(3), 555-565.
Samarghandi, H., Taabayan,P., Jahantigh, F. F., 2010. A particle swarm optimization for the single row facility layout problem, Computers & Industrial Engineering 58, 529-534.
Sanjeevi, S., Kianfar, K., 2010. A polyhedral study of triplet formulation for single row facility layout problem, Discrete Applied Mathematics 158, 1861-1867.
Sarker, B. R., Yu, J., 1994. A two-phase procedure for duplicating bottleneck machines in a linear layout, cellular manufacturing system, International Journal of Production Research 32 (9), 2049-2066.
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 (1-4), 183-207.
Sarker, B. R., Wilhelm, W. E., Hogg, G. L., and Han, M. H., 1995. Backtracking of jobs in one-dimensional machine location problems, European Journal of Operational Research 85 (3), 593-609.
Seehof, J. M., Evans, W. O., 1967. Automated layout design program, Journal of Industrial Engineering 18, 690-695.
Simmons, D. M., 1969. One-dimensional space allocation: An ordering algorithm, Operations Research 17 (5), 812-826.
Solimanpur, M., Vrat, P., and Shankar, R., 2004. Ant colony optimization algorithm to the inter-cell layout problem in cellular manufacturing, European Journal of Operational Research 157 (3), 592-606.
Solimanpur, M., Vrat, P., and Shankar, R., 2005. An ant algorithm for the single row layout problem in flexible manufacturing systems, Computers & Operations Research 32 (3), 583-598.
Tam, K. Y., 1992. A simulated annealing algorithm for allocating space to manufacturing cells, International Journal of Production Research 30 (1), 63-87.
Tam, K. Y., Chan, S. K., 1998. Solving facility layout problems with geometric constraints using parallel genetic algorithms: Experimentation and findings, International Journal of Production Research 36 (12), 3253-3272.
Tompkins, J. A., Reed, R., 1976. An applied model for the facilities design problem, International Journal of Production Research 14 (5), 583-595.
Wang, M. J., Hu, M. H., and Ku, M. Y., 2005. A solution to the unequal area facilities layout problem by genetic algorithm, Computers in Industry 56 (2), 207-220.
Yu, J., Sarker, B. R., 2003. Directional decomposition heuristic for a linear machine-cell location problem, European Journal of Operational Research 149, 142-184.
Zhang, Z., Murray, C. C.,2012. A corrected formulation for the double row layout problem, International Journal of Production Research 50 (15), 4220-4223.