Scheduling assembly tasks with caterpillar precedence constraints on dedicated machines
研究了在专用机器上调度一组不可中断任务以最小化完工时间的问题，针对优先约束为毛虫图的情形提出了启发式算法和下界，并通过计算实验验证了算法性能。
In this work, we address the problem of scheduling a set of n non-preemptive tasks on m dedicated machines in order to minimise the makespan. For each task deterministic processing times and a specific processing machine are given, moreover a set of precedence constraints among the tasks are known. We present a heuristic and some lower bounds on the minimum makespan for a relevant case in manufacturing applications, namely when the precedence constraints form a caterpillar graph. A caterpillar is a directed tree consisting of a single directed path and leaf nodes each of which is incident to the directed path by exactly one incoming arc. A number of computational experiments are also performed in order to test the performance of the proposed solution algorithm.