工件具有入树约束的同类机排序问题的分支定界算法  

A branch-and-bound algorithm for uniform machines scheduling problem with intree precedence constraints

作　　者：胡珈铭 苗翠霞[1] 邹娟[1] HU Jiaming;MIAO Cuixia;ZOU Juan(School of Mathematical Sciences,Qufu Normal University,273165,Qufu,Shandong,PRC)

机构地区：[1]曲阜师范大学数学科学学院

出　　处：《曲阜师范大学学报（自然科学版）》2020年第1期4-10,共7页Journal of Qufu Normal University(Natural Science)

基　　金：国家自然科学基金(11801310,61873144);山东省自然科学基金(ZR2017MA031);山东省研究生教改项目(SDYY17139)

摘　　要：研究具有入树约束的两台同类机排序问题,工件具有不同的到达时间且具有单位的加工时间,目标为极小化最大完工时间.对于该NP-难问题,首先设计了一个分支定界算法并证明了算法的最优性.然后通过一个具体算例,详细验证了算法的执行过程.This paper considers the 2-uniform-parallel-machine scheduling problem with in-tree precedence constraints,in which jobs have different release dates and unit processing time.The objective is to minimize the makespan.For the NP-hard problem,this paper first designs a branch-and-bound algorithm and prove that the algorithm is optimal.Then give an example to process the branch-and-bound algorithm.

关 键 词：同类机排序 入树约束 分支定界算法 

分 类 号：O224[理学—运筹学与控制论]