Zurück zu den Preprints des Jahres 2016


2016-02

Genetic algorithms for hybrid job-shop problems with minimizing the makespan and mean flow time

by Gholami, O.; Sotskov, Y. N.; Werner, F..


Series: 2016-02, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
We address a generalization of the classical job-shop problem which is
called a hybrid job-shop problem. The criteria under consideration are the minimization of the makespan and mean flow time. In the hybrid job-shop, machines of type k are available for processing the specific subset O^k of the given operations. Each set O^k may be partitioned into subsets for their processing on the machines of type k.
Solving the hybrid job-shop problem implies the solution of two subproblems: an assignment of all operations from the set O^k
to the machines of type k and finding optimal sequences of the operations for their processing on each machine.
In this paper, a genetic algorithm is developed to solve these two subproblems simultaneously. For solving the subproblems, a special chromosome is used in the genetic algorithm based on a mixed graph model. Computational results for the benchmark instances show that the proposed genetic algorithm is rather efficient for both criteria.

Keywords:
Scheduling, Hybrid job-shop, Makespan, Mean flow time, Genetic algorithm