Mixed graph model and algorithms for parallel-machine job-shop scheduling problems. Issue 6 (19th March 2017)

• Record Type: Journal Article
• Authors: Sotskov, Yuri N.; Gholami, Omid
• Is Part Of: International journal of production research. Volume 55:Issue 6(2017)
• Page Start: 1549
• Page End: 1564
• Publication Date: 2017-03-19
• Subjects: flexible job-shop -- makespan -- mean flow time -- mixed graph; Factory management -- Periodicals; 658.57
• DOI: 10.1080/00207543.2015.1075666
• Languages: English
• ISSNs: 0020-7543

Abstract

Abstract : Heuristic algorithms are developed to solve the parallel-machine job-shop problems, where the criterion is the minimisation of the makespan, , or the sum of completion times, . The developed algorithms include sequencing and assigning stages. At the sequencing stage, the job-shop problem is solved, where job is available for processing from time . The problem is modelled by a mixed graph, where the vertices are the operations to be processed. The precedence constraints on the set are determined by the arc set . The resource constraints are determined by the edge set . 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 by an arc incident to the same vertices from the set . The resulting digraph determines a heuristic solution to the problem, where all machines are different. The digraph determines a semi-active schedule for the problem . A mixed graph model is used for solving the problem, which allows a scheduler to construct an efficient schedule via deleting some arcs from the set in the digraph or (and) via changing orientations of the arcs. Several heuristics have been developed to transform the digraph into a new digraph as a proper answer for the problem . 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.