[發(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
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于產(chǎn)品族排序?qū)崿F(xiàn)最小總完工時(shí)間的批調(diào)度方法，其特征在于，目標(biāo)函數(shù)是所調(diào)度批的最小總完工時(shí)間，通過模型分解，先以可重入批處理機(jī)前的緩沖器里不同產(chǎn)品族為研究對(duì)象，再以優(yōu)先權(quán)最高的產(chǎn)品族中工件為研究對(duì)象，利用產(chǎn)品族加權(quán)最短加工時(shí)間優(yōu)先規(guī)則，最大重入次數(shù)優(yōu)先規(guī)則，先到先服務(wù)規(guī)則和滿批規(guī)則分步驟實(shí)施，在滾動(dòng)時(shí)域策略下完成實(shí)施全部調(diào)度周期任務(wù)。

2.根據(jù)權(quán)利要求1所述的基于產(chǎn)品族排序?qū)崿F(xiàn)最小總完工時(shí)間的批調(diào)度方法，其特征在于，所述模型分解是將通用的批處理調(diào)度模型“單處理機(jī)|不同工件j到達(dá)時(shí)間，批調(diào)度，可重入，產(chǎn)品族之間不能混合組批|最小總完工時(shí)間目標(biāo)”（即：）分解成模型“單處理機(jī)|批調(diào)度，可重入，產(chǎn)品族之間不能混合組批|最小總完工時(shí)間目標(biāo)”（即：）和模型“單處理機(jī)|不同工件j到達(dá)時(shí)間，產(chǎn)品族f中所有工件j加工時(shí)間相同|最小總完工時(shí)間目標(biāo)”（即：）。

3.根據(jù)權(quán)利要求1所述的基于產(chǎn)品族排序?qū)崿F(xiàn)最小總完工時(shí)間的批調(diào)度方法，其特征在于，所述產(chǎn)品族加權(quán)最短加工時(shí)間優(yōu)先規(guī)則，令p_f表示產(chǎn)品族f的加工時(shí)間，n_f表示產(chǎn)品族f中包含工件數(shù)量，計(jì)算所有的產(chǎn)品族的加工時(shí)間和該產(chǎn)品族所包含工件數(shù)量的比值(p_f/n_f)，所有的產(chǎn)品族優(yōu)先按比值(p_f/n_f)的不減原則進(jìn)行排序。

4.根據(jù)權(quán)利要求1所述的基于產(chǎn)品族排序?qū)崿F(xiàn)最小總完工時(shí)間的批調(diào)度方法，其特征在于，所述最大重入次數(shù)優(yōu)先規(guī)則是指在產(chǎn)品族加權(quán)最短加工時(shí)間優(yōu)先規(guī)則實(shí)施中出現(xiàn)相等產(chǎn)品族的加工時(shí)間和該產(chǎn)品族所包含工件數(shù)量的比值(p_f/n_f)時(shí)，按在產(chǎn)品族重入次數(shù)的不減原則進(jìn)行排序。

5.根據(jù)權(quán)利要求1所述的基于產(chǎn)品族排序?qū)崿F(xiàn)最小總完工時(shí)間的批調(diào)度方法，其特征在于，所述先到先服務(wù)規(guī)則是指優(yōu)先級(jí)別最高的產(chǎn)品族中的工件按其到達(dá)緩沖器的時(shí)間不增原則排序。

6.根據(jù)權(quán)利要求1所述的基于產(chǎn)品族排序?qū)崿F(xiàn)最小總完工時(shí)間的批調(diào)度方法，其特征在于，所述滿批規(guī)則是指進(jìn)行工件組批時(shí)，除最后一個(gè)批中的工件數(shù)量大于或等于批的最小容量外，其余各批中工件數(shù)量必須等于批的最大容量。

7.根據(jù)權(quán)利要求1所述的基于產(chǎn)品族排序?qū)崿F(xiàn)最小總完工時(shí)間的批調(diào)度方法，其特征在于，所述分步驟實(shí)施，其主要包括以下步驟：

步驟1，產(chǎn)生觸發(fā)事件：一臺(tái)可重入批處理機(jī)處于空閑可用狀態(tài)；

步驟2，根據(jù)可重入批處理機(jī)前的緩沖期里的不同產(chǎn)品族的工件數(shù)量信息，基于“產(chǎn)品族加權(quán)最短加工時(shí)間優(yōu)先規(guī)則”和“最大重入次數(shù)優(yōu)先規(guī)則”對(duì)批處理機(jī)前緩沖器里的產(chǎn)品族工件排序，即首先計(jì)算所有的產(chǎn)品族的加工時(shí)間和該產(chǎn)品族所包含工件數(shù)量的比值(p_f/n_f)，所有的產(chǎn)品族優(yōu)先按比值(p_f/n_f)的不減原則進(jìn)行排序，當(dāng)實(shí)施產(chǎn)品族加權(quán)最短加工時(shí)間優(yōu)先規(guī)則排序中出現(xiàn)相等產(chǎn)品族的加工時(shí)間和該產(chǎn)品族所包含工件數(shù)量的比值(p_f/n_f)時(shí)，再按“最大重入次數(shù)優(yōu)先規(guī)則”排序；?

步驟3，根據(jù)步驟2的產(chǎn)品族的排序結(jié)果，選取優(yōu)先權(quán)最高的產(chǎn)品族；

步驟4，對(duì)優(yōu)先權(quán)最高的產(chǎn)品族中的工件，基于“先到先服務(wù)規(guī)則”?排序；

步驟5，根據(jù)步驟4的工件排序結(jié)果，基于“滿批規(guī)則”組建該排序工件的第一個(gè)批；

步驟6，將步驟5組建的第一個(gè)批的工件分配到步驟1的空閑可用的批處理機(jī)；

步驟7，“調(diào)度終止條件”判斷：如果不符合“調(diào)度終止條件”，根據(jù)滾動(dòng)時(shí)域策略，跳轉(zhuǎn)到步驟1，否則往下執(zhí)行；?

步驟8，基于產(chǎn)品族排序?qū)崿F(xiàn)最小總完工時(shí)間的批調(diào)度方法終止。