Nội dung được dịch bởi AI, chỉ mang tính chất tham khảo
Lịch trình gần như không thể gián đoạn
Tóm tắt
Các mô hình lý thuyết đồ thị được mô tả để giải quyết các vấn đề lập lịch có thể gián đoạn và không thể gián đoạn với nguồn lực có thể tái tạo. Các điều kiện được thiết lập để tồn tại lịch trình không thể gián đoạn. Những kết quả này có thể được áp dụng để giảm thiểu sự gián đoạn trong các lịch trình được thu được bằng phương pháp hai pha được phát triển để lập lịch có thể gián đoạn trên các bộ xử lý không liên quan.
Từ khóa
#lập lịch #lý thuyết đồ thị #nguồn lực có thể tái tạo #lịch trình có thể gián đoạn #lịch trình không thể gián đoạnTài liệu tham khảo
C. Berge,Graphes (Gauthier-Villars, Paris, 1983).
J. Błaźewicz, W. Cellary, R. Słowiński and J. Węglarz,Scheduling under Resource Constraints: Deterministic Models (Baltzer, Basel, 1986), [Ann. Oper. Res. 7(1986)].
S. Foldes and P.L. Hammer, Split graphs, in:Graph Theory and Computing, Congressus Numerantium XIXI, Utilitas Math., Winnipeg (1977), pp. 311–315.
M.R. Garey and D.S. Johnson,Computers and Intractability: A Guide to the Theory of NP-Completness (Freeman, San Francisco, 1979).
E.L. Lawler, Recent results in the theory of machine scheduling, in:Mathematical Programming: The State of the Art, ed. A. Bachem, M. Grötschel and B. Korte (Springer Verlag, New York, 1983), pp. 202–234.
M.C. Golumbic,Algorithmic Graph Theory and Perfect Graphs (Academic Press, New York, 1980).
T. Gonzales and S. Sahni, J. ACM 23(1976)665–679.
R. Słowinski, Production scheduling on parallel machines subject to staircase demand, Cahiers du LAMSADE 74, Univ. de Paris-Dauphine (1987).
L.E. Trotter, Line perfect graphs, Math. Progr. 12(1977)255–259.
D. de Werra, On the two-phase method for preemptive scheduling, Eur. J. Oper. Res. 37(1988)227–235.
D. de Werre, On line perfect graphs, Math. Progr. 15(1978)236–238.
D. de Werra, Graph-theoretical models for preemptive scheduling, in:Advances in Project Scheduling, ed. R. Słowinski and J. Węglarz (Elsevier, Amsterdam, 1989).