d017 Playing in the PTC Children's Amusement

Two-machine Flowshop Scheduling(雙機器流水作業排程)

這個問題的激發是由一個在運作研究領域中，流水作業排程問題的特別例子，在限制區域的數量為2情況，有一個效率的演算法來找出最佳解答。（當區域的數量大於2的時候，這個問題被證明為是一個NP-hard問題。)這個效率的解決方法被稱作Johnsons rule. 最佳的班級區域拜訪順序會在這之後決定。

Johnson's Rule

步驟一、切割全部班級為兩個集合，一個集合Ⅰ包含所有的班級i為p(i,1) < p(i,2)和集合Ⅱ包含所有班級j為p(j,1) > p(j,2)，而班級k為p(k,1) = p(k,2)者可以放在任意一個集合。

步驟二、班級在集合Ⅰ者以p(i,1)遞增的順序出發，班級在集合Ⅱ跟隨在後以p(j,2)遞減的順序。

※註：p(班級、區域)為該班級在該區域所花的時間

import java.util.*;
import java.util.Scanner;

public class JAVA {

    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int caseCount = 0;
        LinkedList<Integer> totalTime = new LinkedList<Integer>();
        
        while(sc.hasNext()) {
            
            // get how many classes
            int classes = sc.nextInt(); // classes amount
            if(classes <= 0)
                break;
            /*
             *  timeList[classes][0] = r1 time
             *  timeList[classes][1] = r2 time
             */
            // initialize time list
            int[][] timeList = new int[classes][2];
            
            // get time input
            for(int i = 0; i < classes; i++) {
                timeList[i][0] = sc.nextInt();
                timeList[i][1] = sc.nextInt();
            }
            
            // step1. put them in set I and II respectively
            LinkedList<Integer> setI = new LinkedList<Integer>();
            LinkedList<Integer> setII = new LinkedList<Integer>();
            
            for(int i = 0; i < timeList.length; i++) {
                // r1 < r2, put into set I, in r1-increase order
                if(timeList[i][0] <= timeList[i][1]) {
                    // setI is empty, just insert
                    if(setI.isEmpty())
                        setI.add(i);
                        
                    // check if the first r1-time in list 
                    // is smaller than p(i,r1)?
                    else {
                        boolean addFlag = false;
                        //int r1 = timeList[i][0];
                        for(int j = 0; j < setI.size(); j++) {
                            //int r1_In_List = timeList[setI.get(j)][0];
                            if(timeList[i][0] <= timeList[setI.get(j)][0]) {
                                setI.add(j,i);
                                addFlag = true;
                                break;
                            }
                        }
                        if(!addFlag)
                            setI.addLast(i);
                    }
                } // r1 < r2, put into set II, in r2-decrease order
                else {
                    if(setII.isEmpty())
                        setII.add(i);
                    else {
                        boolean addFlag = false;
                        for(int j = 0; j < setII.size(); j++) {
                            if(timeList[i][1] <= timeList[setII.get(j)][1]) {
                                setII.add(j,i);
                                addFlag = true;
                                break;
                            }
                        }
                        if(!addFlag)
                            setII.addLast(i);
                    }
                }
            }
            
            // combine the set and make the correct sequence
            LinkedList<Integer> sequence = new LinkedList<Integer>();
            
            while(!setI.isEmpty())
                sequence.add(setI.poll());
            
            while(!setII.isEmpty())
                sequence.add(setII.pollLast());
            
            // release memory
            setI = null;
            setII = null;
            
            // step2. start counting time
            int r1Time = 0;
            int r2Time = 0;
            
            r1Time += timeList[sequence.getFirst()][0]; // must be add
            r2Time += timeList[sequence.getFirst()][1] + r1Time;
            
            for(int i = 1; i < sequence.size(); i++) {
                // move i th class to r1
                r1Time += timeList[sequence.get(i)][0];
                
                // i th class played r1 over
                // try to query r2 isEmpty?
                // if r2Time > r1Time mean r2 is still busying.
                if(r1Time > r2Time) {
                    r2Time = r1Time;
                } 
                else  
                {
                    // r2 is available now!!
                }
                // move i th class to r2
                r2Time += timeList[sequence.get(i)][1];
            }
            
            totalTime.add(r2Time);
        }
        
        for(int i = 1; i < totalTime.size() + 1; i++) {
            System.out.println(i + " " + totalTime.get(i-1));
        }
    }

}

這是沒有debug版的較乾淨程式碼，我在寫的時候還另外做了debug版，看哪天再release出來.