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