Bài toán tổ hợp lập lịch-vị trí ngược với độ trễ tối đa trên cây
và
Article Sidebar
Full Text: 
PDF
Abstract
We address the problem of finding the location of a machine on trees and scheduling jobs (located at vertices) so that the maximum lateness is minimized. The customers (jobs) move to the machine whenever they are called due to the slackness of space for jobs waiting at the machine location. We develop an algorithm that solves the corresponding problem in O(n2) time, where n is the number of vertices in the tree. On the counterpart, we investigate the problem of reducing edge lengths within a given budget to improve the maximum lateness at a prespecified point as much as possible. We call it the reverse scheduling location problem with maximum lateness on trees. A greedy-type algorithm that solved the problem in quadratic time is discussed.
Tóm tắt
Bài báo giải quyết vấn đề tìm vị trí của máy trên cây và lập kế hoạch cho các công việc nhất định (nằm ở các đỉnh) sao cho độ trễ tối đa được giảm thiểu. Khách hàng (công việc) di chuyển đến máy bất cứ khi nào họ được gọi do thiếu không gian dành cho công việc tại vị trí đặt máy. Một thuật toán giải bài toán tương ứng trong thời gian O(n2) đã được phát triển, trong đó n là số đỉnh trên cây. Mặt khác, vấn đề giảm độ dài cạnh trong một ngân sách nhất định được xem xét để cải thiện độ trễ tối đa càng nhiều càng tốt tại một điểm được xác định trước. Đây được gọi là bài toán lập lịch-vị trí ngược với độ trễ tối đa trên cây. Một thuật toán tham lam được đề xuất để giải quyết vấn đề trong thời gian bậc hai.
Article Details
This work is licensed under a Creative Commons Attribution-NonCommercial 4.0 International License.
Tài liệu tham khảo
Alizadeh, B., & Burkard, R. E. (2011). Uniform-cost inverse absolute and vertex center location problems with edge length variations on trees. Discrete Appl. Math, 159(8), 706-716. https://doi.org/10.1016/j.dam.2011.01.009
Awerbuch, B. & Gallager, R. (1987). A new distributed algorithm to find breadth first search trees. IEEE Transactions on Information Theory, 33(3), 315-322. https://doi.org/10.1109/TIT.1987.1057314
Berman, O., Ingco, D. I., & Odoni, A. (1992). Improving the location of minisum facilities through network modification. Annals of Operations Research, 40(1), 1-16. https://doi.org/10.1007/BF02060467
Berman, O., Ingco, D. I., & Odoni, A. (1994). Improving the location of minimax facilities through network modification. Networks, 24(1), 31-41.
https://doi.org/10.1002/net.3230240105
Bonab, B. F., Burkard, R. E., & Alizadeh, B. (2010). Inverse median location problems with variable coordinates. Central European Journal of Operations Research, 18(3), 365-381. https://doi.org/10.1007/s10100-009-0114-2
Brucker, P. (2007). Scheduling Algorithms (5th ed.). Springer Verlag, Heidelberg.
Burkard, R. E., Pleschiutschnig, C., & Zhang, J. Z. (2004). Inverse median problems. Discrete Optimization, 1(1), 23-39. https://doi.org/10.1016/j.disopt.2004.03.003
Etemad, R., & Alizadeh, B. (2017). Combinatorial algorithms for reverse selective undesirable center location problems on cycle graphs. Journal of the Operations Research Society of China, 5(1), 347-361. https://doi.org/10.1007/s40305-016-0144-0
Goldman, A. J. (1971). Optimal Center Location in Simple Networks. Transportation Science, 5, 212-221.
https://doi.org/10.1287/trsc.5.2.212
Handler, G. Y., & Mirchandani, P. B. (1979). Location on Networks: Theory and Algorithms. MIT Press, Cambridge.
Hennes, H. (2005). Integrated scheduling and location models. Shaker Verlag, Aachen.
Hennes H., & Hamacher, H. W. (2001). Integrated scheduling and location models: Single machine makespan problem. Stud. Locat. Anal., 16, 77-90.
Hessler, C. J. (2016). Scheduling-location algorithms with application in evacuation planning. Dr. Hut Verlag, Müchen.
Kalsch M. T., & Drezner, Z. (2010). Solving scheduling and location problems in the plane simultaneously. Computers and Operations Research, 37, 256-264. https://doi.org/10.1016/j.cor.2009.04.014
Krumke S. O., & Le, H. M. (2022). 2-approximation algorithm for minmax absolute maximum lateness scheduling-location problem, Operations Research Letters, 50(6), 732-737. https://doi.org/10.1016/j.orl.2022.11.001
Nazari, M., & Fathali, J. (2023). Inverse and Reverse 2-facility Location Problems with Equality Measures on a Network. Iranian Journal of Mathematical Sciences and Informatics, 18(1), 211-225.
https://doi.org/10.52547/ijmsi.18.1.211
Sepasian, A. R., & Rahbarnia, F. (2015). An O(nlogn) algorithm for the inverse 1-median problem on trees with variable vertex weights and edge reductions. Optimization, 64(3), 595-602.
Sepasian, A. R., & Tayyebi, J. (2020). Further study on reverse 1-center problem on trees. Asia-Pacific Journal of Operational Research, 37(6), 1-18. https://doi.org/10.1142/S0217595920500347
Tayyebi, J., & Sepasian, A. R. (2023). Reverse 1-centre problem on trees under convex piecewise-linear cost function. Optimization, 72(3), 843-860. https://doi.org/10.1080/02331934.2021.1995730
Yim S., Hong S. P., Park M. J., & Chung, Y. (2022). Inverse interval scheduling via reduction on a single machine. European Journal of Operational Research, 303(2), 541-549.
https://doi.org/10.1016/j.ejor.2022.02.046