作業調度與N個任務和M機

Question

問題描述：

我n優先約束的工作和m獨立的機器。每項作業的成本分配爲c（以1時間單位完成作業所需的機器數量）。它需要1時間單位完成一項工作，只有當c機器被分配給它時才能完成工作（工作是原子性的，不可能完成一半的工作）。

總之，有n作業和他們的優先約束，m機器和截止日期d（一些時間單位數）。

我的目標：

我要檢查它是否可以將工作分配給機器，所有的工作都內d時間單位完成。如果可能的話，我想打印一份時間表，爲每個作業分配時間單位（處理作業的時間單位，請參閱下面的示例）。

例子：

n = 5; // number of jobs 
m = 6; // number of machines 
d = 4; // deadline (number of time units in which the jobs need to be finished) 

Precedences: (read "Job(x,y)<--Job(q,p)" as "job x with cost y needs to be 
       finished before job q with cost p can be started") 
Job(3,1)<--Job(2,3)<--Job(1,4) 
Job(5,3)<--Job(4,3) 
Job(6,1) 

The solution: in this case it's possible to assign jobs to machines such that each job 
finishes in <=d time units. 
A possible schedule is 1 2 3 3 4 1. 

(read schedule as "job 1 and job 6 are done in the first time unit, job 2 
is done during the second time unit, jobs 3 and 4 during the third time unit, 
job 5 during the fourth time unit") 

我目前的做法：（第二次嘗試感謝@Ole VV的反例）

我想要做一個回溯的方式（最好的方法，我可以拿出）。目前我遇到麻煩實施它。

我想存儲作業及其優先順序。然後我確定一個集合A，其中包含當前時間單位可以解決的所有作業。然後，我找到一個集合B（它包含我在這個時間單元中考慮解決的所有集合），它包含所有可用有限數量的機器解決的A的子集，使得沒有其他工作可以添加到每個子集通過向其中一個子集添加作業，該子集中所有作業的成本超過「​​m」）。然後我重複這個程序，但沒有解決的工作（A \ B），我對B中的每個子集進行遞歸調用。當傳遞的剩餘工作集合（A \ B）爲空時（所有工作完成），停止如果遞歸深度爲< = d（如果滿足截止日期），則返回找到的計劃。

@Ole V.V.提供的示例中此方法的示例：

的步驟是指遞歸的深度，盒子指的是就業機會（第一個數字是作業ID，第二個是在單位時間成本在步驟0我明確地寫出來的子集（集。在這個步驟中我認爲要解決的工作）

現在我的問題是存儲作業及其優先級，找到可以當前時間單位解決的作業（集合A），找到我需要的作業子集考慮在當前時間單位（B組）中解決問題，並將其放在一個遞歸函數中，最終輸出找到的時間表或「沒有時間表找到」，如果沒有我的時間表截止日期。

Answer 1

你的方法似乎很好，但我相信有一個更簡單的方法。我建議你使用constraint saisfaction的方法。有很多方法來解決你的問題，例如mixed-integer programming，MaxSAT。你的任務似乎很簡單，你確定不會有大數字，所以你可以試試Minizinc。例如，請考慮this調度示例。

如果我們正在談論Java專用工具，請看Choco solver。

Answer 2

我相信你的貪婪算法並不總能給你正確的結果。

採取：

Job 1 costs 3 
Job 2 costs 3 
Job 3 costs 1 
Job 4 costs 5 
Job 5 costs 1 

機的數目爲7

優先次序是

#1 before #5 
#2 before #5 
#4 before #3 before #5 

截止日期爲3

我相信你的算法會選擇

Step 1 jobs 1, 2, total cost 6 
Step 2 job 4 cost 5 
Step 3 job 3 cost 1 

現在工作5還沒有運行，並且截止日期已到。你的程序會說這是不可能的。

以下時間表可能

Step 1 job 4 cost 5 
Step 2 jobs 1, 2, 3 total cost 7 
Step 3 job 5 cost 1 

Answer 3

你正在尋找這個問題顯然是NP難的，我們可以從partition problem做一個還原如下： 假設你有一個分區的問題與整數S1， s2 ...，sn。目標是找到這個集合的一個劃分成兩個集合S1和S2，使得S1上的和等於S2上的和。

我們可以通過爲每個整數定義一個作業（其成本是整數的值）來將這個問題轉化爲您的問題，並且我們添加一個額外的作業，必須在所有其他作業之後完成。我們設置d = 3

我們可以很容易地證明，當且僅當存在解決問題的解決方案時，纔有解決分區問題的方法，因此您的問題是NP難題。