混合流程生产系统基于提前与拖期的作业排序混合流程生产系统中生产的排序经常需要考虑提前/拖期（ETT）问题，对提前/拖期问题的优化可以提高生产排序的性能指标。本章拟解决的是基于提询/拖期的作业排序问题，提出采用簇分配算法解决该问题。文章对E/T问题进行了槪述，阐述了聚类算法的原理和应用，然后把聚类算法应用到提前/拖期的作业排序中，给出了用簇分配算法解决该问题的启发式算法，最后通过示例验证，得出了方法的可行性。6.1混合流程系统中的提前/拖期问题在过去的几十年，准时制（JIT）的思想对我们的生产计划产生了很重要的影响,在准时制思想的影响下，客户不愿意接受提前或延期的货物，最常用的计划目标演变成最小化完成时间与截止日期的偏差，一个比较著名的有关准时制计划的模型是提前拖期计划模型（E/T模型）。6.1.1提前/拖期计划的特点一般的ETT问题是不考虑批量的。木文考虑的问题放松了在批量问题中不延期的假设，同时把昕问题延伸到了批量和计划问题，称为提前/延期批量计划问题（ETLS）简单地说就是确定生产的批量和计划，使得总的装设成本，存储成本和延期成本最小化。本章使用离散批最计划问题（DLSP）构建ETLS模型。DLSP问题假定时间区域是不连续的,需求是随时间变化的，是一个适合短期工作计划即工序排序的计划问题。DLSP的研究引起了很多学者的关注〔“文献［136］提出了分支定界算法，使用拉格朗日松弛法解决了相关装设成本的计划，文献［137］对文献［136］的工作进行了进一步研究，考虑了装设次数的问题。文献［138］考虑了相关装设成本的问题，但足没有把它融入模型中进行考虑，文献［139］研究了装设成本和装设次数的问题。本章提出采用簇分配的算法很好地解决了基于提前/拖期的作业排序问题。本章拟解决的提前/拖期的作业排序问题的特点如下:在计划区域开始的时候有n个订单在单个机器上等待着进行加工；每一个订单是一种类型的产品，不同的订单加工的可能是不同的或相同类型的产每-个订单有自己的截止日期，存储成本和延期成本：为了满足订单的需求，产品必须要进行分批加工。产品批量的定义为在连续的时间段内加工同一种产品的批次；每一个订单在一个时间段内发货。如果产品的完成时间早于或等于截止日期，那么发货日期等于截止口期。否则订单的发货日期等于产品的完成日期。6.1.2提前/拖期的生产调度模型一个典型的带有提前、拖期和完工时间罚值的制造系统的生产调度利计划问题(ETCPSP)有N种产品，M个生产过程。通常在一个生产计划和调度时期T上，很难满足顾客在任何时间的需要。为克服资源短缺和资源过剩问题，允许提前和拖期生产。然而当考虑占有资金和短缺补偿资金时，不希望岀现有提前和拖期的生产情况,实际中还需同时考虑直接与产品交货期相联系的产品完工时间，因此，对上述问题的优化原则是最小化总的提前、拖期和完工时间的罚值，在调度期内找到最优的生产调度并使制造过程的容量限制得到满足。建立模型时有以下假设：(1)将调度期T分为大小相等的时段，同此相关的参数如处理时间、完工时间等都由该时段的整数倍来确定；(2)各个产品的处理时间是确定的：(3)不允许中断，即一旦一个产品的操作开始之后，该产品的另一个操作必须在其完成之后才能进行；(4)所有产品的到达时间相同并假定为零。ETCPSP问题可以用离散化的形式表示为如下的规划问题卩40),NTNMmin=+兀尸61)p>■!M/■!s.t勺伙)j=12・・・.Mk=l,2,••・・・,T(6-2)