A Bi-Objective Genetic Algorithms for solving a job shop  scheduling problem with material constraint and  parallel batching when minimizing makespan and  total number of tardy stage-outs.

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：30

、訪客IP：3.144.115.125

姓名

蔡承哲(Chen-Che Tsai) 查詢紙本館藏

畢業系所

工業管理研究所

論文名稱

(A Bi-Objective Genetic Algorithms for solving a job shop scheduling problem with material constraint and parallel batching when minimizing makespan and total number of tardy stage-outs.)

相關論文

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

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

至系統瀏覽論文 (2029-7-31以後開放)

摘要(中)

本研究主旨在探討零工式排程問題(job shop scheduling problem)下，考量材料限制(material constraint)以及批次處理(batching)的問題，目標為極小化最大完工時間(makespan)以及極小化total number of tardy stage-outs。在材料限制之下，當裝載在機器上的材料組合使用時間達到特定時長時，材料組合就必須進行更換。另外，我們建立了一個分離弧線圖(conjunctive graph)，其中每個工件(job)都具有多個層級(layer)，每個層級包含多個操作(operation)，而在層和層之間有額外的弧線去界定各層級的順序。在特定的層級的最後一個操作之後，我們新增了一個點並用弧線將此點與層級的最後一個操作相連，作為衡量該層級是否完工的依據。
針對研究的問題，我們使用了非支配排序遺傳演算法(NSGA-II)，除了修改前人的Job based Order Crossover(JOX)之外，也將原本隨機的變異過程改為使用局部搜索中的鄰域結構(neighborhood structure)取代。我們的鄰域結構會透過雙目標的關鍵路徑(critical path)所定義，以及引入偏好值來幫助我們的搜索過程。我們還會透過對移動(move)計算下限(lower bound)，並使用節省法(saving method)量化此移動對於雙目標的改善，以此作為選擇移動的依據。

摘要(英)

The main purpose of this study is to investigate the Job Shop Scheduling Problem, taking into account material constraints and batching, with the objective of minimizing the maximum makespan and the total number of tardy stage-outs. Under material constraints, when the usage time of materials set which loaded on machine reaches certain limits, the materials set needs to be changed. Additionally, we have established a conjunctive graph where each job has multiple layers, each layer consists of multiple operations, and additional arcs are used to define the order of the layers. After the last operation in a specific layer, we add a node and connect it with an arc to the last operation in that layer to determine if that layer has completed.
To address the research problem, we modified the Non-Dominated Sorting Genetic Algorithm (NSGA-II) by revising Job Based Order Crossover (JOX) and replacing the originally random mutation process with the neighborhood structure of local search. Our neighborhood structure is defined by critical paths of two objectives, and we introduce a preference value to aid in our search process. We also calculate lower bounds for moves and quantify the improvement of these moves on both objectives by using a saving method, which serves as the basis for selecting move.

關鍵字(中)

★ 零工式排程
★ 雙目標
★ 分離弧線圖
★ 節省法
★ 基因演算法

關鍵字(英)

★ Job shop scheduling problem
★ bi-objective
★ disjunctive graph
★ saving method
★ genetic algorithm

論文目次

摘要 i
Abstract ii
Table of contents iii
List of figures v
List of tables vi
Chapter 1 Introduction 1
1.1 Research motivation and background 1
1.2 Research description 3
1.3 Research objectives 4
1.4 Research methodologies 4
Chapter 2 Literature Review 7
2.1 Job shop scheduling problem 7
2.2 Disjunctive graph 9
2.3 Neighborhood structure 10
2.4 Non-dominated sorting genetic algorithm-II 11
Chapter 3 Research Methodology 14
3.1 Disjunctive graph model 14
3.2 Neighborhood operator 16
3.2.1 Single operation moves 16
3.2.2 Entire micro block moves 17
3.2.3 Feasibility check 19
3.2.4 Lower bound 20
3.2.5 Saving value 26
3.3 NSGA-II algorithm 28
3.3.1 Initialization 29
3.3.2 Dominance of Pareto 30
3.3.3 Non-dominated sort 31
3.3.4 Crossover operator 31
3.3.5 Mutation operator 35
3.3.6 The process to generate the next population 37
3.4 Search strategy 37
Chapter 4 Computation result 39
4.1 The ability of the feasibility checks to reduce the neighborhood size 41
4.2 Comparison between selecting move by saving value and randomly selecting 42
4.3 Comparison between different inheritance rate 44
4.4 Comparison between different neighborhood structure 47
Chapter 5 Conclusion 50
Acknowledgement 50
Appendix 51
Appendix 1. Proof of Theorem 1. 51
Appendix 2. Proof of Theorem 3. 58
Appendix 3. Illustration of crossover operator. 60
Reference 68

