現行的製造產業已轉變成快速生產、產量小而樣式多，在如此的生產環境下如何降低總延遲時間並提昇達交率成為主要的課題，同時也是企業競爭力的所在。因此有許多相關研究討論排程的派工法則，針對不同的情形提出不同的解決方法。
本研究主要是探討Job Shop的排程問題，同時考量交期與容許等待時間這兩個因素進行排程。為達成此目標，我們提出以「反向排序正向排程（Backward Sequence Forward Schedule, BSFS）」的啟發式演算法，利用後向排序得到每個作業的容許等待時間再進行前向排程，同時判斷作業是否可以提前工作，藉此降低總延遲時間。BSFS的結果與Baker在1983提出的修正交期法（Modified Due Date , MDD）進行比較討論，試圖找出兩者之間對於總延遲時間的表現特性。依據本研究的實驗結果顯示，由於BSFS在逆向排程中是以交期為開工時間，而在進行派工時，則是以作業本身的作業時間為決策準則，故較不受交期大小而影響排程的結果，由於加入詹森法則（Johnson’s rule）與『超車』概念所以在作業間的調整上較為靈活。

Under the production environment of current manufacturing industry, how to reduce the total tardiness and complete a deal has become a major research topic and is critical to increase competency. Therefore, there are many schedules of dispatching rules under study proposing different solutions regarding to different situations. This study mainly discusses the schedule problem of Job Shop that takes into account due date and tolerant waiting time for scheduling process. In order to achieving the goal, we have proposed a heuristic algorithm of Backward Sequence Forward Schedule (BSFS) which uses the backward sequence to obtain the tolerant waiting time for every procedure and then proceeds the forward scheduling by making a judgment about Job and Operation to be done earlier, in order to reduce the total tradiness. In this thesis, we also hold a comparison discussion with Bake’s Modified Due Date (MDD) proposed in 1983.The result show to find out the performing characteristics regarding the total tardiness between both method. Because BSFS depend on Due Date for ready time, and in scheduling is according to operation time so it is a little effect scheduling result because of Due Date.

ABSTRACT…………..………………………………….……………………………….…I
TABLE OF CONTENT….……………………………..…………………...…..…………II
LIST OF FIGURES............................................................................................................ IV
LIST OF TABLES …………………………………..…………………...………………. V
CHAPTER 1 INTRODUCTION…….…………………………………………………..1
1.1 Background and Motivation …………………...……………..……………….1
1.2 Research Objective.……………………...…………………………………….2
1.3 Research Procedure…...……………………………………………….……….2
1.4 Thesis Organization.……………………………..…………………………….5
CHAPTER 2 LITERATURE REVIEW………………………………………………...6
2.1 Outline for Scheduling Problem …...…..…………………………………….6
2.2 Job Shop Problem……..…………………...…………………………….……..8
2.3 Dispatching Rule……………………….…..…………………………….……10
2.4 Backward Scheduling ……………...................................................................11
CHAPTER 3 RESEARCH METHOD……………..…………………………………..17
3.1 Basic Hypothesis…………………………………………………………..….17
3.2 Model Construction…………..…………………….....…………………..….17
3.3 Algorithm ……...……………..…………………………………....................19
3.3.1 Idea Of Backward Sequence…..…..………………………………..19
3.3.2 Idea Of Froward Schedule…..………….…….….………………...19
3.3.3 Cut In Concept ………………………..……………………………..19
CHAPTER 4 SYSTEM ILLUSTRATION AND CASE ANALYSIS….…………….21
4.1 Introduction To Simulation Environment….…….………….……………...21
4.2 Scheduling Algorithm flow…….…………….………….………………...23
4.2.1 MDD Dispatching Process……….…………………………...…….23
4.2.2 BSFS Dispatching Process………….…...…………..………………25
4.3 Experirrent Results and Analysis..……………………….……..……...………29
CHAPTER 5 CONCLUSIONS.……………………………………..………………….39
5.1 Conclusion………..………….………..…………..….……………………....39
5.2 Future Work……………..………………….……………..………………...41
REFERENCES...……...…………………………...…………………………………..….43

[1] Allahverdi, A. and Tatari, M.F., “Simulation of different rules in stochastic
flowshops,” Computers & Industrial Engineering , Vol:31, Issue: 1-2, pp.209-212,
1996.

[2] Baker, K.R. and Kanet, J.J., “Job Shop Scheduling With Modified Due Dates,” Journal of operations management, Vol.4, No.1, 1983.

[3] Kim, Y.D., “A backward approach in list scheduling algorithms for multi-machine tardiness problem,” Computers Ops Res.Vol.22 , No.3, pp.307-319, 1995.

[4] Pinedo, M., “Scheduling：theory, algorithms, and system,” Prentice Hall, New Jersey, 1995.

[5] Watson, E.F., Medeiros, D.J. and Sadowski, R.P. “Generating component release plans with backward simulation,” Proceedings of the 1993 Winter Simulation Conference, pp.930-938, 1995.

[6] Watson, E.F., Medeiros, D.J. and Sadowski, R.P. “A simulation-based backward planning approach for order-release, ” Proceedings of the 1997 Winter Simulation Conference, pp.765-772, 1997.

[7] 陳建良，“排程概述”，機械工業雜誌，第12月號，pp.122-137，1995。
[8] 陳國偉，“平行-串連流程工廠中總延遲時間最小化之研究：IC 封裝作業之應用”，雲林科技大學工業工程系碩士論文，1997年。

[9] 張育嘉，“考量交期與機器使用率之Job Shop排程問題”，雲林科技大學工業工程系碩士論文，1998。

[10] 蘇傑昌，“台灣鐵路電腦輔助列車排程之研究”，雲林科技大學工業工程系碩士論文，1996。