臺灣博碩士論文加值系統

空間排程問題對於高科技設備製造商的工作效率來說是一個重要的議題，現存解決空間排程問題的方法總是會造成訂單延遲或過早被完成，這為製造商帶來巨大的財務上的懲罰。
本研究針對此問題發展出ㄧ新的空間配置演算法，命名為「擬似三維空間配置演算法」，並與西北演算法和最大接觸法，運用不同的派工法則，比較各項績效指標的表現。本研究目的為對空間排程問題，找到一個排程計畫來減少總懲罰(提早與延遲懲罰)。
根據隨機集區實驗與因子實驗結果分析，本研究證明擬似三維概念空間配置法相較於以前的空間配置演算法可更有效降低提早與延遲訂單的懲罰成本。它在其它一些績效指標也比其他演算法有更好的表現 (提早訂單數、提早總天數)，且它在其餘績效指標的表現也不輸給其他演算法(製距、延遲工作數、總延遲天數、空間利用率)。雖然此演算法並沒有在所有的績效指標都有突出的表現，但它對於整個問題有更完整的思考性。在研究最後，針對不同績效指標建議採用的派工法則和空間配置演算法也在實驗中被獲得。

A space scheduling problem is an important issue of work efficiency for high-tech equipment manufacturers. The existing approaches to solve a space scheduling problem always cause orders (jobs) to be completed too late or too early. It brings huge financial penalties to manufacturers.
In this study, the purpose of this research is to find a schedule to r total penalties (early and tardy penalties) for a space scheduling problem. A new space allocation algorithm, namely, Quasi-Three-Dimensional Space Allocation Algorithm (QTDSA) was developed. We compared its performance for different performance indicators with those of the Northwest Algorithm (NWA) and Longest Contact Edge Algorithm (LCEA) by different dispatching rules.
In addition, randomized block designs and factorial designs were employed for statistical analysis. The results demonstrated that the QTDSA is more effective than the other space allocation algorithms in reducing total penalties. It also has better performances for some other performance indicators (i.e. number of early jobs and total earliness) than the other algorithms. The performance of the QTDSA and the other algorithms are about the same for the other performance indicators (makespan, number of tardy jobs, total tardiness and space utilization). In the final part of the research, suggested dispatching rules and suggested space allocation algorithms for each performance indicator were also provided.

ABSTRACT I
摘要 II
致謝 III
CONTENTS IV
LIST OF TABLES VI
LIST OF FIGURES XI
CHAPTER 1 INTRODUCTION 1
1.1 BACKGROUND 1
1.2 MOTIVATION FOR THE RESEARCH 1
1.3 OBJECTIVES OF THE RESEARCH 3
1.4 ORGANIZATION OF THIS THESIS 3
CHAPTER 2 LITERATURE REVIEW 4
2.1 SCHEDULING PROBLEMS 4
2.2 SPACE ALLOCATION PROBLEMS 5
2.3 EARLY AND TARDY PENALTIES 9
2.4 SPACE SCHEDULING PROBLEMS 10
CHAPTER 3 RESEARCH METHODOLOGY 12
3.1 PROBLEM ASSUMPTIONS AND NOTATIONS 12
3.2 QUASI-THREE-DIMENSIONAL SPACE ALLOCATION ALGORITHM 15
3.2.1 Introduction 15
3.2.2 Overview of quasi-three-dimensional space allocation algorithm 16
3.2.3 The Quasi-Three-Dimensional Space Allocation Algorithm 23
CHAPTER 4 DESIGN OF EXPERIMENT 35
4.1 EXPERIMENTAL DATA 35
4.2 THE FIRST DESIGN OF EXPERIMENT 38
4.3 THE SECOND DESIGN OF EXPERIMENT 40
CHAPTER 5 RESULTS AND DISCUSSION 43
5.1 RESULTS OF THE FIRST EXPERIMENT 43
5.2 RESULTS OF THE SECOND EXPERIMENT 52
5.3 SUMMARY 63
CHAPTER 6 CONCLUSION AND SUGGESTION 66
6.1 CONCLUSION 66
6.2 SUGGESTIONS 67
REFERENCES 68
APPENDIX 72
A. THE OTHER ANALYSES OF THE FIRST EXPERIMENT 72
A.1 The Analysis for Makespan 72
A.2 The Analysis for Space Utilization 76
A.3 The Analysis for Total Tardiness 80
A.4 The Analysis for Total Earliness 84
A.5 The Analysis for Tardy Jobs 88
A.6 The Analysis for Early Jobs 93

