Mixed graph colouring for unit-time scheduling
将单位时间作业车间调度问题转化为混合图的最优着色问题，提出新的上下界、数学规划模型和禁忌搜索算法，实验验证了方法的有效性。
We consider the job shop scheduling problem with unit-time operations and the makespan criterion. This problem is reduced to finding an optimal colouring of a special class of mixed graph, where its partial graph without edges represents the union of maximal directed paths and its partial graph without arcs represents the union of maximal cliques. As the problem is known to be NP-hard, both exact and heuristic methods are proposed to solve it. This study is carried out in three steps. First, a new lower and upper bounds for the mixed chromatic number are proposed. Afterwards, a colour-indexed mathematical model using the proposed bounds is developed. Then, a tabu search using a dynamic neighbourhood structure is adapted for solving large instances. Computational experiments conducted on several modified benchmarks show the efficiency and effectiveness of the proposed resolution methods.