随着顾客需求的日益多样化,越来越多的制造企业开始采用混流组装线组织生产,尤其在汽车、家电等制造行业,混流组装线已得到广泛的应用。混流组装线是一种柔性生产系统,其特点是在一条组装线上同时组装结构相似且工艺、尺寸接近的不同品种产品,可以在不增加库存的情况下,实现大规模定制化生产,从而快速响应市场的变化。优化混流组装线需要解决两个主要问题:一是线平衡问题,即将所有组装作业任务合理地分配到组装线上各个工位中;二是排产问题,即确定不同品种产品投入组装线的顺序。本文研究随机作业时间下混流组装线的最优排产问题,考虑两种目标:最小化总期望超载时间和最小化总超载概率。论文假设线平衡已经完成,发生超载时不停线,由辅助工人在工位之间的缓冲区域完成超载的作业量。论文首先以文献[21]建立的混流组装线模型为基础,对其进行推广和扩展得到随机作业时间下多工位混流组装线期望超载时间、期望空闲时间、超载概率和空闲概率的近似计算方法。然后,针对两种目标函数分别设计出包括模拟退火算法和启发式算法在内的多种排产优化算法。具体算例表明,模拟退火算法改进解的速度较慢,并且对参数较为敏感,算法稳定性较差。研究还发现,基于问题背景知识的邻近解产生机制并不一定能提高模拟退火算法的改进幅度和收敛速度。重点研究了两类启发式算法:贪婪式和交替式。每一类算法根据选择标准的不同又可分为三种。针对每种启发式算法,分别对不同问题规模、作业时间分布和变动系数下的大量算例进行考察。结果显示,某些算法解的质量很好也很稳定,即应用于小规模问题时可直接得到最优解或者启发值与最优值很接近,而应用于大规模问题时启发值与上下界的相对位置分布很集中也很靠前。因此,在解决实际问题(往往规模较大)时,可以通过启发值与上下界的相对位置关系大体判断启发解的好坏。另外,对于不同的作业时间分布和变动系数,各种启发式算法的表现都很稳定,优化效果几乎不受作业时间分布的影响,受变动系数影响也很小,说明算法具有较高的鲁棒性。最后针对启发解的进一步优化设计了简单的算法,利用启发解的特性对其做局部调整。大量算例表明该算法对某些启发式算法的解有明显的改进效果。因此,在实际应用时,可分别用几种效果较好的启发式算法得到启发解并对其应用改进算法,然后从中选择最好的改进解作为排产。对大量算例详细的分析表明,针对每一种目标函数设计的六种启发式算法均具有较好的鲁棒性,并且其中几种算法效果很好,具有实际应用价值。