Study On Job Shop Scheduling Problem With Function-Same Machines

Job Shop scheduling problem (JSSP) is a class of combinatorial optimum problems with time, sequence and resource constraints. It has been proved in theory that JSSP is a NP-hard, and there is not an effective algorithm to find its optimal solution in polynomial time. Job Shop scheduling problem with function-same machines is that the machine which can process certain operation is not unique, that is there is a function-same machine set, any machine among which can process the operation. So this kind of scheduling problem broadens constraint for machine, enlarges optimal space and makes the problem intractable.The goal studied, subject to the constraints, is how to find the operational sequences to confirm the starting time of each operation and minimize the total processing time, called the make span. Firstly Job Shop scheduling problem with function-same machines is analyzed and single job is changed into a manufacturing tree, then critical path of manufacturing tree is confirmed to make operations on the critical path push stack. Operations in the stack are searched one by one until cross operation is encountered, and the manufacturing tree is divided up small segments according to these cross operations. Operations in the segment are divided up dependent operations and independent operations according to characteristic of operations, and corresponding objective function is constructed according to forward greedy rule and optimum scheduling rule. Last corresponding scheduling strategy is adopted for operations according to operation characteristic in the segment and the complementarities of function-same machines.A method of constructing virtual manufacturing tree for multi-job JSSP or dynamic JSSP is proposed to simplify these kinds of problems. Aiming at dynamic Job Shop scheduling problem, when dynamic job arrives, operations of job at the beginning should be judged to confirm operations remained, and a new virtual manufacturing tree is constructed by operations remained and dynamic arriving job, stack and queue which are used to save operations of job at the beginning are emptied, and critical path of the new manufacturing tree is confirmed and operations are scheduled according to objective function and scheduling strategy proposed. Experiment shows that the algorithm proposed has favorable complexity and can obtain better results. So the algorithm has important value both in practice and theory.