车间调度是制造业生产的最基本的问题。该问题描述为:设有m台加工机器和n个加工工件,每个加工工件有m个加工工序,每个工序的在不同机器上的加工时间已知,确定每个工序机器上的加工顺序,使得某个目标最小。加工顺序的结果可用甘特图表示,试编写程序建立甘特图,并求出下述指标:
1) 最后一个工序的完工时间;
2)任意一个工序的开始加工时间和结束时间;
3)任意一个工序在哪台机器上加工;
4)任意一台机器上加工的工序集合;
工件的加工必须满足下述约束:
1)同一工件只有在前序工序结束后才能进行后一工序的加工;
2)机器不能同时加工两个不同的工序;
3)一个工序在同一机器上只能加工一次;
4)工序一旦加工就不能被中断。