Java中的作业调度算法

Question

我正在写一个问题来解决工作日程，但我很难理解如何解决

这家木制品店积压着世界著名的摇椅订单（每份订单1把椅子）。有几个 手工制作巴伯摇椅的步骤（如切割木片、组装、打磨、涂抹污渍、， 和涂清漆）

制作椅子所需的总时间为1周。然而，由于椅子是以不同的价格出售的 在不同地区和不同市场，每个订单的利润额可能不同。此外，还有一个相关的截止日期 每一个订单。公司只有在截止日期前才能盈利；否则，利润为0

编写一个程序，确定订单的最佳时间表，以实现利润最大化。输入文件将 包含一个或多个测试用例。测试用例中的第一行将包含一个整数n（0 n 1000），它表示 挂起的订单数

n的值为0表示输入文件结束。 接下来的n行各包含3个正整数。第一个整数i是订单号

给定产品的所有订单号 测试用例是唯一的。第二个整数表示从现在到i的截止日期的周数 th 顺序这个 第三个整数表示如果满足i的最后期限，公司将获得的利润额 th 秩序

我所要求的是一个算法，说明我应该如何着手解决这个问题

对于输入文件中的每个测试用例，输出文件应该输出一行，报告从中获得的利润量 以最佳顺序完成订单

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

好吧，这里的问题不是Java。与其专注于语言，不如考虑算法

这个“味道”就像有一个dynamicprogramming解决方案，但从这里我可以推断你是一个初学者，所以只要订单数量合理，穷举搜索可能更容易。在详尽的搜索中，你只需列出每个可能的订单，并保存最有利可图的订单

Answer 2

有很多方法可以解决工作间的问题。从阅读维基百科条目开始，然后拿起一本关于算法设计的好书。你的教授可能会推荐一个。我怀疑动态规划是一种很好的方法，但也会有其他方法

这是一个难题，所以不要期待一个简单的答案。许多人仍在研究有效解决这个问题的方法

Answer 3

欢迎来到NP完全规划问题的精彩世界。一旦你扩大规模，就不可能在我们的有生之年找到最佳解决方案。不过这并不重要，你只需要在给定的时间内找到最好的解决方案（击败人类规划师和其他软件程序）

不要自己编写这些算法（除非你是有多年经验的专家）。使用专门解决此类问题的现成库，例如：

• Drools Planner（开源、ASL、java）

• openTS

• cpsolver

Answer 4

你的问题的假设是不完整的。需要知道你每周能做多少把椅子。也许你可以一次完成所有任务。但假设你只能做一个。解决办法是这样的

根据卡梅隆·斯金纳的聪明评论，我改变了我的答案：

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;
        }


    }


}