Two Procedures For Solving Job Shop Scheduling Problem Based On Decomposition Strategy

Job shop scheduling problem (JSSP) is considered one of the most difficult combination optimization problems, his complexity embodies the computational complexity and the uncertainty of dynamic environments. People can't find precise algorithms for the problems, so heuristic algorithms are very popular algorithms solving these problems.Decomposition strategy is one of heuristic algorithms which can reduce the complexity effectively. It cuts the problems for two parts, the first one we consider the restriction relations between the sub-problems, while the second one we consider the relations the sub-problems themselves, we solve the sub-problems in the second part, then we consider the first part to ensure the result we got from the second part is feasible.In this paper, we introduce two algorithms for a topical Job shop problems: one of them is a rolling horizon procedure, then we give its improved algorithm; another is a tabu search based on shifting bottleneck(SB) algorithm. Summarily, the main work of this dissertation lies in these aspects as follows:(?) Introduce the classes and the characteristic of scheduling problems, and their current research methods and the defects of the methods and their ways to solve the defects.(?) To a rolling horizon procedure, we give its improved algorithm, finally give their computational results respective, because of the complexity of the problems we have many parameters, first we consider the effect for each parameter change to the result, then choose a better value for each parameter, finally we use the values compare the algorithm with its improved algorithm.(?) Bring forward a tabu search based on SB algorithm, we got a initial result by SB algorithm, then used local search method constantly to get a better result, we re-optimize the result once we get a better result with SB algorithm, finally we got a result we can accepted.