Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Lập lịch Flowshop tái nhập với xem xét việc học để giảm thiểu thời gian hoàn thành
Tóm tắt
Trong những ngày gần đây, các chủ đề liên quan đến lập lịch trong các cấu trúc flowshop tái nhập và các mô hình lập lịch có xem xét đến việc học đã nhận được sự quan tâm ngày càng tăng trong các lĩnh vực nghiên cứu. Tuy nhiên, việc lập lịch kết hợp cả khái niệm học và tái nhập vẫn chưa được khám phá nhiều. Được thúc đẩy bởi hạn chế này, bài báo này xem xét lập lịch flowshop permutatation tái nhập cho các công việc liên quan đến một hàm học dựa trên tổng thời gian xử lý nhằm tối thiểu hóa thời gian hoàn thành. Vì vấn đề tương tự mà không có yếu tố học hoặc tái nhập đã được chứng minh là NP-khó, chúng tôi đề xuất bốn phương pháp heuristic và một thuật toán simulated annealing (SA) để tìm kiếm các giải pháp gần đúng. Ở giai đoạn đầu tiên, quy tắc Johnson (JH) kết hợp với bốn phương pháp tìm kiếm cục bộ, cụ thể là phương pháp NEH, hoán đổi cặp (PI), tái chèn dịch ngược (BACK), và tái chèn dịch tiến (FOR), được giải quyết trong vấn đề này. Chúng được gọi là bốn phương pháp heuristic là JH + NEH, JH + PI, JH + BACK và JH + FOR, tương ứng. Ở giai đoạn thứ hai, một thuật toán simulated annealing được khởi tạo với bốn giá trị khởi đầu khác nhau tốt từ giai đoạn đầu tiên được cung cấp nhằm tìm kiếm các giải pháp có chất lượng tốt. Cuối cùng, các kết quả thực nghiệm được kiểm tra để đánh giá hiệu suất của tất cả các thuật toán đề xuất khi kích thước công việc thay đổi hoặc số máy hoặc ảnh hưởng của việc học hoặc số lần tái nhập.
Từ khóa
#lập lịch flowshop #tái nhập #học máy #thuật toán heuristic #simulated annealingTài liệu tham khảo
Akram K, Kamal K (2016) Fast simulated annealing hybridized with quenching for solving job shop scheduling problem. Appl Soft Comput 49:510–523
Bellman R, Ernest R (1982) Mathematical aspects of scheduling and applications. Pergamon Press, Oxford
Bengu G (1994) A simulation-based scheduler for flexible flowlines. Int J Prod Res 32:321–344
Biskup D (1999) Single-machine scheduling with learning considerations. Eur J Oper Res 115:173–178
Biskup D (2008) A state-of-the-art review on scheduling with learning effect. Eur J Oper Res 188:315–329
Bispo CF, Tayur S (2001) Managing simple re-entrant flow lines: theoretical foundation and experimental results. IIE Trans 33:609–623
Chen J-S (2006) A branch-and-bound procedure for the reentrant permutation flow-shop scheduling problem. Int J Adv Manuf Technol 29:1186–1193
Chen J-S, Pan JCH, Wu CK (2007) Minimizing makespan in reentrant flow-shops using hybrid tabu search. Int J Adv Manuf Technol 34:353–361
Cheng TCE, Wang G (2000) Single machine scheduling with learning effect considerations. Ann Oper Res 98:273–290
Della Croce F, Narayan V, Tadei R (1996) The two-machine total completion time flow shop problem. Eur J Oper Res 90:227–237
Dondeti VR, Mohanty BB (1998) Impact of learning and fatigue factors on single machine scheduling with penalties for tardy jobs. Eur J Oper Res 105:509–524
Gawiejnowicz S (1996) A note on scheduling on a single processor with speed dependent on a number of executed jobs. Inf Process Lett 56:297–300
Janiak A, Krysiak T, Trela R (2011) Scheduling problems with learning and ageing effects: a survey. Decis Mak Manuf 5(1–2):19–36
Johnson SM (1954) Optimal two- and three-stage production schedules with setup times. Nav Res Logist Q 1:61–68
Kirkpatrick S, Gelatt C, Vecchi M (1983) Optimization by simulated annealing. Science 220(4598):671–680
Koulamas C, Kyparisis GJ (2007) Single-machine and two-machine flowshop scheduling with general learning functions. Eur J Oper Res 178:402–407
Kubiak W, Lou SXC, Wang Y (1996) Mean flow time minimization in reentrant job-shops with a hub. Oper Res 44:764–776
Lee WC, Wu C-C, Sung HJ (2004) A bi-criterion single-machine scheduling problem with learning considerations. Acta Inform 40:303–315
Lin YK, Chuang WH (2015) Uniform parallel machine scheduling problems with a truncation sum-of-logarithm-processing-times-based learning effect. Int J Internet Manuf Serv 4(1):37–53
Lin D, Lee CKM (2011) A review of the research methodology for the re-entrant scheduling problem. Int J Prod Res 49(8):2221–2242
Liu S-C, Hung W-L, Wu C-C (2015) Note on a single-machine scheduling problem with sum of processing times based learning and ready times. Math Probl Eng 2015:9, Article ID 452602
Moschakis IA, Karatza HD (2015) Multi-criteria scheduling of Bag-of-Tasks applications on heterogeneous interlinked clouds with simulated annealing. J Syst Softw 101:1–14
Nawaz M, Enscore EE, Ham I (1983) A heuristic algorithm for the m-machine, n-job sequencing problem. Omega 11:91–95
Niu Y-P, Wan L, Wang J-B (2015) A note on scheduling jobs with extended sum-of-processing-times-based and position-based learning effect. Asia Pac J Oper Res 32:1550001 [12 pages]
Pan JCH, Chen J-S (2003) Minimizing makespan in re-entrant permutation flow-shops. J Oper Res Soc 54:642–653
Taghi Assadi M, Bagheri M (2016) Differential evolution and Population-based simulated annealing for truck scheduling problem in multiple door cross-docking systems. Comput Ind Eng 96:149–161
Uzsoy R, Lee CY, Martin-Vega LA (1992) A review of production planning and scheduling models in the semiconductor industry-part 1: system characteristics, performance evaluation and production planning. IIE Trans 24:47–60
Vargas-Villamil FD, Rivera DE (2001) A model predictive control approach for real-time optimization of reentrant manufacturing lines. Comput Ind 45:45–57
Wang MY, Sethi SP, van de Velde SL (1997) Minimizing makespan in a class of reentrant shops. Oper Res 45:702–712
Wilson JM (1989) Alternative formulations of a flow-shop scheduling problem. J Oper Res Soc 40:395–399
Wu Y-B, Wang J-J (2016) Single-machine scheduling with truncated sum-of-processing-times-based learning effect including proportional delivery times. Neural Comput Appl 27(4):937–943
Wu WH, Wu W-H, Chen JC, Lin WC, Wu JP, Wu C-C (2015) A heuristic-based genetic algorithm for the two-machine flowshop scheduling with learning consideration. J Manuf Syst 351:223–233
Wu W-H, Yin Y, Cheng TCE, Lin W-C, Chen JC, Luo S-Y, Wu C-C (2016) A combined approach for two-agent scheduling with sum-of-processing-times-based learning effect. J Oper Res Soc. doi:10.1057/s41274-016-0008-3
Xiao J, Yang C, Zheng L, Gupta JND (2015) A hybrid Lagrangian-simulated annealing-based heuristic for the parallel-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times. Comput Oper Res 63:72–82
Xu J, Yin Y, Cheng TCE, Wu C-C, Gu S (2014) A memetic algorithm for the re-entrant permutation flowshop scheduling problem to minimize the makespan. Appl Soft Comput 24:277–283
Xu J, Lin W-C, Wu J, Cheng S-R, Wang Z-L, Wu C-C (2016) Heuristic based genetic algorithms for the re-entrant total completion time flowshop scheduling with learning consideration. Int J Comput Intell Syst 9(6):1082–1100
Yin Y, Xu D, Sun K, Li H (2009) Some scheduling problems with general position-dependent and time-dependent learning effects. Inf Sci 179:2416–2425
Yin Y, Xu D, Wang J (2010a) Some single-machine scheduling problems past-sequence-dependent setup times and a general learning effect. Int J Adv Manuf Technol 48:1123–1132
Yin Y, Xu D, Wang J (2010b) Single-machine scheduling with a general sum-of-actual-processing-times-based and job-position-based learning effect. Appl Math Model 34:3623–3630
Yin Y, Xu D, Huang X (2011) Notes on “some single-machine scheduling problems with general position-dependent and time-dependent learning effects”. Inf Sci 181:2209–2217
Yin Y, Liu M, Hao J, Zhou M (2012) Single machine scheduling with job position-dependent learning and time-dependent deterioration. IEEE Trans Syst Man Cybern Part A Syst Hum 42:192–200
Zhang X, Liu SC, Yin Y, Wu C-C (2016) Single-machine scheduling problems with a learning effect matrix. Iran J Sci Technol Trans A Sci. doi:10.1007/s40995-016-0080-1