[1]Ahmed, M. U., and P. S. Sundararaghavan. (1990). Minimizing the weighted sum of late and early completion penalties in a single machine. IIE Transactions, 22(3), 288-290.
[2]Axelrod, C. W. (1976). The effective use of computer resources. Omega, 4(3), 321-330.
[3]Balakrishnan, J., C. H. Cheng, D. G. Conway and C. M. Lau. (2003). A hybrid genetic algorithm for the dynamic plant layout problem. International Journal of Production Economics, 86(2), 107-120.
[4]Barbosa-Povoa, A. P., R. Mateus and A. Q. Novais (2001). Optimal 2D Layout Design of Industrial Facilities. International Journal of Production Research, 39(12), 2567-2593.
[5]Barbosa-Povoa, A. P., R. Mateus and A. Q. Novais. (2002). Optimal 3D layout of industrial facilities. International Journal of Production Research, 40(7), 1669-1698.
[6]Beasley, J. E. (1990). OR-Library: distributing test problems by electronic mail. Journal of Operational Research Society, 41(11), 1069-1072.
[7]Beasley, J. E. (2008). OR-Library. from http://people.brunel.ac.uk/~mastjjb/jeb/info.htm
[8]Bischoff, E. E. (2006). Three-dimensional packing of items with limited load bearing strength. European Journal of Operational Research, 168(3), 952-966.
[9]Bortfeldt, A., H. Gehring and D. Mack. (2003). A parallel tabu search algorithm for solving the container loading problem. Parallel Computing, 29(5), 641-662.
[10]Chretienne, P., E. G. Coffman, J. K. Lenstra and Z. Liu. (1995). Scheduling theory and its application: John Wiley and Sons press.
[11]Dantzig, G. B. (1957). Discrete-variable extremum problems. Operations Research, 5(2), 266-277.
[12]Dunker, T., G. Radons and E. Westkamper. (2005). Combining evolutionary computation and dynamic programming for solving a dynamic facility layout problem. European Journal of Operational Research, 165(1), 55-69.
[13]Eley, M. (2002). Solving container loading problems by block arragement. European Journal of Operational Research, 141(2), 393-409.
[14]Erel, E., J. B. Ghosh and J. T. Simon. (2003). New heuristic for the dynamic layout problem. Journal of the Operational Research Society, 54(12), 1275-1282.
[15]Gehring, H., and A. Bortfeldt. (1997). A genetic algorithm for solving the container loading problem. International Transactions in Operational Research, 4, 401-418.
[16]Gilmore, P. C., and R. E. Gomory. (1965). Multistage cutting stock problems of two and more dimentions. Operations Research, 13, 94-120.
[17]Hardin, J. R., G. L. Nemhauser and M. W. P. Savelsberghb. (2008). Strong valid inequalities for the resource-constrained scheduling problem with uniform resource requirements. Discrete Optimization, 5(1), 19-35.
[18]Haynes, R. D., C. A. Komar and J. J. Byrd. (1973). Effectiveness of three heuristic rules for job sequencing in a single production facility. Management Science, 19(5), 575-580.
[19]Holthaus, O., C. Rajendran (1997). Efficient dispatching rules for scheduling in a job shop. International Journal of Production Economics, 48(1), 87-105.
[20]Ikonen, I. T., W. E. Biles, A. Kumar, R. K. Ragade and J. C. Wissel. (1997). A genetic algorithm for packing three-dimensional non-convex objects having cavities and holes. Paper presented at the Proceedings of the 7th International Conference on Genetic Algortithms, Michigan State University, East Lansing, MI., United States of America.
[21]Johnson, D. S. (1973). Approximation algorithms for combinatorial problems. Proceedings of the fifth annual ACM symposium on theory of computing-Austin-Texas-United States of America, 38-49.
[22]Johnson, D. S. (1974). Fast algorithms for bin packing. Journal of Computer Systems Science, 8, 272-314.
[23]Kovacs, A., and J. C. Beck. (2008). A global constraint for total weighted completion time for cumulative resources. Engineering Applications of Artifical Intelligence, 21(5), 691-697.
[24]Lauff, V., and F. Werner. (2004). On the complexity and some properties of multi-stage scheduling problems with earliness and tardiness penalties Computers & Operations Research, 31(3), 317-345.
[25]Lee, Y., and N. Y. Hsu. (2007). An optimization model for the container pre-marshalling problem. Computers and Operations Research, 34(11), 3295-3313.
[26]Lewis, J. E., R. K. Ragade, A. Kumar and W. E. Biles. (2005). A distributed chromosome genetic algorithm for bin-packing. Robotics and Computer-Integrated Manufacturing, 21(4-5), 486-495.
[27]Liaw, C. F. (1999). A branch-and-bound algorithm for the single machine earliness and tardiness scheduling problem. Computers & Operations Research, 26(7), 679-693.
[28]Martello, S., and P. Toth. (1990). Knapsack problems: Algorithms and computer implementations: John Wiley and Sons press.
[29]Mckendall, A. R., and J. Shang. (2006). Hybrid ant systems for the dynamic facility layout problem. Computers and Operations Research, 33(3), 790-803.
[30]Mizrak, P., and G. M. Bayhan. (2006). Comparative study of dispatching rules in a real-life job shop environment. Applied Artificial Intelligence, 20, 585-607.
[31]Pathumnakul, S., and P. J. Egbelu. (2006). An algorithm for minimizing weighted earliness penalty in assembly job shops. International Journal of Production Economics, 103(1), 230-245.
[32]Perng, C., Y. Lai, Z. Y. Zhuang and Z. P. Ho. (2007). Job scheduling in machinery industry with space constrain. Paper presented at the System Analysis Section, The Fourth Conference on Operations Research of Taiwan.
[33]Perng, C., Y. Lai and Z. P. Ho. (2008). Jobs scheduling in an assembly factory with space obstacles. Paper presented at the The 18th International Conference on Flexible Automation and Intelligent Manufacturing.
[34]Perng, C., S. S. Lin and Z. P. Ho. (2008). On space resource constrained job scheduling problems- A container loading heuristic approach. Paper presented at the The 4th International Conference on Natural Computation.
[35]Perng, C., Y. Lai, C. L. Ouyang and Z. P. Ho. (2008). Application of new approaches to space scheduling problems with early and tardy penalty. Paper presented at the The Chinese Institute of Industrial Engineers Conference.
[36]Perng, C., Y. Lai and Z. P. Ho. (2009). A space allocation algorithm for minimal early and tardy costs in space scheduling. Paper presented at the 3rd International Conference on New Trends in Information and Service Science papers (NISS).
[37]Pinedo, M. (2002). Scheduling theory, algorithms and systems (second ed.). New Jersey: Prentice Hall press.
[38]Puchinger, J., and G. R. Raidl. (2007). Models and algorithms for three-stage two-dimensional bin packing. European Journal of Operational Research, 183(3), 1304-1327.
[39]Pugazhendhi, S., S. Thiagarajan, C. Rajendran and N. Anantharaman. (2004). Relative performance evaluation of permutation and non-permutation schedules in flowline-based manufacturing systems with flowtime objective. International Journal of Advance Manufacturing Technology, 23, 820-830.
[40]Schaller, J. E., and J. N. D. Gupta. (2008). Single machine scheduling with family setups to minimize total earliness and tardiness. European Journal of Operational Research, 187(3), 1050-1068.
[41]Sciomachen, A., and E. Tanfani. (2007). A 3D-BPP approach for optimising stowage plans and terminal productivity. European Journal of Operational Research, 183(3), 1433-1446.
[42]Sleator, D. (1980). A 2.5 time optimal algorithm for packing in two dimensions. Information Processing Letters, 10(1), 37-40.
[43]Su, L. H. (2009). Minimizing earliness and tardiness subject to total completion time in an identical parallel machine system. Computers & Operations Research, 36(2), 461-471.
[44]Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operations Research, 64, 278-285.
[45]Thiagarajan, S., and C. Rajendran. (2005). Scheduling in dynamic assembly job-shops to minimize the sum of weighted earliness, weighted tardiness and weighted flowtime of jobs. Computers & Industrial Engineering, 49(4), 463-503.
[46]Tsai, R. D., E. M. Malstrom and W. Kuo. (1993). Three dimensional palletization of mixed box sizes. IIE Transactions, 25, 64-75.
[47]Wan, G., and B. P. C. Yen. (2002). Tabu search for single machine scheduling with distinct due windows and weighted earliness and tardiness penalties. European Journal of Operational Research, 142(2), 271-281