本論文針對零工廠排程問題提供一個新的近似演算法。零工廠排程問題的目標在最小化完成工時，本研究以工作在各機器台上的先後關係為決策變數，並以最小化該先後關係對完成工時所造成的最大影響為決策手段，發展出複雜度為O(n2)的啟發性演算法。以本演算法在電腦上計算經典的十件工作/十部機器零工廠排程問題，在不保證為最佳解的條件下，計算時間為八點二七二秒。最後，本研究試解一個一百件工作/三十部機器的大規模的零工廠排程問題作為未來相關研究的新指標問題。

We describe an approximation method for solving the minimum makespan problem of job shop scheduling. It makes use of the disjunctive graph, and set the direction of the disjunctive arcs as decision variables. The decision variables, as micro bottlenecks, are cleared one by one, following the critical path algorithm. Once a new disjunctive arc is adopted all the implicit disjunctive arcs will be decided. The time complexity is O (n2). Computational testing is performed to solve the notorious ten machines /ten jobs problem in running time of 8.272 CPU seconds on a P-II 450MHz PC, however, without finding an optimal solution. Finally, we verified the algorithm by testing a 100x30 (100 jobs/30machines) problem, which may contribute to be one of the new benchmark problems.

CONTENTS
1. INTRODUCTION ………………………………………...1
2. PAPER REVIEW …………………………………….……1
3. THE PROBLEM …………………………………….…….2
4. THE NEW APPROXIMATION METHOD ………….…...3
5. IMPLEMENTATION ……………………………………..7
6. COMPUTATION EXPERIENCE ………………………...9
7. CONCLUSION ………………………………………….11
REFERENCE ………………………………………………12
APPENDICES ………………………………………….......13

References
Adams J.,Balas E,and Zawack(1988) The Shifting Bottleneck Procedure for Job Shop Scheduling Management Science Vol.34,No.3 391-401
Applegate D. and Cook W.(1991)A Computational Study of Job-Shop Scheduling Problem ORSA Journal on Computing Vol.3,No.2 149-156
Balas E.(1969) Machine sequencing via disjunctive graphs: an implicit enumeration algorithm Oper.Res.,17,941-957
Carlier J, and Pinson E.(1989) An Algorithm for Solving the Job-Shop Problem, Management Science 35,164-176
French S.(1982) Sequencing and Scheduling: An introduction to the Mathematics of Job Shop Wiley, Chichester
Garey M.R. and Johnson D.S.(1979) Computers and Intractability: A Guide to the Theory of NP-Completeness Freeman, San Francisco.
Jain A.S. and Meeran S.(1999) Deterministic Job-Shop Scheduling: Past Present and Future, European Journal of Operation Research Vol.113, Issue2,390-434
Lenstra J.K.,Rinnooy Kan A.H.G. and Brucker P.(1977)Complexity of machine scheduling problem Ann.Discr.Math., 1,343-362
Muth, J.F., and G.L.Thompson, Industrial Scheduling, Prentice-Hall,Englewood Cliffs,N.J.,1963
Pinedo M. , Scheduling-Theory, Algorithms, and Systems, Prentice Hall
Pinedo M. and Chao X.,Operation Scheduling with Applications in Manufacturing and Service, McGraw-Hill.
Pinson E.(1995)The Job Shop Scheduling Problem: A Concise Survey and Some Recent Development, Scheduling Theory and its Applications, John Wiley&Sons Ltd
Potts C.N.(1980)An Algorithm for the Single Machine Sequencing Problem with Precedence Constraints, Mathematical Programming Study 13,78-87, North-Holland Publishing Company
Roy B. and Sussman B.(1964) Les problémes d’ordonnancement avec constraints disjunctives. Note DS no 9 bis, SEMA, Paris