Mixed graph model and algorithms for parallel-machine job-shop scheduling problems

Heuristic algorithms are developed to solve the parallel-machine job-shop problems FJ|ri|Φ$ FJ|r_i|\Phi $, where the criterion Φ$ \Phi $ is the minimisation of the makespan, Φ=Cmax$ \Phi =C_{\max } $, or the sum of completion times, Φ=∑Ci$ \Phi =\sum C_i $. The developed algorithms include sequencing and assigning stages. At the sequencing stage, the job-shop problem J|ri|Φ$ J|r_i|\Phi $ is solved, where job Ji∈J$ J_i \in \mathcal{J} $ is available for processing from time ri$ r_i $. The problem J|ri|Φ$ J|r_i|\Phi $ is modelled by a mixed graph G=(O,A,E)$ G=(\mathcal{O}, A, E) $, where the vertices O$ \mathcal{O} $ are the operations to be processed. The precedence constraints on the set O$ \mathcal{O} $ are determined by the arc set A$ A $. The resource constraints are determined by the edge set E$ E $. In order to resolve a conflict arising between two operations processed on the same machine, the algorithm should substitute a conflict edge from the set E$ E $ by an arc incident to the same vertices from the set O$ \mathcal{O} $. The resulting digraph Gt=(O,A⋃At,∅)$ G_t=(\mathcal{O}, A \bigcup A_t, \varnothing ) $ determines a heuristic solution to the problem J|ri|Φ$ J|r_i|\Phi $, where all machines are different. The digraph Gt$ G_t $ determines a semi-active schedule for the problem FJ|ri|Φ$ FJ|r_i|\Phi $. A mixed graph model is used for solving the problem FJ|ri|Φ$ FJ|r_i|\Phi $, which allows a scheduler to construct an efficient schedule via deleting some arcs from the set At$ A_t $ in the digraph Gt$ G_t $ or (and) via changing orientations of the arcs. Several heuristics have been developed to transform the digraph Gt$ G_t $ into a new digraph as a proper answer for the problem FJ|ri|Φ$ FJ|r_i|\Phi $. The developed algorithms have been tested on the benchmark instances. It is demonstrated how these algorithms may be used for solving a train timetabling problem.