利用半主動排程之搜尋求解具最小與最大時間延遲限制之零工式排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：45

、訪客IP：3.16.137.117

姓名

葉秩州(Chih-chou Yeh) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

利用半主動排程之搜尋求解具最小與最大時間延遲限制之零工式排程問題
(Finding Semi-Active Schedules for Job Shop Scheduling Problem with Minimum and Maximum Time Lags)

相關論文

★ 以類神經網路探討晶圓測試良率預測與重測指標值之建立	★ 六標準突破性策略—企業管理議題
★ 限制驅導式在製罐產業生產管理之應用研究	★ 應用倒傳遞類神經網路於TFT-LCD G4.5代Cell廠不良問題與解決方法之研究
★ 限制驅導式生產排程在PCBA製程的運用	★ 平衡計分卡規劃與設計之研究-以海軍後勤支援指揮部修護工廠為例
★ 木製框式車身銷售數量之組合預測研究	★ 導入符合綠色產品RoHS之供應商管理-以光通訊產業L公司為例
★ 不同產品及供應商屬性對採購要求之相關性探討－以平面式觸控面板產業為例	★ 中長期產銷規劃之個案探討 -以抽絲產業為例
★ 消耗性部品存貨管理改善研究-以某邏輯測試公司之Socket Pin為例	★ 封裝廠之機台當機修復順序即時判別機制探討
★ 客戶危害限用物質規範研究-以TFT-LCD產業個案公司為例	★ PCB壓合代工業導入ISO/TS16949品質管理系統之研究-以K公司為例
★ 報價流程與價格議價之研究–以機殼產業為例	★ 產品量產前工程變更的分類機制與其可控制性探討-以某一手機產品家族為例

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 ( 永不開放)

摘要(中)

本論文主要探討具有最小與最大時間延遲限制之零工式 (job shop) 排程問題，此類時間限制常見於實務上生產製造，例如：化學產業的鍍鎳製程、半導體產業的曝光製程等等，在此零工式排程問題中，作業與作業的開始時間之間有一最小與最大的時間延遲，使得作業必須等候一段時間後才能開始，也必須在一特定時間內完成，在此問題中我們的目標為最小化最晚完工時間。
針對此一排程問題，我們發展一分枝界線演算法來求解此問題，在此演算法中，我們引用及修改了 Carlier and Pinson (1989)及Sheen and Liao (2007)的proposition來增加演算法的效率，在分枝的方法上，我們結合了Giffler and Thompson (1960)及Carlier and Pinson (1989)的分枝方式。

摘要(英)

We consider the job shop scheduling problem with minimum and maximum time lags while minimizing the makespan. This problem typically arises in a manufacturing environment where the next operation has to be carried out within a specific time range after the completion of the immediately preceding operation. This type of temporal constraints occurs in practical applications such food production, chemical production and steel production. We describe a branch and bound algorithm, based on the input and output of given clique, a concept first proposed by Carlier and Pinson (1989), and the relevant propositions adopted from Sheen and Liao (2007), for finding the optimal waiting times. For enumerating the solutions efficiently, we incorporate the branching scheme form Giffler and Thompson (1960) and Carlier and Pinson (1989) to generate semi-active schedules for the job shop scheduling problem with minimum and maximum time lags. In the computational experiments, we generate scenarios to showing we can either find an optimal schedule or establish the infeasibility in different waiting time ranges.

關鍵字(中)

★ 排程
★ 零工式生產
★ 最晚完工時間
★ 分枝界線演算法
★ 最小與最大時間延遲

關鍵字(英)

★ Scheduling
★ Job shop
★ makespan
★ Branch and bound algorithm
★ minimum and maximum time lags

論文目次

