Job Scheduling Problem in Java

Question

I am writing a problem to solve Job schedules but I am having a hard time understanding how.

The Wood Shop has a backlog of orders for its world famous rocking chair (1 chair per order). There are several steps involved in making a handmade Baber Rocking chair (eg. cutting wood pieces, assembly, sanding, applying a stain, and applying varnish).

The total time required to make a chair is 1 week. However, since the chairs are sold in different regions and various markets, the amount of profit for each order may differ. In addition, there is a deadline associated with each order. The company will only earn a profit if they meet the deadline; otherwise, the profit is 0.

Write a program that will determine an optimal schedule for the orders that will maximize profit. The input file will contain one or more test cases. The first line in a test case will contain an integer, n (0 n 1000), that represents the number of orders that are pending.

A value of 0 for n indicates the end of the input file. The next n lines contain 3 positive integers each. The first integer, i, is an order number.

All order numbers for a given test case are unique. The second integer represents the number of weeks from now until the deadline for i th order. The third integer represents the amount of profit that the company will earn if the deadline is met for the i th order.

What I am asking for is an algorithm of how I should go about solving this problem.

For each test case in the input file, the output file should output a line that reports the amount of profit that results from completing the orders in an optimal order.

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

Welcome to the wonderful world of NP complete planning problems. Once you scale out, it's impossible to find the optimal solution in our lifetimes. That doesn't matter though, you just have to find the best solution in the given time (beating human planners and other software programs).

Don't write these algorithms yourself (unless you're an expert with years of experience). Use an off the shelf library which specialize in these kind of problems, such as:

• Drools Planner (open source, ASL, java)

• openTS

• cpsolver

Answer 2

The postulate of your problem is incomplete. It is required to know ho many chairs can you make per week. Maybe you can make all at once. But let's assume you can make only one. The solution is like this.

based on the very smart comments of Cameron Skinner I change my answer to this:

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

There are a bunch of ways to solve the job shop problem. Start by reading the wikipedia entry, then pick up a good book on algorithm design. Your professor can probably recommend one. I suspect dynamic programming would be a good way to approach this but there will be other approaches too.

This is a difficult problem so don't expect an easy answer. Many people are still researching ways to solve this problem efficiently.

Answer 4

Okay, Java is not the problem here. Instead of concentrating on the language, think about the algorithm.

This "tastes" like something where there is a dynamic programming solution, but from this I'm kind of inferring you're a beginner, so an exhaustive search is probably easier as long as the number of orders is reasonable. In an exhaustive search, you'd simply lay out each possible order and save the most profitable one.