雙機流程型生產環境下加權提早與延遲成本最小化之排程問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：7

、訪客IP：3.145.51.15

姓名

徐士凱(Shih-Kai Hsu) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

雙機流程型生產環境下加權提早與延遲成本最小化之排程問題
(Two-Machine Flow Shops Scheduling to Minimize Job Independent Earliness and Tardiness Penalties with a Given Common Due Date)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

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

摘要(中)

本研究探討雙機流程型生產環境下加權提早與延遲成本最小化之排程問題。在這篇論文中，我們假設有多個工作它們有共同的交期要加工，權重是根據這個工作是提早或延遲完工來決定。本論文提出一個分支界限法求得一多產品之加工順序、最小加權提早與延遲成本。而我們也針對提出的分支界限法進行實驗和資料分析，用以驗證演算法的正確性和效率。

摘要(英)

This study deals with the two-machine flow shops scheduling problem with the consideration of earliness and tardiness penalties.
There are multiple jobs with a given common due date to be scheduled. All jobs have equal earliness and tardiness weights, and the weight of a job depends on whether the job is early or late, which are job-independent. The objective is to find a schedule that minimizes the weighted sum of earliness and tardiness penalties.
We propose a number of propositions and revised Bagchi’s algorithm as a lower bound, which are implemented in our branch-and-bound algorithm to eliminate nodes efficiently in the branching tree. We also conduct computational analysis to show the validation and the effectiveness of our algorithm compared with enumeration.

關鍵字(中)

★ 雙機流程型生產
★ 分支界限法
★ 交期
★ 提早與延遲成本
★ 排程

關鍵字(英)

★ Two-machine flow shops
★ Scheduling
★ Earliness and tardiness penalties
★ Due date
★ Branch-and-bound algorithm

論文目次

Abstract...................................................................I
Table of contents..........................................................II
List of figures............................................................IV
List of tables.............................................................V
Chapter 1 Introduction.....................................................1
1.1 Motivation and background............................................1
1.2 Problem description and assumptions..................................3
1.3 Research objectives..................................................4
1.4 Research methodology and framework...................................4
1.4.1 Research methodology.............................................4
1.4.2 Research framework...............................................6
Chapter 2 Literature review................................................7
2.1 Single machine scheduling with earliness and tardiness penalties.....7
2.1.1 Sum of absolute deviations (SAD) problem.........................8
2.1.2 Weighted sum of absolute deviations (WSAD) problem...............9
2.2 Flow shops scheduling with earliness and tardiness penalties.........10
Chapter 3 Two-machine flow shops scheduling problem with job-independent weighted earliness and tardiness penalties.................................15
3.0 Notation.............................................................15
3.1 Basic propositions and branching scheme..............................16
3.2 Branch-and-bound algorithm...........................................27
Chapter 4 Computational analysis...........................................31
4.1 Validation...........................................................31
4.2 Evaluation...........................................................32
Chapter 5 Conclusion.......................................................41
5.1 Research contribution................................................41
5.2 Further research.....................................................42
References.................................................................43
Appendix...................................................................45

參考文獻

[1] Bagchi, U., Chang, Y-L, and Sullivan, R.S., “Minimizing Absolute and Squared Deviations of Completion Times with Different Earliness and Tardiness Penalties and a Common Due Date,” Naval Research Logistics 34, 1987, 739-751.
[2] Bagchi, U., Sullivan, R.S., and Chang, Y.-L., “Minimizing Mean Absolute Deviation of Completion Times about a Common Due Date,” Naval Research Logistics Quarterly 33, 1986, 227-240.
[3] Baker, K.R., Scudder, G.D., “Sequencing with Earliness and Tardiness Penalties：A Review,” Operations Research 38, 1990, 22-36.
[4] Birman, M., Mosheiov, G., “A Note on a Due Date Assignment on a Two-Machine Flow Shop,” Computers & Operations Research 31, 2004, 473-480.
[5] Bülbül, K., Kaminsky, P., Yano, C., “Flow Shop Scheduling with Earliness, Tardiness, and Inventory Holding Costs,” Naval Research Logistics 51, 2004, 407-445.
[6] Chen, Z.-L., “Scheduling and Common Due Date Assignment with Earliness-Tardiness Penalties and Batch Delivery Costs,” European Journal of Operational Research 93, 1996, 49-60.
[7] Garey, M.R., Johnson, D.S., Sethi, R., “The Complexity of Flowshop and Jobshop Scheduling,” Mathematics of Operations Research 1, 1976, 117-129.
[8] Gupta, J.N.D., Lauff, V., Werner, F., “Two-Machine Flow Shop Scheduling with Nonregular Criteria,” Journal of Mathematical Modelling and Algorithms 3, 2004, 123-151.
[9] Hall, N., Posner, M., “Earliness-Tardiness Scheduling Problems,Ⅰ：Weighted Deviation of Completion Times about a Common Due Date,” Operations Research 39, 1991, 836-846.
[10] Hall, N., Kubiak, W., Sethi, S., “Earliness-Tardiness Scheduling Problems, Ⅱ：Deviation of Completion Times about a Restrictive Common Due Date,” Operations Research 39, 1991, 847-856.
[11] Johnson, S.M., “Optimal Two and Three Stage Production schedules with Setup Times Included,” Naval Research Logistics Quarterly 1, 1954, 61-68.
[12] Kanet, J.J., “Minimizing the Average Deviation of Job Completion Time about a Common Due Date,” Naval Research Logistics Quarterly 28, 1981, 643-651.
[13] Lauff, V., Werner, F., “On the Complexity and Some Properties of Multi-stage Scheduling Problems with Earliness and Tardiness Penalties,” Computers and Operations Research 31, 2004, 317-345.
[14] Lauff, V., Werner, F., “Scheduling with Common Due Date, Earliness and Tardiness Penalties for Multimachine Problems: A Survey,” Mathematical and Computer Modeling 40, 2004, 637-655.
[15] Panwalkar, S.S., Smith, M.L., Seidmann, A., “Common Due Date Assignment to Minimize Total Penalty for the One Machine Scheduling Problem,” Operations Research 30, 1982, 391-399.
[16] Sarper, H., “Minimizing the Sum of Absolute Deviations about a Common Due Date for the Two-Machine Flow Shop Problem,” Applied Mathematical Modeling 19, 1995, 153-161.
[17] Sung, C.S., Min, J.I., “Scheduling in a Two-Machine Flowshop with Batch Processing Machine(s) for Earliness/Tardiness Measure under a Common Due Date,” European Journal of Operational Research 131, 2001, 95-106.
[18] Szwarc, W., “Single-Machine Scheduling to Minimize Absolute Deviation of Completion Times from a Common Due Date ,” Naval Research Logistics 36, 1989, 663-673.
[19] Ventura, J.A., Weng, M.X., “An Improved Dynamic Programming Algorithm for the Single Machine Mean Absolute Deviation Problem with a Restrictive Common Due Date,” Operations Research Letters 17, 1995, 149-152.
[20] Yeung, W.K., Oğuz, C., Cheng, T.C.E., “Two-Stage Flowshop Earliness and Tardiness Machine Scheduling Involving a Common Due Window,” International Journal of Production Economics 90, 2004, 421-434.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2005-7-3

推文