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