Java中的作业调度问题

Question

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

The Wood Shop 的世界著名摇椅积压了订单（每个订单 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

有很多方法可以解决车间问题。首先阅读维基百科条目，然后拿起一本关于算法设计的好书。你的教授可能会推荐一个。我怀疑动态编程将是解决这个问题的好方法，但也会有其他方法。

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

Answer 2

你的问题的假设是不完整的。需要知道您每周可以制作多少张椅子。也许你可以一次性全部做好。但我们假设你只能制作一个。解决办法是这样的。

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

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 3

欢迎来到 NP 完整规划问题的奇妙世界。一旦横向扩展，我们一生中就不可能找到最佳解决方案。但这并不重要，你只需要在给定时间内找到最佳解决方案（击败人类规划者和其他软件程序）。

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

• Drools Planner< /a>（开源、ASL、java）

• openTS

• cpsolver

Answer 4

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

这“尝起来”就像有一个动态 编程解决方案，但据此我推断您是初学者，因此详尽的搜索可能更容易只要订单数量合理。在详尽的搜索中，您只需列出每个可能的订单并保存最有利可图的订单。