[發明專利]基于產品族排序實現最小總完工時間的批調度方法

有效

• 申請號: 201310022574.4
• 申請日: 2013-01-22
• 公開（公告）號: CN103136631A
• 公開（公告）日: 2013-06-05
• 發明（設計）人: 賈文友;劉莉;趙雪松;賈昊瑞;劉濤
• 申請（專利權）人: 安徽工程大學
• 主分類號: G06Q10/06
• 分類號: G06Q10/06
• 代理公司: 暫無信息
• 代理人: 暫無信息

1.一種基于產品族排序實現最小總完工時間的批調度方法，其特征在于，目標函數是所調度批的最小總完工時間，通過模型分解，先以可重入批處理機前的緩沖器里不同產品族為研究對象，再以優先權最高的產品族中工件為研究對象，利用產品族加權最短加工時間優先規則，最大重入次數優先規則，先到先服務規則和滿批規則分步驟實施，在滾動時域策略下完成實施全部調度周期任務。

2.根據權利要求1所述的基于產品族排序實現最小總完工時間的批調度方法，其特征在于，所述模型分解是將通用的批處理調度模型“單處理機|不同工件j到達時間，批調度，可重入，產品族之間不能混合組批|最小總完工時間目標”（即：）分解成模型“單處理機|批調度，可重入，產品族之間不能混合組批|最小總完工時間目標”（即：）和模型“單處理機|不同工件j到達時間，產品族f中所有工件j加工時間相同|最小總完工時間目標”（即：）。

3.根據權利要求1所述的基于產品族排序實現最小總完工時間的批調度方法，其特征在于，所述產品族加權最短加工時間優先規則，令p_f表示產品族f的加工時間，n_f表示產品族f中包含工件數量，計算所有的產品族的加工時間和該產品族所包含工件數量的比值(p_f/n_f)，所有的產品族優先按比值(p_f/n_f)的不減原則進行排序。

4.根據權利要求1所述的基于產品族排序實現最小總完工時間的批調度方法，其特征在于，所述最大重入次數優先規則是指在產品族加權最短加工時間優先規則實施中出現相等產品族的加工時間和該產品族所包含工件數量的比值(p_f/n_f)時，按在產品族重入次數的不減原則進行排序。

5.根據權利要求1所述的基于產品族排序實現最小總完工時間的批調度方法，其特征在于，所述先到先服務規則是指優先級別最高的產品族中的工件按其到達緩沖器的時間不增原則排序。

6.根據權利要求1所述的基于產品族排序實現最小總完工時間的批調度方法，其特征在于，所述滿批規則是指進行工件組批時，除最后一個批中的工件數量大于或等于批的最小容量外，其余各批中工件數量必須等于批的最大容量。

7.根據權利要求1所述的基于產品族排序實現最小總完工時間的批調度方法，其特征在于，所述分步驟實施，其主要包括以下步驟：

步驟1，產生觸發事件：一臺可重入批處理機處于空閑可用狀態；

步驟2，根據可重入批處理機前的緩沖期里的不同產品族的工件數量信息，基于“產品族加權最短加工時間優先規則”和“最大重入次數優先規則”對批處理機前緩沖器里的產品族工件排序，即首先計算所有的產品族的加工時間和該產品族所包含工件數量的比值(p_f/n_f)，所有的產品族優先按比值(p_f/n_f)的不減原則進行排序，當實施產品族加權最短加工時間優先規則排序中出現相等產品族的加工時間和該產品族所包含工件數量的比值(p_f/n_f)時，再按“最大重入次數優先規則”排序；?

步驟3，根據步驟2的產品族的排序結果，選取優先權最高的產品族；

步驟4，對優先權最高的產品族中的工件，基于“先到先服務規則”?排序；

步驟5，根據步驟4的工件排序結果，基于“滿批規則”組建該排序工件的第一個批；

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

步驟7，“調度終止條件”判斷：如果不符合“調度終止條件”，根據滾動時域策略，跳轉到步驟1，否則往下執行；?

步驟8，基于產品族排序實現最小總完工時間的批調度方法終止。