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

Yuri N. Sotskov and Omid Gholami

International Journal of Production Research, 2017, vol. 55, issue 6, 1549-1564

Abstract: 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.

Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://hdl.handle.net/10.1080/00207543.2015.1075666 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tprsxx:v:55:y:2017:i:6:p:1549-1564

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TPRS20

DOI: 10.1080/00207543.2015.1075666

Access Statistics for this article

International Journal of Production Research is currently edited by Professor A. Dolgui

More articles in International Journal of Production Research from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().