An efficient combination of dispatch rules for job-shop scheduling problem

Toshiki Kawai, Yasutaka Fujimoto

2005 · 10 citations · 5 references

DOIFull text

Open access

Concepts

Abstract

This paper presents new combination of dispatch scheduling for job shop scheduling problem. The job shop scheduling problem is one of the NP hard optimization problems, and it is difficult to obtain the exact optimal solution. Scheduling methods based on the dispatch rule are a set of efficient approximate methods. In this paper, by combining several dispatch rules, we have proposed three new rules. The first rule is the rule that combines two simple dispatch rules which are often adopted in actual production systems. The proposed rule gives better result than that of any single dispatch rule. The second rule is the rule that keeps balance of remaining load of all machines. In this rule, the weight is decided in early stage of the schedule. It gives good solutions with high probability. The third rule is the rule that predetermines the mixing ratio, which accompanies a sequence of operations. This rule often gives better results than any other dispatch rules.

References

5