多目標問題的圖形表示

Question

我正在研究涉及多目標調度問題的論文項目的可能研究主題，我想知道是否有人有將圖像表示爲這樣的問題的想法。我查看了一些關於這個主題的文獻，並且一種常見的方法似乎是在邊緣使用成本向量而不是單個成本數字。這對我來說很有意義，但我不明白我如何通過這種方式對我的問題的某些方面進行建模。

特別是模型中有資源將每個活動限制在特定的時間窗口內，而有效的時間表必須安排這些限制內的每個活動。此外，還有一些相互依賴的活動。例如，用戶可以在兩個活動之間放置時間增量要求，說明它們必須在彼此的若干個時間單位內進行安排，或者必須至少在有效時間安排中隔開一定數量的時間單位。我可以想象將這些作爲可選元素建模成本矢量，但有沒有更好的方法？

獎金的問題是，這也應該是一個最少的承諾調度。每個活動都應該有一個名義上有n個單位長的窗口，因此不一定是活動的總訂單。

任何關於表達這樣的問題的文獻將不勝感激！

Answer 1

這裏有一個關鍵字爲您搜索：約束編程

可以作爲所謂的約束滿足問題，即一組變量，它們的可能值這樣的問題模型和組約束你的解決方案（=選擇變量的值）必須滿足。

通過CP，您可以將上面的文本直接表達爲單個約束（f.ex.，活動A必須在活動B變得像A.endTime < = B.startTime之前）。

至於文獻，有許多關於CP可用的書籍和論文，特別是關注調度（甚至有專門針對調度問題的CP的會議）。

Answer 2

聽起來像Job Shop Scheduling：有大量的文章。