分批排序问题必威体育精装版进展张玉忠yuzhongrzeyoucomcullencao.pdfVIP

分批排序问题 必威体育精装版进展 张玉忠，曹志刚 ( yuzhongrz@, cullencao@ ) 曲阜师范大学运筹与管理学院, 日照, 山东, 276826 报告人：曹志刚 2005年8月24 日，上海第二工业大学 应用背景  分批排序或分批调度(batch scheduling)是兴起于 90年代初的一类应用背景极强的优化问题.主要 产生于大规模的现代化生产流水作业线如：  半导体生产  航空工业(1997, 2001, Zee, D.J. Vander et al)  钢铁铸造(2000, M. Mathirajan)  甚至制鞋业(1996, M.P. Fanti et al)  其中半导体生产流水作业线, 确切来说集成电路 芯片(IC chips)生产流水作业线, 是被研究和应用 最广泛、最深刻的一个领域. 应用背景（续）  集成电路芯片的生产分为四个阶段：晶片 生产(wafer fabrication)、晶片探测(wafer probe)、装配(assembly)以及最后的测试 (final testing),每一个阶段都有分批排序的 应用。  三种主要模型(1995,Webster and Baker):  parallel batch  serial batch及  批加工时间为常数的模型 应用背景（续）  本文所介绍的分批排序模型特指p-batch, 亦即所 谓的burn-in model, 它来源于最有意义的测试过 程.  在芯片测试时,其中一个过程是将芯片放入烤箱 烘烤.每个芯片都有一个预定的烘烤时间,经受住 这段时间烘烤的芯片被视作合格产品.烤箱有一 个固定的容积B. 烘烤过程是不允许被打断的.每 个芯片预定的烘烤时间可能是不同的,为了保证 产品质量,同一烤箱内芯片的实际烘烤时间为其 中预定时间最长的. 问题研究的意义  由于相对与其它过程来说,烘烤的用时是很 长的(大约120:5),成为芯片生产的一个瓶颈. 随着半导体工业的飞速发展以及竞争的不 断加剧,如何有效地利用(厂家和顾客的)时 间这一宝贵资源显得越发重要,因而用组合 优化的工具来研究此问题是很有意义的. （1992，Lee, Uzsoy and Martin-Vega ） 问题的具体描述  有n个工件 {J ,J ,,J } 要在一台(或多台)机器上加 1 2 n 工, 每个工件 有工时( processing time ) p 、 J j j 就绪时间( release time ) r 和工期(due date) d j j (有时候可能工件同时到达或/和没有工期).至多B 个工件可分作一批同时加工,批加工时间为此批 中最大工件的加工时间,工件 的完工时间 C J j j (completion time) 为所在批的完工时间.  加工过程不允许中断  问题是如何合理地分批及排序，使得给定的目标 函数最小 问题的具体描述（续）  研究的的目标函数一般是每个工件完工时间的非 减函数f max 或 f j