⽣产计划与管理——单机作业排程极⼩化平均流程时间——四种线性规划模型知识点 排程问题的“冲突回避概念”建模 -- 累死CPLEX的模型1 排程问题的“图(论)概念”建模排程问题的“排序概念”建模排程问题的“P-算法”建模 -- 秒解模型单机作业排程/极⼩化平均流程时间单机作业排程是指将n个作业依次地在⼀台机器上完成，不同作业不能同时占⽤这台机器，且⼀旦机器被分配给该作业，则该机器必须完成该作业才能交付下⼀个作业使⽤。
假设作业i的作业时间为T[i], 且其开始作业时间为 t[i] 则其流程时间(即完成时间）为 t[i]+T[i]。
极⼩化平均流程时间，即⽬标为： min sum{i=1,...,n}(T[i]+t[i])/n数据：假设有10个作业，其作业时间分别为 13 15 21 9 10 12 5 14 11 20模型1——“冲突回避”模型考虑任务i,j且i<>j（即i不等于j), 则有两种情况：或者i作业先于j作业加⼯或者反之。
如果是前者，则 t[j] >= t[i] + T[i]如果是后者，则 t[i] >= t[j] +T[j]两个约束显然是互斥的，不能同时成⽴。
因此必须⽤或关系将他们加⼊模型。
加⼊或关系的⽅法是引进0-1变量u[i][j]，如果u[i][j]=1前⼀个约束成⽴，否则如果u[i][j]=0后⼀个约束成⽴。
此时配合⼀个⾜够⼤的数bigM,则可把上⾯两个或约束表⽰成： t[j]-t[i] >= T[i] - (1 - u[i][j])bigM //（1） t[i]-t[j] >= T[j] - u[i][j]bigM // （2） 完整模型：min sum{i=1,...,n}(T[i]+t[i])subject tot[j]-t[i] >= T[i] - (1 - u[i][j])bigM | i=1,...,n; j=1,...,n; i<>j //（1）t[i]-t[j] >= T[j] - u[i][j]bigM | i=1,...,n; j=1,...,n; i<>j //（2）wheren is an integerbigM is a numberT is a sett[i] is a variable of nonnegative number | i=1,...,nu[i][j] is a variable of binary | i=1,...,n; j=1,...,n; i<>jdata_relationn=_$(T)bigM =sum{i=1,...,n}T[i]dataT={13 15 21 9 10 12 5 14 11 20}模型2——“图(论)概念”模型把作业看成是图的节点，作业之间的直接衔接关系看成是边。
