Parallel tabu search for the cyclic job shop scheduling problem

- We consider cyclic job show problem with minimization of cycle time.
- We introduce the new method of parallel cost function calculation.
- Parallelization is not trivial due to recurrent character of formulas.
- New MIC (Intel Xeon Phi coprocessor) multiprocessor hardware is used.

In this paper, we consider a cyclic job shop problem, consisting of production of a certain set of elements at fixed intervals. Optimization of the process is reduced to a minimization of a cycle time, i.e. the time, after which the next batch of the same elements may be produced. We introduce a new parallel method for the cost function calculation. The parallelization is not trivial and cannot be done automatically by the existing compilers due to the recurrent character of formulas. Since the problem is strongly NP-hard, a heuristic algorithm was designed to solve it. Computational experiments were done in a multiprocessor environment, namely - in Intel Xeon Phi.