Lên lịch cho bài toán nhiều lớp công việc với ba tiêu chí và đơn hàng khách hàng trên một máy bằng cách sử dụng các phương pháp heuristics và kỹ thuật tăng nhiệt giả

Operational Research - Tập 24 - Trang 1-22 - 2023
Chin-Chia Wu1, Xingong Zhang2, Danyu Bai3, Ameni Azzouz4,5, Wen-Hsiang Wu6, Xin-Rong Chen1, Win-Chin Lin1
1Department of Statistics, Feng Chia University, Taichung City, Taiwan
2College of Mathematics Science, Chongqing Normal University, Chongqing, China
3School of Maritime Economics and Management, Dalian Maritime University, Dalian, China
4SMART Laboratory, Institut supérieur de gestion de Tunis, Université de Tunis, Tunis, Tunisia
5Tunis Business School, University of Tunis, Tunis, Tunisia
6Department of Healthcare Management, Yuanpei University of Medical Technology, Hsinchu City, Taiwan

Tóm tắt

Các bài toán lập lịch nhiều lớp công việc giải quyết một nhóm công việc thuộc nhiều lớp, trong đó để giảm thời gian xử lý, các công việc trong cùng một lớp có xu hướng được thực hiện cùng nhau với thời gian chuẩn bị giống nhau. Ngược lại, các bài toán lập lịch đơn hàng khách hàng tập trung vào việc hoàn thành tất cả các công việc (thuộc các lớp khác nhau) theo cùng một thứ tự tại cùng một thời điểm để giảm chi phí giao hàng. Vì các nghiên cứu liên quan về các bài toán lập lịch nhiều lớp công việc với nhiều tiêu chí hiện tại khá hạn chế trong cộng đồng nghiên cứu hiện nay, nghiên cứu này điều tra các bài toán lập lịch với ba tiêu chí có nhiều lớp công việc và đơn hàng khách hàng trên một máy, nơi mục tiêu là giảm thiểu một tổ hợp tuyến tính của tổng thời gian hoàn thành, tổng thời gian hoàn thành của tất cả các công việc, và tổng khoảng cách của tất cả các đơn hàng. Do độ phức tạp cao của vấn đề được đề xuất, lập trình số hỗn hợp được phát triển để lập phương trình cho vấn đề, và một phương pháp nhánh và giới hạn cùng với một giới hạn dưới và một thuộc tính được sử dụng để tìm ra các lịch tối ưu. Sau đó, hai phương pháp heuristics và một thuật toán tăng nhiệt giả được đề xuất để giải quyết vấn đề một cách xấp xỉ. Kết quả mô phỏng của các phương pháp heuristics và thuật toán được đề xuất được đánh giá thông qua các phương pháp thống kê.

Từ khóa

#lập lịch #nhiều lớp công việc #đơn hàng khách hàng #lập trình số hỗn hợp #phương pháp nhánh và giới hạn #heuristics #thuật toán tăng nhiệt giả

Tài liệu tham khảo