參考文獻

Adams, J., Balas, E., Zawack, D., 1988. Shifting Bottleneck Procedure for Job Shop Scheduling. Manage. Sci. 34, 391–401.
Amaral Armentano, V., Rigão Scrich, C., 2000. Tabu search for minimizing total tardiness in a job shop. Int. J. Prod. Econ. 63, 131–140.
Amjad, M.K., Butt, S.I., Kousar, R., Ahmad, R., Agha, M.H., Faping, Z., Anjum, N., Asgher, U., 2018. Recent Research Trends in Genetic Algorithm Based Flexible Job Shop Scheduling Problems. Math. Probl. Eng. 2018.
Anh, N.H.G., 2023. Scheduling Parallel Batch Processing Machines with Incompatible Families, Time Window Con-straints and Machine Eligibility Determination. Unpublished master’s thesis, National Central University, Taoyuan City.
Balas, E., 1969. Machine sequencing via disjunctive graphs: An implicit enumeration algorithm. Oper. Res. 17, 941–957.
Balas, E., Lenstra, J.K., Vazacopoulos, A., 1995. The One-machine Problem with Delayed Precedence Constraints and Its Use in Job Shop Scheduling. Manage. Sci. 41(1), 94–109.
Balas, E., Vazacopoulos, A., 1998. Guided local search with shifting bottleneck for job shop scheduling. Manage. Sci. 44(2), 262–275.
Barnes, J.W., Chambers, J.B., 1995. Solving the job shop scheduling problem with tabu search. IIE Trans. (Institute Ind. Eng. 27, 257–263.
Bellman, R., 1958. On a routing problem. Q. Appl. Math. 16, 87–90.
Bierwirth, C., 1995. A generalized permutation approach to job shop scheduling with genetic algorithms. OR Spectrum. 17, 87–92
Bierwirth, C., Kuhpfahl, J., 2017. Extended GRASP for the job shop scheduling problem with total weighted tardiness objective. Eur. J. Oper. Res. 261(3), 835-848.
Brandimarte, P., 1993. Routing and scheduling in a flexible job shop by tabu search. Ann Oper. Res. 41, 157–183.
Braune, R., Zäpfel, G., Affenzeller, M., 2013. Enhancing local search algorithms for job shops with min-sum objectives by approximate move evaluation. J. Sched. 16, 495–518.
Brucker, P., Jurisch, B., Sievers, B., 1994. A branch and bound algorithm for the job-shop scheduling problem. Discret. Appl. Math. 49, 107–127.
Bülbül, K., 2011. A hybrid shifting bottleneck-tabu search heuristic for the job shop total weighted tardiness problem. Comput. Oper. Res. 38, 967–983.
Carlier, J., Pinson, É., 1989. An algorithm for solving the job-shop problem. Manage. Sci. 35, 164–176.
Carlier, J., Pinson, É., 1994. Adjustment of heads and tails for the job-shop problem. Eur. J. Oper. Res. 78, 146-161.
Chang, S.C., Lee, L.H., Pang, L.S., Chen, T.W.Y., Weng, Y.C., Chiang, H.Der, Dai, D.W.H., 1995. Iterative capacity allocation and production flow estimation for scheduling semiconductor fabrication. Proc. IEEE/CPMT Int. Electron. Manuf. Technol. Symp. 508–512.
Chaudhry, I.A., Khan, A.A., 2016. A research survey: Review of flexible job shop scheduling techniques. Int. Trans. Oper. Res. 23, 551–591.
Clarke, G., Wright, J.R., 1964. Scheduling of Vehicle Routing Problem from a Central Depot to a Number of Delivery Points. Oper. Res. 12, 568-581.
Cruz-Chávez, M.A., 2015. Neighborhood generation mechanism applied in simulated annealing to job shop scheduling problems. Int. J. Syst. Sci. 46, 2673–2685.
Cruz-Chavez, M.A., Frausto-Solis, J., 2004. Simulated annealing with restart to job shop scheduling problem using upper bounds. Lect. Notes Artif. Intell. (Subseries Lect. Notes Comput. Sci. 3070, 860–865.
Dauzère-Pérès, S., Paulli, J., 1997. An integrated approach for modeling and solving the general multiprocessor job-shop scheduling problem using tabu search. Ann Oper. Res. 70, 281-306.
Deb, K., Pratap, A., Agarwal, S., Meyarivan, T., 2002, A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Trans. Evol. Comput. 6(2), 182-197.
DeBontridder, K.M.J., 2005. Minimizing total weighted tardiness in a generalized job shop. J. Sched. 8, 479–496.
Dell’Amico, M., Trubian, M., 1993. Applying tabu search to the job-shop scheduling problem. Ann. Oper. Res. 41, 231–252.
DellaCroce, F., Tadei, R., Volta, G., 1995. A genetic algorithm for the job shop problem. Comput. Oper. Res. 22, 15–24.
Dorndorf, U., Pesch, E, 1995. Evolution based learning in a job shop scheduling environment. Comput. Oper. Res. 22, 25-40.
M.Essafi, I., Mati, Y., Dauzère-Pérès, S., 2008. A genetic local search algorithm for minimizing total weighted tardiness in the job-shop scheduling problem. Comput. Oper. Res. 35, 2599–2616.
Fieldsend, J.E., Everson, R.M., Singh, S., 2003. Using unconstrained elite archives for multiobjective optimization. IEEE Trans. Evol. Comput. 7, 305–323.
Gao, J., Gen, M., Sun, L., Zhao, X., 2007. A hybrid of genetic algorithm and bottleneck shifting for multiobjective flexible job shop scheduling problems. Comput. Ind. Eng. 53, 149–162.
Gao, K.Z., Suganthan, P.N., Pan, Q.K., Chua, T.J., Cai, T.X., Chong, C.S., 2014. Discrete harmony search algorithm for flexible job shop scheduling problem with multiple objectives. J. Intell. Manuf. 27, 363–374.
García-León, A., Dauzère-Pérès, S., Mati, Y., 2016. A General Approach for the Multi-Objective Flexible Job-Shop Scheduling Problem with Regular Criteria. Proc. 15th Int. Conf. Proj. Manag. Sched. 260–263.
García-León, A.A., Dauzère-Pérès, S., Mati, Y., 2019. An efficient Pareto approach for solving the multi-objective flexible job-shop scheduling problem with regular criteria. Comput. Oper. Res. 108, 187–200.
Garey, M.R., Johnson, D.S., Laboratomes, B., Hill, M., 1976. Scheduling Tasks with Non-uniform Deadlines on Two Processors. J. Assoc. Comput. Mach. 23, 461–467.
Genova, K., Kirilov, L., Guliashki, V., 2015. A survey of solving approaches for multiple objective flexible job shop scheduling problems. Cybern. Inf. Technol. 15, 3–22.
Geramianfar, R., Pakzad, M., Golhashem, H., Tavakkoli-Moghaddam, R., 2013. A multi-objective hub covering location problem under congestion using simulated annealing algorithm. Uncertain Supply Chain Manag. 1, 153–164.
Graham, R.L., Lawler, E.L., Lenstra, J.K., Kan, A.H.G.R., 1979. Optimization and approximation in deterministic sequencing and scheduling: A survey. Ann. Discret. Math. 5, 287-326.
Huang, K.L., Liao, C.J., 2008. Ant colony optimization combined with taboo search for the job shop scheduling problem. Comput. Oper. Res. 35, 1030–1046.
Jia, S., Hu, Z.H., 2014. Path-relinking Tabu search for the multi-objective flexible job shop scheduling problem. Comput. Oper. Res. 47, 11–26.
Kao, Y.T., Chang, S.C., 2018. Setting daily production targets with novel approximation of target tracking operations for semiconductor manufacturing. J. Manuf. Syst. 49, 107–120.
Knowles, J., Corne, D., 2004. Bounded Pareto Archiving: Theory and Practice. Metaheuristics multiobjective Optim. Springer, Berlin, Heidelb. 39–64.
Kreipl, S, 2000. A large step random walk for minimizing total weighted tardiness in a job shop. J. Sched. 3,125-138.
Kuo, Y.H., 2023. An extended batch-oblivious approach for flexible Job shop with batching and material consumption when minimizing the total weighted material consumed and makespan. Unpublished master’s thesis, National Central University, Taoyuan City.
Lange, J., Werner, F., 2018. Approaches to modeling train scheduling problems as job-shop problems with blocking constraints. J. Sched. 21, 191–207.
Li, J.Q., Pan, Q.K., Chen, J., 2012. A hybrid Pareto-based local search algorithm for multi-objective flexible job shop scheduling problems. Int. J. Prod. Res. 50, 1063–1078.
Li, J.Q., Pan, Q.K., Tasgetiren, M.F., 2014. A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities. Appl. Math. Model. 38, 1111–1132.
M’Hallah, R., Al-Khamis, T., 2015. A Benders decomposition approach to the weighted number of tardy jobs scheduling problem on unrelated parallel machines with production costs. Int. J. Prod. Res. 53, 5977–5987.
Manne, A.S., 1960. On the job-shop scheduling problem. Oper. Res. 8, 219–223.
Mason, S.J., Fowler, J.W. and Matthew Carlyle, W., 2002. A modified shifting bottleneck heuristic for minimizing total weighted tardiness in complex job shops. J. Sched. 5, 247-262.
Mati, Y., Dauzere-Pérès, S., Lahlou, C., 2011. A general approach for optimizing regular criteria in the job-shop scheduling problem. Eur. J. Oper. Res. 212, 33–42.
Miguel A. González, Riccardo Rasconi, Angelo Oddi., 2022. Metaheuristics for multiobjective optimization in energy-efficient job shops. Engineering Applications of Artificial Intelligence. 115.
Mokhtari, H., Hasani, A., 2017. An energy-efficient multi-objective optimization for flexible job-shop scheduling problem. Comput. Chem. Eng. 104, 339–352.
Mönch, L., Fowler, J.W., Mason, S.J., 2012. Production planning and control for semiconductor wafer fabrication facilities: modeling, analysis, and systems. Springer Science & Business Media.
Moslehi, G., Mahnam, M., 2011. A Pareto approach to multi-objective flexible job-shop scheduling problem using particle swarm optimization and local search. Int. J. Prod. Econ. 129, 14–22.
Murovec, B., 2015. Job-shop local-search move evaluation without direct consideration of the criterion’s value. Eur. J. Oper. Res. 241, 320-329.
Muth, J.F., Thompson, G.L., 1963. Industrial Scheduling. Prentice-Hall, Englewood Cliffs, N.J.
Nicoarǎ, E.S., Filip, F.G., Paraschiv, N., 2011. Simulation-based optimization using genetic algorithms for multi-objective flexible JSSP. Stud. Informatics Control 20, 333–344.
Nowicki, E., Smutnicki, C., 1996. A fast taboo search algorithm for the job shop problem. Manage. Sci. 42, 797–813.
Rabiee, M., Zandieh, M., Ramezani, P., 2012. Bi-objective partial flexible job shop scheduling problem: NSGA-II, NRGA, MOGA and PAES approaches. Int. J. Prod. Res. 50, 7327–7342.
Pezzella, F., Merelli, E., 2000. Tabu search method guided by shifting bottleneck for the job shop scheduling problem. Eur. J. Oper. Res. 120, 297–310.
Pinedo, M., Singer, M., 1999. A shifting bottleneck heuristic for minimizing the total weighted tardiness in a job shop. Nav. Res. Logist. 46, 1–17.
Riquelme, N., Von Lücken, C., Baran, B., 2015. Performance metrics in multi-objective optimization. CLEI 2015: Arequipa, Peru. 1-11.
Roy, B. and Sussmann, B, 1964. Les Problems d’Ordon Ordonnancement Avec Constraints Disjunctives. SEMA. Note D.S., No. 9, Paris.
Schott, J.R., 1995. Fault tolerant design using single and multicriteria genetic algorithm optimization. Department of Aeronautics and Astronautics, Massachusetts Institute of Technology.
Schulz, S., Neufeld, J.S., Buscher, U., 2019. A multi-objective iterated local search algorithm for comprehensive energy-aware hybrid flow shop scheduling. J. Clean. Prod. 224, 421–434.
Sebastian Knopp, Stéphane Dauzère-Pérès, Claude Yugma., 2017. A batch-oblivious approach for Complex Job-Shop scheduling problems. Eur. J. Oper. Res. 263(1), 50-61.
Sheen, G.J., 2023. A Bi-Objeective Optimization for Job Shop Scheduling Problem Minimizing Both Makespan and Number of Tardy Stage-Outs. Retrieved from National Science and Technology Council.
Singh, M.R., Singh, M., Mahapatra, S.S., Jagadev, N., 2016. Particle swarm optimization algorithm embedded with maximum deviation theory for solving multi-objective flexible job shop scheduling problem. Int. J. Adv. Manuf. Technol. 85, 2353–2366.
Snyman, S. & Bekker, J., 2019. Comparing the performance of different metaheuristics when solving a stochastic bi-objective job shop scheduling problem. In Proceedings of the 2019 ORSSA Annual Conference.
Sobeyko, O., Mönch, L., 2016. Heuristic approaches for scheduling jobs in large-scale flexible job shops. Comput. Oper. Res. 68, 97–109.
Taillard, E.D., 1994. Parallel Taboo Search Techniques for the Job Shop Scheduling Problem. ORSA J. Comput. 6(2), 107-220.
Tamaki, H., Kita, H., Kobayashi, S., 1996. Multi-objective optimization by genetic algorithms: A review. Proc. IEEE Int. Conf. Evol. Comput. 517–522.
Tamssaouet, K., Dauzère-Pérès, S., Knopp, S., Bitar, A., Yugma, C., 2022. Multiobjective optimization for complex flexible job-shop scheduling problems. Eur. J. Oper. Res. 296, 87–100.
Türkyılmaz, A., Senvar, O., Ünal. İ., Bulkan. S., 2022. A hybrid genetic algorithm based on a two-level hypervolume contribution measure selection strategy for bi-objective flexible job shop problem. Comput. Oper. Res. 141, 105694.
Vilcot G., Billaut J.C., 2008. A tabu search and a genetic algorithm for solving a bicriteria general job shop scheduling problem. Eur. J. Oper. Res. 190(2), 398-411.
VanLaarhoven, P.J.M., Aarts, E.H.L., Lenstra, J.K., 1992. Job shop scheduling by simulated annealing. Oper. Res. 40, 113–125.
Wagner, H.M., 1959. An integer linear-programming model for machine scheduling. Nav. Res. Logist. Q. 6, 131–140.
Wang, L., Wang, S., Liu, M., 2013. A Pareto-based estimation of distribution algorithm for the multi-objective flexible job-shop scheduling problem. Int. J. Prod. Res. 51, 3574–3592.
Wu, G.L., Wei, K., Tsai, C.Y., Chang, S.C., Wang, N.J., Tsai, R.L., Liu, H.P., 1998. TSS: A daily production target setting system for fabs. In 1998 Semicond. Manuf. Technol. Workshop. 86–98.
Xia, W., Wu, Z., 2005. An effective hybrid optimization approach for multi-objective flexible job-shop scheduling problems. Comput. Ind. Eng. 48, 409–425.
Xing, L.N., Chen, Y.W., Yang, K.W., 2009. An efficient search method for multi-objective flexible job shop scheduling problems. J. Intell. Manuf. 20, 283–293.
Yan, H., Sen, Li, W.C., 2017. A multi-objective scheduling algorithm with self-evolutionary feature for job-shop-like knowledgeable manufacturing cell. J. Intell. Manuf. 28, 337–351.
Yuan, Y., Xu, H., 2015. Multiobjective flexible job shop scheduling using memetic algorithms. IEEE Trans. Autom. Sci. Eng. 12, 336–353.
Zhang, C.Y., Li, P.G., Guan, Z.L., Rao, Y.Q., 2007. A tabu search algorithm with a new neighborhood structure for the job shop scheduling problem. Comput. Oper. Res. 34, 3229–3242.
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. Comput. Oper. Res. 35, 282–294.
Zhang, G., Shao, X., Li, P., Gao, L., 2009. An effective hybrid particle swarm optimization algorithm for multi-objective flexible job-shop scheduling problem. Comput. Ind. Eng. 56, 1309–1318.
Zhang, R., Wu, C., 2011. A simulated annealing algorithm based on block properties for the job shop scheduling problem with total weighted tardiness objective. Comput. Oper. Res. 38, 854–867.
Zhou, H., Cheung, W., Leung, L.C., 2009. Minimizing weighted tardiness of job-shop scheduling using a hybrid genetic algorithm. Eur. J. Oper. Res. 194,637-649.

指導教授

沈國基

審核日期

2024-7-17

推文