ALGORITMA PENJADWALAN JOB SHOP DETERMINISTIK BERBASIS MATRIKS - S. TANUMIRARDJA, YEYEN
Because of its complexity, job shop scheduling problem is categorized in NP-hard problem. Jain and Meeran [1999] conducted a comprehensive study that covered job shop scheduling techniques. Jain and Meeran [1999] also showed that research has been shifted towards heuristic techniques, because optimization has been considered not efficient. One of heuristic scheduling technique was developed by Toha and Halim [19991 using network-based algorithm. This network algorithm uses infeasible but shortest makespan as the initial solution, i.e. the solution that permits a certain condition in which theological/resource constraints cannot be satisfied. This research develops job shop heuristic scheduling algorithm by structuring network-based algorithm from Toha and Halim [1999] into matrix representation. This matrix-based scheduling algorithm results in near optimal feasible solution. Comparative study using hypothetical data proves that the matrix-based algorithm gives the same makespan, 19 time unit, as the network-based algorithm. Several trials using different initial solutions show that the quality of solution is affected by initial solution.