[發(fā)明專利]基于產(chǎn)品族排序?qū)崿F(xiàn)最小總完工時(shí)間的批調(diào)度方法

有效

• 申請(qǐng)?zhí)枺?/td>: 201310022574.4
• 申請(qǐng)日: 2013-01-22
• 公開（公告）號(hào): CN103136631A
• 公開（公告）日: 2013-06-05
• 發(fā)明（設(shè)計(jì)）人: 賈文友;劉莉;趙雪松;賈昊瑞;劉濤
• 申請(qǐng)（專利權(quán)）人: 安徽工程大學(xué)
• 主分類號(hào): G06Q10/06
• 分類號(hào): G06Q10/06
• 代理公司: 暫無信息
• 代理人: 暫無信息

技術(shù)領(lǐng)域

本發(fā)明涉及重入生產(chǎn)線的批處理機(jī)調(diào)度，尤其涉及一種用于可重入生產(chǎn)線的基于產(chǎn)品族排序?qū)崿F(xiàn)最小總完工時(shí)間目標(biāo)的批調(diào)度方法。?

背景技術(shù)

可重入生產(chǎn)線(re-entrant)是在上世紀(jì)80年代末90年代初，由美國Kumar教授針對(duì)半導(dǎo)體芯片、膠卷等行業(yè)的生產(chǎn)特點(diǎn)而提出的概念，并將其列為有別于流水作業(yè)（Flow-shop）和異序作業(yè)（Job-shop）的第三類重入型生產(chǎn)線。所謂的重入是指未完成加工的產(chǎn)品沿著生產(chǎn)線進(jìn)行加工時(shí)，有可能數(shù)次在同一個(gè)工作臺(tái)被加工，每次的加工時(shí)的工件狀態(tài)不同，每個(gè)產(chǎn)品狀態(tài)稱為一個(gè)產(chǎn)品族（family）（注：產(chǎn)品族概念不同于產(chǎn)品類型，假設(shè)產(chǎn)品類型的數(shù)量為N，產(chǎn)品需要重入批處理機(jī)的次數(shù)為K，則產(chǎn)品族的數(shù)量F=N*K）。批加工是指在不超過工作臺(tái)的最大加工能力時(shí)，一次可以加工多個(gè)未完成加工的產(chǎn)品，每次實(shí)際加工多個(gè)未完成加工產(chǎn)品稱為一個(gè)批（Batch）。如，在半導(dǎo)體芯片生產(chǎn)線前段的爐管區(qū)，該加工機(jī)臺(tái)屬于可多重入的批處理機(jī)，具有加工時(shí)間長(zhǎng)，是生產(chǎn)系統(tǒng)的瓶頸機(jī)臺(tái)，需要多層重入性加工和設(shè)備價(jià)格更昂貴等特性。為了提高爐管區(qū)的批調(diào)度效率，有多種調(diào)度目標(biāo)可以衡量，其中最小總完工時(shí)間是一種衡量目標(biāo)。以最小總完工時(shí)間為衡量目標(biāo)的多產(chǎn)品族不能混合組批（incompatible?job?families）、產(chǎn)品具有不同到達(dá)時(shí)間（dynamic?job?arrivals）的可重入生產(chǎn)線的批處理機(jī)（re-entrant?batch?processing?machine）的合理調(diào)度控制是批調(diào)度與控制研究是的一個(gè)非多項(xiàng)式的難問題（NP-hard），它制約著半導(dǎo)體生產(chǎn)系統(tǒng)的整體績(jī)效，開展以最小總完工時(shí)間為調(diào)度目標(biāo)的批處理機(jī)的合理調(diào)度控制研究對(duì)改善半導(dǎo)體芯片生產(chǎn)線的性能具有重要意義，一直是學(xué)術(shù)界與應(yīng)用界的研究熱點(diǎn)之一。?

目前，從我國乃至各國的半導(dǎo)體芯片生產(chǎn)的情況看，設(shè)備更新和產(chǎn)品升級(jí)的速度非常快，生產(chǎn)線的調(diào)度方法研究遠(yuǎn)遠(yuǎn)跟不上其實(shí)際發(fā)展的需要。在半導(dǎo)體可重入生產(chǎn)線上，以最小總完工時(shí)間（）為調(diào)度目標(biāo)的批處理機(jī)生產(chǎn)過程調(diào)度中，常規(guī)調(diào)度方法是：當(dāng)批處理機(jī)空閑可用時(shí)，對(duì)批處理機(jī)前的緩沖器里的不同階段產(chǎn)品族的工件按一定規(guī)則組批，所組的批再按以最小總完工時(shí)間為調(diào)度目標(biāo)的優(yōu)化排序和調(diào)度排序中優(yōu)先級(jí)最高的批分配到空閑可用的批處理機(jī)。但是隨著批處理機(jī)前的緩沖器里的工件數(shù)量的不斷增加，所組的批數(shù)量也相應(yīng)增加，致使以最小總完工時(shí)間為目標(biāo)的調(diào)度問題的規(guī)模增大，求解問題的難度增加，使得求解時(shí)間變長(zhǎng)而影響批調(diào)度算法的時(shí)間復(fù)雜度和解的精度。?

發(fā)明內(nèi)容

本發(fā)明針對(duì)上述現(xiàn)有技術(shù)中存在的技術(shù)問題，提供一種用于可重入生產(chǎn)線的基于產(chǎn)品族排序?qū)崿F(xiàn)最小總完工時(shí)間的批調(diào)度方法，克服了具有可重入特性的半導(dǎo)體芯片生產(chǎn)線的批處理機(jī)動(dòng)態(tài)實(shí)時(shí)調(diào)度過程中，隨著批處理機(jī)前的緩沖器里的工件數(shù)量的不斷增加，所組的批數(shù)量也相應(yīng)增加，致使以最小總完工時(shí)間為目標(biāo)調(diào)度問題的規(guī)模增大，求解問題的難度增加，使得求解時(shí)間變長(zhǎng)而影響批調(diào)度算法的時(shí)間復(fù)雜度和解的精度。?

本發(fā)明具體解決其技術(shù)問題所采用的技術(shù)解決方案是：?