ROUTING TWO-MACHINE FLOWSHOP PROBLEMS ON NETWORKS WITH SPECIAL STRUCTURES
研究了运输网络中两台机器需移动执行各节点作业的双机流水车间调度问题，目标是最小化完工时间并控制总移动距离，针对树和仙人掌图结构提出了O(n log n)算法。
The authors consider a version of the routing two-machine flowshop problem, where n jobs located at different nodes of a transportation network must be executed by two machines traveling between the jobs. Each job must be processed by both machines in the order, machine 1 first, machine 2 second. The goal is to minimize the makespan given that the total distance traveled must be as small as possible. Properties of the problem are discussed, and algorithms with complexity O (n log n) are developed for the problem on trees and cactuses.