Java中的作業調度問題

Question

我正在寫一個解決作業計劃的問題，但我很難理解如何。

The Wood Shop的世界着名搖椅訂單積壓（每張訂單一把椅子）。有幾個 步驟參與制作一個手工Baber搖椅（例如，切割木片，組裝，打磨，應用污漬， 和應用清漆）。

製作椅子所需的總時間爲1周。然而，由於椅子在不同的 地區和不同的市場出售，每個訂單的利潤額可能不同。此外，每個訂單還有一個截止日期爲 。公司只能在截止日期前賺取利潤;否則，利潤爲0.

編寫一個程序，該程序將確定最大化利潤的訂單的最佳時間表。輸入文件 包含一個或多個測試用例。測試用例中的第一行將包含一個整數n（0 n 1000），表示待處理訂單的數量爲 。

n的值爲0表示輸入文件的結尾。 接下來的n行包含3個正整數。第一個整數i是一個訂單號。

給定的 測試用例的所有訂單號都是唯一的。第二個整數表示從現在起至截止日期爲止的週數，其中i爲 和 。 第三個整數表示如果訂單的最終期限已滿足，該公司將獲得的利潤金額爲 和 。

我所要求的是一種算法，我應該如何解決這個問題。

對於輸入文件中的每個測試用例，輸出文件應輸出一行，報告從 以最優順序完成訂單產生的利潤額。

Example Input File (sched.in) 
7 
1 3 40 
2 1 35 
3 1 30 
4 3 25 
5 1 20 
6 3 15 
7 2 10 
4 
3054 2 30 
4099 1 35 
3059 2 25 
2098 1 40 
0 
Example Output File (sched.out) 
100 
70 

Answer 1

你的問題的假設是不完整的。你需要知道你每週可以做多少把椅子。也許你可以一次完成所有的事情。但是讓我們假設你只能製作一個。解決方案就是這樣。

基於卡梅倫斯金納的非常聰明的意見，我我的答案改成這樣：

public class tarea 
{   
    List<input> datas = new ArrayList<input>(); 

    class input 
    { 
     public int profit; 
     public int deadline; 
     public int index1; 
     public int index2; 
     public int sum() {return index1+index2;} 
     /** 
     * @param profit 
     * @param deadline 
     */ 
     public input(int deadline, int profit) 
     { 
      super(); 
      this.profit = profit; 
      this.deadline = deadline; 
     } 

    } 


    public void readData1() 
    { 
     this.datas.add(new input(1,1)); 
     this.datas.add(new input(1,1)); 
     this.datas.add(new input(1,1)); 
     this.datas.add(new input(1,1)); 
     this.datas.add(new input(1,1)); 
     this.datas.add(new input(1,1)); 
     this.datas.add(new input(1,1)); 
     this.datas.add(new input(1,1)); 
     this.datas.add(new input(1,1)); 
     this.datas.add(new input(1,1)); 
     this.datas.add(new input(10,1000)); 
     this.datas.add(new input(10,1000)); 
     this.datas.add(new input(10,1000)); 
     this.datas.add(new input(10,1000)); 
     this.datas.add(new input(10,1000)); 
     this.datas.add(new input(10,1000)); 
     this.datas.add(new input(10,1000)); 
     this.datas.add(new input(10,1000)); 
     this.datas.add(new input(10,1000)); 
     this.datas.add(new input(10,1000)); 
    } 


    public void readData2() 
    {/* 
     3 40 
     2 1 35 
     3 1 30 
     4 3 25 
     5 1 20 
     6 3 15 
     7 2 10 */ 

     this.datas.add(new input(3,40)); 
     this.datas.add(new input(1,35)); 
     this.datas.add(new input(1,30)); 
     this.datas.add(new input(3,25)); 
     this.datas.add(new input(1,20)); 
     this.datas.add(new input(3,15)); 
     this.datas.add(new input(2,10)); 
    } 

    public void readData3() 
    {/* 
    2 30 
    4099 1 35 
    3059 2 25 
    2098 1 40*/ 

     this.datas.add(new input(2,30)); 
     this.datas.add(new input(1,35)); 
     this.datas.add(new input(2,25)); 
     this.datas.add(new input(1,40)); 
    } 



