Mixed integer linear programs and tabu search approach to solve mixed graph coloring for unit-time job shop scheduling
Authors:
- 1 August 2015
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 21618070,p. 1177-1181
Abstract
Graph coloring is one of the most studied combinatorial optimization problems that can be used to model several practical problems. This paper develops a reduction of job shop scheduling problem with unit-time operations to mixed graph coloring. In this study, a methodology based on Mixed Integer Linear Programming and tabu search (TS) algorithm are proposed for solving mixed graph coloring. The performances of the proposed methods are evaluated through several adapted Benchmarks.Keywords
This publication has 14 references indexed in Scilit:
- Partitioning of ECE schemes components based on modified graph coloring algorithm2014
- Evaluation of mixed integer programming formulations for non-preemptive parallel machine scheduling problemsComputers & Industrial Engineering, 2010
- Adaptive automated construction of hybrid heuristics for exam timetabling and graph colouring problemsEuropean Journal of Operational Research, 2009
- A note on mixed tree coloringInformation Processing Letters, 2008
- On two coloring problems in mixed graphsEuropean Journal of Combinatorics, 2008
- Coloring some classes of mixed graphsDiscrete Applied Mathematics, 2007
- Using mixed graph coloring to minimize total completion time in job shop schedulingApplied Mathematics and Computation, 2006
- On a graph-theoretical model for cyclic register allocationDiscrete Applied Mathematics, 1999
- Mixed graph coloringsMathematical Methods of Operations Research, 1997
- Computational Complexity of Discrete Optimization Problems1979