多績效衡量單機排程問題之Pareto最佳解

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：39

、訪客IP：13.58.138.83

姓名

陳威仰(Wei-Yang Chen) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

多績效衡量單機排程問題之Pareto最佳解
(A Pareto-optimal solution procedure for the single machine scheduling problem with multiple performance measures)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

本研究探討一釋放時間(release times)存在與否之多績效衡量單機排程問題。目標是在受限於各種不同延遲作業數目條件下，求得最小化加權早交時間與延遲時間。問題假設各自具有不同的早交與延遲加權權重的n個作業有相同的到期日(due date )。本研究提供二演算法於各種延遲作業數目之限制下，分別針對存在釋放時間(release time)限制與否之前提，有效地產生Pareto最佳解。演算法的正確性與運算執行時間亦於本研究中被討論。另外也呈現本研究之演算法可排除大部份分枝樹(branching tree)內的節點以有效地找到解答。

摘要(英)

This dissertation investigates a single-machine scheduling problem without and with release time restriction. The objective is to minimize the summation of the weighted earliness and tardiness, subject to the number of tardy jobs. There are n jobs with a given common due date and each job has different weights for earliness and tardiness. Two algorithms are proposed to efficiently generate Pareto-optimal solutions for any possible number of tardy jobs without and with release time restriction. We also work with the benchmark problems discussed in Biskup and Feldmann [3]. The accuracy and run time of our algorithms are discussed. In addition the results show that the proposed algorithms can eliminate most nodes in the branching tree to efficiently find solutions.

關鍵字(中)

★ 延遲時間
★ 延遲作業
★ 早交時間
★ 排程
★ Pareto最佳解

關鍵字(英)

★ tardy jobs
★ tardiness
★ earliness
★ scheduling
★ Pareto-optimal

論文目次

摘要 ………………………….…i
Abstract …………………….…ii
誌謝 ………………………….…iii
Table of Content ………………..…iv
List of Figures ……………………vi
List of Tables ………………….…vii
Chapter 1 Introduction ……………1
1.1 Background and motivation …………….1
1.2 Problem definition ………………2
1.3 Research objectives …………..…4
1.4 Research methodology and framework ……………5
1.4.1 Research methodology ………….5
1.4.2 Research framework ………………5
Chapter 2 Literature review ……………..7
2.1 Multiple performance measures ………….…7
2.2 Release time restriction ………………11
Chapter 3 Pareto-optimal solution for scheduling problem with multiple performance measures …...………15
3.1 Branching scheme ………..…16
3.2 Basic propositions for a Pareto-optimal solution …………19
3.3 Branch and Bound algorithm ……..…27
3.4 Computational experience ………31
Chapter 4 Applicability of Pareto-optimal solution for scheduling problem with release time restriction …………42
4.1 Branching scheme …………..43
4.2 Basic propositions for a Pareto-optimal solution …………45
4.3 Branch and Bound algorithm ………….54
4.4 Computational experience .................60
Chapter 5 Conclusion .....................75
References …………….77

參考文獻