Outline
摘要 i
Abstract ii
Outline iii
Figure list v
Table list vi
Chapter 1 Introduction 1
1.1 Background and Motivation 1
1.2 Problem Description 3
1.3 Research objectives 5
1.4 Research methodology and framework 6
1.4.1 Research methodology 6
1.4.2 Research framework 7
Chapter 2 Literature 8
2.1 Disjunctive graph 8
2.2 Job Shop problem 9
2.3 Minimum and Maximum Time-lags 11
2.4 Job shop problem with minimum and maximum time-lags 12
Chapter 3 Branch and Bound Algorithm 13
3.1 Notations 13
3.2 Problem statement 13
3.3 Terminology 15
3.3.1 Clique of disjunctions 15
3.3.2 Starting time interval 15
3.3.3 Release time and tail 16
3.3.4 Single-machine problem with minimum and maximum time-lags 16
3.4 Propositions 16
3.4.1 Lower bound calculation 16
3.4.2 Computing E and S 17
3.4.3 Input and output determination 20
3.4.4 Immediate selection of a disjunctive constraint 20
3.4.5 Bounding scheme 21
3.5 Branch Scheme 21
3.6 Branch and bound algorithm 23
Chapter 4 Computational results 27
4.1 Test Problem Generation 27
4.2 Validation of the Branch and Bound Algorithm 29
Chapter 5 Conclusion 35
5.1 Research Conclusion and Contribution 35
5.2 Research Limitation 35
5.3 Further Research 36
References 37
Appendix A 41
Appendix B 42

參考文獻

