Efficient algorithm to find makespan in manufacturing systems under multiple scheduling perturbations
提出结构扰动算法(SPA)，通过将制造系统建模为有向无环图，在一次遍历中处理多条边的增删，加速计算调度方案的完工时间，适用于各类可描述为扰动有向无环图的问题。
Manufacturing scheduling improvement heuristics iterate over trial schedules to determine a satisfactory schedule. During each iteration, a performance measure (e.g. makespan) is calculated. The paper presents an efficient algorithm, Structural Perturbation Algorithm (SPA), that accelerates the calculation of the makespan. This means all scheduling improvement heuristics using SPA to calculate makespan for each trial schedule will run faster. To achieve this goal, the manufacturing system is modelled by a Directed Acyclic Graph (DAG). Schedule trials can be described as a perturbed DAG where multiple edges are added and deleted. The major contribution of this research is that SPA can handle multiple edge deletions/additions with a single pass which makes it more efficient in terms of time complexity than current approaches. SPA accomplishes this by partitioning the nodes into three regions based on the locations of the added and deleted edges. Then, SPA updates the length of the affected nodes in each region. The application of SPA is not limited to the scheduling problem. The SPA can be applied in other fields as long as the problem can be described as a Perturbed DAG.