[1] Baker, K. R. and Scudder, G. D., “Sequencing with earliness and tardiness penalties: A Review,” Operations Research 38, 1990, 22-36.
[2] Bansal, S. P., “Single machine scheduling to minimize weighted sum of completion times with secondary criterion-a branch and bound approach,” European Journal of Operational Research, 1980, 5, 177-181.
[3] Biskup, D. and Feldmann, M., “Benchmarks for scheduling on a single-machine against restrictive and unrestrictive common due dates,” Computers and Operations Research, 2001, 28, 787–801.
[4] Burns, R. N., “Scheduling to minimize the weighted sum of completion times with secondary criteria,” Naval Research Logistics, 1976, 23, 125-129.
[5] Chand, S. and Schneeberger, H., “Single machine scheduling to minimize weighted earliness subject to no tardy jobs,” European Journal of Operational Research, 1988, 34, 221-230.
[6] Chen, W.-Y. and Sheen, G.-J., “Single machine scheduling with multiple performance measures: minimizing job dependent earliness and tardiness subject to the number of tardy jobs,” International Journal of Production Economics, 2007, 109, 214-229.
[7] Cheng, T. C. E. and Kahlbacher, H. G., “A proof for the longest/job/first policy in one/machine scheduling,” Naval Research Logistics, 1991, 38, 715-720.
[8] Cheng, T. C. E., Chen, Z.L., and Shakhlevich, N.V., “Common due date assignment and scheduling with ready times,” Computers & Operations Research, 2002, 29, 957-1967.
[9] Emmons, H., “A note on a scheduling problem with dual criteria,” Naval Research Logistics, 1975, 22, 615-616.
[10] Fattahi, P., “A Hybrid Multi Objective Algorithm for Flexible Job Shop Scheduling,” Engineering and Technology, 2009, 50, 551-556.
[11] Framinan, J. M. and Leisten, R., “A heuristic for scheduling a permutation flowshop with makespan objective subject to maximum tardiness,” International Journal of Production Economics, 2006, 99, 28-40.
[12] Feldmann, M. and Biskup, D., “Single-machine scheduling for minimizing earliness and tardiness penalties by meta-heuristic approaches,” Computers and Industrial Engineering, 2003, 44, 307-323.
[13] Hall, N., Kubiak W. and Sethi, S. , “Earliness-Tardiness Scheduling Problems, Ⅱ：Deviation of Completion Times About a Restrictive Common Due Date,” Operations Research, 1991, 39, 847-856.
[14] Heck, H. and Roberts, S., “A note on the extension of a result on scheduling with secondary criteria,” Naval Research Logistics, 1972, 19, 403-405.
[15] Hino, C. M., Ronconi, D. P. and Mendes, A. B., “Minimizing earliness and tardiness penalties in a single-machine problem with a common due date,” European Journal of Operational Research, 2005, 160, 190-201.
[16] Lawler, E. L., “Scheduling a single machine to minimize the number of late jobs,” EECS Department University of California, Berkeley, Technical Report No. UCB/CSD-83-139. 1983.
[17] Mazzini, R. and Armentano, V. A., “A heuristic for single machine scheduling with early and tardy costs,” European Journal of Operational Research, 2001, 128, 129-146.
[18] Miyazaki, S., “One machine scheduling problem with dual criteria,” Journal of Operational Research Society of Japan, 1981, 24, 37-50.
[19] Moore, J. M., “An n job, one machine sequencing algorithm for minimizing the number of late jobs,” Management Science, 1986, 15, 102-109.
[20] Nagar, A., Haddock, J. and Heragu, S., “Multiple and bicriteria scheduling：A literature survey,” European Journal of Operational Research, 1995, 81, 88-104.
[21] Nelson, R. T., Sarin, R. K., Daniels, R. L., “Scheduling with multiple performance measures：the one-machine case,” Management Science, 1986, 32, 464-479.
[22] Pathumnakul, S. and Egbelu P. J., “An algorithm for minimizing weighted earliness penalty in assembly job shops,” International Journal of Production Economics, 2006, 103, 230-245.
[23] Ronconi, D. P. and Kawamura, M. S., “The single machine earliness and tardiness scheduling problem: lower bounds and a branch-and-bound algorithm,” Computational & Applied Mathematics, 2010, 29, 107-124.
[24] Sen, T. and Gupta, S. K., “A branch-and bound procedure to solve a bicriterion scheduling problem,” IIE Transactions, 1983, 15, 84-88.
[25] Smith, W. E., “Various optimizers for single-stage production,” Naval Research Logistics, 1956, 3, 59-66.
[26] T’kindt, V. and Billaut, J.-C., “Some guideline to solve multicriteria scheduling problems,” IEEE, 1999, 463-468.
[27] Yeung, W. K., Oguz C. and Cheng, T. C. E., “Two-stage flowshop earliness and tardiness machine scheduling involving a common due window,” International Journal of Production Economics, 2004, 90, 421-434.
[28] Valente, J. M. S. and Alves, R. A. F. S., “Heuristics for the early/tardy scheduling problem with release dates,” International Journal of Production Economics, 2007, 106, 261-274.
[29] Valente, J.M.S. and Alves, R.A.F.S., “An exact approach to early/tardy scheduling with release dates,” Computers & Operations Research, 2005, 32, 2905-2917.

指導教授

沈國基(Gwo-Ji Sheen)

審核日期

2011-7-18

推文