Allahverdi A, Gupta JND, Aldowaisan T (1999) A review of scheduling research involving setup considerations. Omega 27(2):219–239 Allahverdi A, Ng CT, Cheng TCE, Kovalyov MY (2008) A survey of scheduling problems with setup times or costs. Eur J Oper Res 187(3):985–1032 Allahverdi A (2015) The third comprehensive survey on scheduling problems with setup times/costs. Eur J Oper Res 246(2):345–378 Della Croce F, Narayan V, Tadei R (1996) The two-machine total completion time flow shop problem. Eur J Oper Res 90:227–237 Dileepan P, Sen T (1988) Bicriterion static scheduling research for a single machine. Omega 16:53–59 Erel E, Ghosh JB (2007) Customer order scheduling on a single machine with family setup times: complexity and algorithms. Appl Math Comput 185:11–18 Framinan JM, Perez-Gonzalez P, Fernandez-Viagas V (2019) Deterministic assembly scheduling problems: a review and classification of concurrent-type scheduling models and solution procedures. Eur J Oper Res 273:401–417 Fry TD, Armstrong RD, Lewis H (1989) A framework for single machine multiple objective sequencing research. Omega 17:595–607 Gupta JND, Ho JC, van der Veen JA (1997) Single machine hierarchical scheduling with customer orders and multiple job classes. Ann Oper Res 70:127–143 Hassan DA, Amiri NM, Ramadan AM (2022) Solving three objectives single-machine scheduling problem using fuzzy multi-objective linear programming. Tikrit J Pure Sci 27(6):82–87 Hollander MD, Wolfe A, Chicken E (2014) Nonparametric statistical methods, 3rd edn. Wiley, Hoboken Hosseinzadeh MR, Heydari M, Mazdeh MM (2022) Mathematical modeling and two metaheuristic algorithms for integrated process planning and group scheduling with sequence-dependent setup time. Oper Res Int J 22:5055–5105 Hsu SY, Liu CH (2009) Improving the delivery efficiency of the customer order scheduling problem in a job shop. Comput Ind Eng 57:856–866 Kirkpatrick S, Gellat CD, Vecchi MP (1983) Optimization by simulated annealing algorithm. Science 220:671–680 Kim SC, Bobrowski PM (1997) Scheduling jobs with uncertain setup times and sequence dependency. Omega 25(4):437–447 Klamroth K, Wiecek MM (2001) A time-dependent multiple criteria single-machine scheduling problem. Eur J Oper Res 135:17–26 Kovalenko YV, Zakharov AO (2020) The Pareto set reduction in bicriteria customer order scheduling on a single machine with setup times. In: Journal of physics: conference series, IOP Publishing. p 012087 Liaee MM, Emmons H (1997) Scheduling families of jobs with setup times. Int J Prod Econ 51(3):165–176 Liao CJ (1993) Tradeoff between setup times and carrying costs for finished items. Comput Oper Res 20:697–705 Li LY, Lin WC, Bai D, Zhang X, Azzouz A, Cheng SR, Wu YL, Wu CC (2023) Composite heuristics and water wave optimality algorithms for tricriteria multiple job classes and customer order scheduling on a single machine. Int J Ind Eng Comput 14(2):265–274 Lin BMT, Yin PY, Liu YS (2013) Sequence-dependent scheduling with order deliveries. Appl Math Comput 222:58–71 Lin BMT, Kononov AV (2007) Customer order scheduling to minimize the number of tardy jobs. Eur J Oper Res 183(2):944–948 Lin WC, Zhang X, Liu X, Hu KX, Cheng SR, Azzouz A, Wu CC (2023) Sequencing single machine multiple-class customer order jobs using heuirstics and improved simulated annealing algorithms. RAIRO Op Res 57:1417–1441 Liu CH (2009) Lot streaming for customer order scheduling problem in job shop environments. Int J Comput Integr Manuf 22(9):890–907 Liu CH (2010) A coordinated scheduling system for customer orders scheduling problem in job shop environments. Expert Syst Appl 37:7831–7837 Qian J, Lin H, Kong Y, Wang Y (2020) Tri-criteria single machine scheduling model with release times and learning factor. Appl Math Comput 387:124543 Shi Z, Wang L, Liu P, Shi L (2017) Minimizing completion time for order scheduling: formulation and heuristic algorithm. IEEE Trans Autom Sci Eng 14(4):1558–1569 Shi Z, Huang Z, Shi L (2018) Customer order scheduling on batch processing machines with incompatible job families. Int J Prod Res 56(1–2):795–808 Soltani R, Jolai F, Zandieh M (2010) Two robust meta-heuristics for scheduling multiple job classes on a single machine with multiple criteria. Expert Syst Appl 37:5951–5959 Suma T, Murugesan R (2019) Mathematical model and heuristic based subtask scheduling algorithm for order scheduling. AIP Conf Proc 2095:030026-1–030026-9 Suerie C (2006) Modeling of period overlapping setup times. Eur J Oper Res 174(2):874–886 Suerie C, Stadtler H (2003) The capacitated lot-sizing problem with linked lot-sizes. Manag Sci 49:1039–1054 van Donk DP, van Doorne R (2016) The impact of the customer order decoupling point on type and level of supply chain Integration. Int J Prod Res 54(9):2572–2584 Xu X, Ma Y, Zhou Z, Zhao Y (2015) Customer order scheduling on unrelated parallel machines to minimize total completion time. IEEE Trans Autom Sci Eng 12(1):244–257 Yang WH (1999) Survey of scheduling research involving setup times. Int J Syst Sci 30(2):143–155 Yang J (2011) Customer order scheduling in a two machine flowshop. Int J Manag Sci 17(1):95–116 Yedidsion L (2012) Bi-criteria and tri-criteria analysis to minimize maximum lateness makespan and resource consumption for scheduling a single machine. J Sched 15:665–679 Ying KC, Pourhejazy P, Cheng CY, Syu RS (2020) Supply chain-oriented permutation flowshop scheduling considering flexible assembly and setup times. Int J Prod Res 61(1):258–281 Zangwill WI (1987) From EOQ towards ZI. Manag Sci 33:1209–1223 Zhao Y, Xu X, Li H, Liu Y (2018) Stochastic customer order scheduling with setup times to minimize expected cycle time. Int J Prod Res 56(7):2684–2706
Thông tin
Thông tin xuất bản

Operational Research

Tập 24

1-22

Thông tin tác giả