Some Combinatorial optimization scheduling problems are known NP-complete, so that no algorithmic approaches can be applied to solve these problems in polynomial time.
One of these problems, MxJ job-shop scheduling problem is considered in this thesis for making the superiority comparisons among various approaches such as decomposition method, branch-and-bound method, and MWKR probabilistic dispatching method.
In the decomposition approach, we determine first the number of subset by the numbers of both jobs and machines. Next, a machine conflict matrix is a constructed with the number of machine conflicts between each job pairs, which are identified by applying the branch-and-bound technique to the original job set until the further search may get helfless.
Both branch-and-bound and MWKR probabilistic dispatching methods were tested in view of computational efficiency under a time restriction, at which the solution improvement was decelerated in the decomposition approach.
From the result of this analysis procedure, it was found that the effect of the decomposition approach gets decreased due to the heterogeneity of pairwise job routings while remarkable in effect for flow-shop patterns independent of the machine conflict matrix information due to the homogeneity of routings.
Among the approaches, the MWKR probabilistic dispatching approach was identified to give the best schedules from MxJ job-shop problems having the heterogeneity in routing, while in the decomposition approach, good schedules could not be found because of the unnecessary machine idle times between pairwise successive subsets.
As a further research subject, it may be noted how to use the completion times of machines in the preceding subset for scheduling the operations of the following job subsets.
