求解作业车间批量流问题的变邻域搜索算法

Variable Neighborhood Search for Lot Streaming Problem in Job Shop

对具有等子批和空闲约束的作业车间批量流问题进行了研究,提出一种有效变邻域搜索(VNS)算法以最小化延迟和提前惩罚总和,该算法利用双串表示法描述问题的解.为了适应问题的特点,几个初始解独立进化以改善VNS的探索能力,对批调度采用一个变邻域结构,而对批量流条件则根据一个较小的概率进行调整.将VNS应用于一些实例,计算结果验证了VNS的优异性能.

This paper addresses the lot streaming（LS）problem in job shop with equal sublots and idling constraint,in which each lot is regarded as an individual job.The objective is to minimize total penalties of tardiness and earliness.An effective variable neighborhood search（VNS）is proposed,in which two-string representation is used to indicate the solution of the problem.In VNS,several initial solutions are evolved independently to improve exploration ability,to effectively adapt the features of the problem,a variable neighborhood structure is used for lot scheduling and the LS conditions are adjusted according to a small probability.The proposed VNS is finally applied to some instances and computational results validate the promising advantage of VNS.