    @SuppressWarnings("unchecked") 
    public void sortbyprofit(List<input> datas) 
    { 
     Collections.sort(datas, new Comparator() { 

      public int compare(Object o1, Object o2) 
      { 
       if(((input)(o1)).profit < ((input)(o2)).profit) 
        return 1; 
       else if(((input)(o1)).profit == ((input)(o2)).profit) 
        return 0; 
       else return -1; 
      }}); 
    } 

    @SuppressWarnings("unchecked") 
    public void sortbydeadline(List<input> datas) 
     { 
      Collections.sort(datas, new Comparator() { 

      public int compare(Object o1, Object o2) 
      { 
       if(((input)(o1)).deadline > ((input)(o2)).deadline) 
        return 1; 
       else if(((input)(o1)).deadline == ((input)(o2)).deadline) 
        return 0; 
       else return -1; 
      }}); 
     } 


    @SuppressWarnings("unchecked") 
    public void sortbySum(List<input> datas) 
     { 
      Collections.sort(datas, new Comparator() { 

      public int compare(Object o1, Object o2) 
      { 
       if(((input)(o1)).sum() > ((input)(o2)).sum()) 
        return 1; 
       else if(((input)(o1)).sum() == ((input)(o2)).sum()) 
        return 0; 
       else return -1; 
      }}); 
     } 


    @SuppressWarnings("unchecked") 
    public static void main(String[] args) 
    { 
     tarea tsk = new tarea(); 
     //tsk.readData1(); 
     //tsk.readData2(); 
     tsk.readData3(); 


     while (tsk.datas.size() > 0) 
     { 
      //sort by profit 
      tsk.sortbyprofit(tsk.datas); 
      int idx0 = 1; 
      //assign index 
      for (input data : tsk.datas) 
      { 
       data.index1 = idx0; 
       idx0++; 
      } 

      //sort by deadline 
      tsk.sortbydeadline(tsk.datas); 
      int idx2 = 1; 
      for (input data : tsk.datas) 
      { 
       data.index2 = idx2; 
       idx2++; 
      } 

      //sort by sum and profit 
      tsk.sortbySum(tsk.datas); 

      List<input> tmpdatas = new ArrayList<input>(); 
      int valsum = tsk.datas.get(0).sum(); 
      for (input data : tsk.datas) 
      { 
       if (data.sum() == valsum) 
        tmpdatas.add(data); 
      }    
      tsk.sortbyprofit(tmpdatas); 

      //get the first one as result 
      input thedata = tmpdatas.get(0); 

      System.out.println("result ===> " + thedata.profit); 

      tsk.datas.remove(thedata); 
      tmpdatas = new ArrayList<input>(); 
      for (input data : tsk.datas) 
      { 
       data.deadline--; 
       if (data.deadline > 0) 
        tmpdatas.add(data); 
      } 
      tsk.datas = tmpdatas; 
     } 


    } 


} 

Answer 2

好的，Java在這裏不是問題。不要專注於語言，而應該考慮算法。

這種「味道」喜歡的東西，那裏是一個dynamicprogramming解決方案，但從此我有種推斷你是一個初學者，那麼窮舉搜索可能是比較容易，只要訂單數量是合理的。在詳盡的搜索中，您只需佈置每個可能的訂單並保存最有利可圖的訂單。

Answer 3

有很多方法可以解決加工車間問題。首先閱讀維基百科條目，然後選擇一本關於算法設計的好書。你的教授可以推薦一個。我懷疑動態編程是解決這個問題的好方法，但也會有其他方法。

這是一個難題，所以不要期待一個簡單的答案。許多人仍在研究如何有效地解決這個問題。

Answer 4

歡迎的NP完全問題，規劃的奇妙世界。一旦你擴大規模，就不可能在我們的有生之年找到最佳解決方案。這並不重要，但是你必須在給定的時間內找到最好的解決方案（毆打人類規劃者和其他軟件程序）。

不要自己寫這些算法（除非你是有多年經驗的專家）。使用現成的庫，專門在這些類型的問題，如：

• Drools Planner（開源，ASL，JAVA）

• openTS

• cpsolver