- Adams, J., Balas, E., Zawack, D. (1988). The shifting bottleneck procedure for job shop scheduling. Management Science, 34, 391-401.
- Armstrong, R., Lei, L., Gu, S. (1994). A bounding scheme for deriving the minimal cycle time of a single-transporter N-stage process with time-window constraint. European Journal of Operational Research, 78, 130-140.
- Baker, K. R. (1974). Introduction to Sequencing and Scheduling. Wiley, New York.
- Balas, E., Christofides, N. (1981). A restricted Lagrangean approach to the traveling salesman problem. Mathematical Programming, 21, 19-46.
- Balas, E., Lenstra, J. K., Vazacopoulos, A. (1995). The one-machine problem with delayed precedence constraints and its use in job shop scheduling. Management Science, 41(1), 94-109.
- Brinkmann, R., Neumann, K. (1996). Heuristic procedures for resource-constrained project scheduling with minimal and maximum time lags: The resource –leveling and minimum project duration problems. Journal of Decision Systems, 5, 129-155.
- Brucker, P., Hilbig, T., Hurink, J. (1999). A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags. Discrete Applied Mathematics, 94, 77-99.
- Brucker, P., Jurisch, B., Kramer, A. (1994a). The job-shop problem and immediate selection. Annals of Operations Research, 50, 73-114.
- Brucker, P., Jurisch, B., Sievers, B. (1994b). A branch and bound algorithm for the job-shop scheduling problem. Discrete Applied Mathematics, 49, 107-127.
- Brucker, P., Drexl, A., Mohring, R., Neumann, K., Pesch, E. (1999). Resource-constrained project scheduling: Notation, classification, models, and methods. European Journal of Operational Research, 112, 3-41.
- Carlier, J. (1982). The one-machine sequencing problem. European Journal of Operational Research, 11, 42-47.
- Carlier, J., Pinson E. (1989). An algorithm for solving the job shop problem. Management Science, 35(2), 164-176.
- Carlier, J., Pinson, E. (1990). A practical use of Jackson’s preemptive schedule for solving the job-shop problem. Annals of Operations Research, 26, 269-287.
- Carlier, J., Pinson, E. (1994). Adjustment of heads and tails for the job-shop problem. European Journal of Operational Research, 78, 146-161.
- Caumond, A., Lacomme, P., Tchernev, N. (2008). A memetic algorithm for the job-shop with time-lags. Computers & Operations Research, 35, 2331-2356.
- Dauzere-Peres, S., Lasserre, J. B. (1993). A modified shifting bottleneck procedure for job-shop scheduling. International Journal of Production Research, 31(4), 923-932.
- Della Croce, F., Tadei, R., Volta, G. (1995). A genetic algorithm for job shop problem. Computers and Operations Research, 22, 15-24.
- Franck, B., Neumann, K., Schwindt, C. (2001). Project scheduling with calendars. OR Spektrum, 23, 325-334.
- Giffler, B., Thompson, G. L. (1960). Algorithm for solving production-scheduling problems. Operation Research, 8, 487-503.
- Heilmann, R. (2003). A branch-and-bound procedure for the multi-mode resource-constrained project scheduling problem with minimum and maximum time lags. European Journal of Operational Research, 144, 348-365.
- Herroelen, W., Reyck, B. D., Demeulemeester, E. (1998). Resource-constrained project scheduling: A survey of recent developments. Computers and Operations Research, 25, 279-302.
- Hurink, J., Keuchel, J. (2001). Local search algorithm for a single-machine scheduling problem with positive and negative time-lags. Discrete Applied Mathematics, 112, 179-197.
- Jain, A. S., Meeran, S. (1999). Deterministic job-shop scheduling: past, present and future. European Journal of Operational Research, 113, 390-434.
- Lei, L., Wang, T. J. (1991). The minimum common-cycle algorithm for cycle scheduling of time windows constraints. Management Science, 37(12), 1629-1639.
- Muth, J. F., Thompson, G. L. (1963). Industrial Scheduling. Prentice Hall: Englewood Cliffs.
- Neumann, K., Schwindt, C. (1997). Activity-on-node networks with minimal and maximal time lags and their application to make-to-order production. OR Spectrum, 19, 205-217.
- Neumann, K., Schwindt, C., Zimmermann, J. (2002). Recent results on resource-constrained project scheduling with time windows: Model, solution methods, and applications. Central European Journal of Operations Research, 10, 113-148.
- Neumann, K., Schwindt, C., Zimmermann, J. (2003). Order-based neighborhoods for project scheduling with nonregular objective functions. European Journal of Operational Research, 149, 325-343.
- Neumann, K., Zhan, J. (1995). Heuristics for the minimum project-duration problem with minimal and maximal time-lags under fixed resource constraints. Journal of Intelligent Manufacturing, 6, 145-154.
- Shapiro, G. W., Nuttle, H. W. (1998). Hoist scheduling for a PCB electroplating facility. AIIE Transactions, 20(2), 157-167.
- Sakawa, M., Mori, T. (1999). An efficient genetic algorithm for job-shop scheduling problems with fuzzy processing time and fuzzy duedate. Computers & Industrial Engineering, 36, 325-341.
- Su, L. H. (2003). A hybrid two-stage flowshop with limited waiting time constraints. Computers & Industrial Engineering, 44, 409-424.
- Sheen, G. J., Liao, L. W. (2007). A branch and bound algorithm for the one-machine scheduling problem with minimum and maximum time lags. European Journal of Operational Research, 181, 102–116.
- Park, B. J., Choi, H. R., Kim, H. S. (2003). A hybrid genetic algorithm for the job shop scheduling problems. Computers & Industrial Engineering, 45, 597–613.
- Wikum, E. D., Llewllyn, D. C., Nemhauser, G. L. (1994). One-machine generalized precedence constrained scheduling problems. Operations Research Letters, 16, 87-99.
- Yang, D. L., Chern, M. S. (1995). A two-machine flowshop sequencing problem with limited waiting time constraint. Computers & Industrial Engineering, 28, 63-70.
- Yih, Y., Liang, T. P., Moskowitz, H. (1993). Robot scheduling in a circuit board production line: a hybrid OR/ANN approach. IIE Transactions, 25(2), 26-33.
- Zhang, C. Y., Li, P. G., Rao, Y. Q., Guan, Z. L. (2008). A very fast TS/SA algorithm for the job shop scheduling problem. Computers & Operations Research, 35, 282-294.

指導教授

沈國基(Gwo-ji Sheen)

審核日期

2014-7-28

推文