排程问题的“冲突回避概念”建模 -- 累死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 to t[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） where n is an integer bigM is a number T is a set t[i] is a variable of nonnegative number | i=1,...,n u[i][j] is a variable of binary | i=1,...,n; j=1,...,n; i<>j data_relation n=_$(T) bigM =sum{i=1,...,n}T[i] data T={13 15 21 9 10 12 5 14 11 20}