多代理生產(chǎn)調(diào)度問題的理論研究
發(fā)布時間：2018-08-02 13:12
【摘要】：生產(chǎn)調(diào)度是指對給定的一組工件和多臺機器,在滿足生產(chǎn)工藝的約束下,確定每臺機器上工件的順序與時間,以使得能源、資源或效率等指標達到最優(yōu)。以往的調(diào)度研究主要集中在所有工件作為一個整體考慮一致的性能指標作為目標。但是隨著經(jīng)濟的發(fā)展和人們消費水平的提高,顧客對商品的個性化和多樣化的需求越來越高,傳統(tǒng)的調(diào)度理論已不再適合這種新的需求情況下的調(diào)度問題。所以迫切需要研究考慮顧客多樣性需求的多代理生產(chǎn)調(diào)度問題。多代理生產(chǎn)調(diào)度是指每個顧客的需求對應一個代理,所有代理競爭在共同的機器上同時加工各自的工件,使得每個代理的目標達到最優(yōu)。本文以鋼鐵生產(chǎn)中不同生產(chǎn)階段的工藝過程為背景,提煉出多代理生產(chǎn)調(diào)度中一系列問題。針對帶有依賴于時間惡化工件的雙代理單機調(diào)度問題、帶有線性惡化工件的雙代理單機批處理機調(diào)度問題、單機批處理機上多代理合作博弈問題、以及帶有線性惡化工件的雙代理兩臺機器車間調(diào)度問題進行了理論研究。對于上述問題,分別進行了復雜性分析；對于可解問題,給出了最優(yōu)算法或分配機制；對于難解問題,給出了NP-難證明,對難解問題的特殊情況,分析了最優(yōu)解的結(jié)構特征和性質(zhì),構造了多項式或偽多項式時間的求解方法。具體內(nèi)容概括如下：1) 針對帶有線性惡化工件和釋放時間的雙代理單機調(diào)度問題,考慮了工件釋放時間相同與不同兩種情況如下：(1)當工件釋放時間相同時,針對最小化代理A的總加權拖期工件個數(shù)使得代理B工件完工時間的最大費用不超過一個給定上界的問題,證明了問題的NP-難性。對于代理B工件完工時間的最大費用為最大完工時間的特殊情況,分析了最優(yōu)解性質(zhì),給出了偽多項式時間動態(tài)規(guī)劃算法進行求解；對于代理A的所有工件具有相等權值特殊情況,通過分析可中斷問題的最優(yōu)解結(jié)構與性質(zhì),給出了求解問題的多項式時問最優(yōu)算法。(2)當工件釋放時間不同時,針對最小化代理A的總拖期工件個數(shù)使得代理B的總拖期工件個數(shù)不超過一個給定上界的問題,證明了問題在不同數(shù)量釋放時間與工期情況下的NP-難性。對于所有工件具有一致的釋放時間與工期,或同一代理的工件具有相同惡化率和一致的釋放時間與工期兩種特殊情況,分析了最優(yōu)解性質(zhì),分別給出了多項式時間動態(tài)規(guī)劃算法進行求解。2) 針對帶有依賴于時間惡化的工件及機器維護的單機雙代理調(diào)度問題,考慮了依賴于工件的學習效應與不依賴于工件的學習效應兩種情況,其中工件的學習效應是指工件的加工時間隨著加工位置的延后而減小,如下：(1)當依賴于工件的學習效應時,針對最小化工件提前懲罰、拖期懲罰、共同工期窗開始時間費用、以及工期窗大小費用之和問題,分析了最優(yōu)解性質(zhì),將問題轉(zhuǎn)換為指派問題,進而在多項式時間求得最優(yōu)解。對于問題的三個特殊情況,分析了最優(yōu)解的結(jié)構,分別給出了更為有效的求解方法。(2)當不依賴于工件的學習效應時,針對最小化總加權完工時間與最大延遲兩個問題,分別證明了在滿足一定條件下WSPT與EDD規(guī)則仍可求得問題的最優(yōu)解。3) 針對帶有線性惡化工件的雙代理單機有界批處理機調(diào)度問題,基于工件的釋放時間相同與不同,以及工件組批時兩個代理的工件可以在同一批的兼容性與不可在同一批的不可兼容性,考慮了不同情況下目標函數(shù)為最小化代理A工件的最大完工時間(或總拖期工件個數(shù))使得代理B工件的最大完工時間(或總拖期工件個數(shù))不超過一個給定上界的八個不同問題的時間復雜性。對于可解問題,給出了多項式時間最優(yōu)算法；對于難解問題,給出了Np-難證明,對難解問題的一般情況或特殊情況,分析了最優(yōu)解性質(zhì),給出了偽多項式或多項式時間的求解方法。4) 針對帶有線性惡化工件的雙代理單機無界批處理機調(diào)度問題,基于工件組批時兩個代理的工件可以在同一批的兼容性與不可在同一批的不可兼容性,考慮了工件釋放時間相同與不同兩種情況如下：(1)當工件釋放時間相同時,針對最小化代理A工件完工時間的總費用使得代理B工件完工時間的最大費用(或總費用)不超過一個給定上界的問題,分析了問題的最優(yōu)解性質(zhì),分別給出了動態(tài)規(guī)劃算法求得最優(yōu)解；(2)當工件釋放時間不同時,針對最小化代理A工件的最大完工時間使得代理B工件的最大完工時間不超過一個給定上界的問題,分析了最優(yōu)解的結(jié)構與性質(zhì),給出了最優(yōu)解的求解方法。5) 針對單機批處理機上多代理生產(chǎn)調(diào)度的合作博弈問題,研究了多代理生產(chǎn)調(diào)度的最優(yōu)解,設計了多代理合作節(jié)省費用的合理分配機制,證明了多代理合作博弈與工件合作博弈核的存在性。對于多代理生產(chǎn)調(diào)度的特殊情況,證明了對應的多代理合作博弈與工件合作博弈均為凸博弈。6) 針對帶有線性惡化工件的雙代理兩臺機器車間調(diào)度問題,分別考慮了流水車間、開放車間、以及異序作業(yè)車間環(huán)境下,目標函數(shù)為最小化代理A工件的最大完工時間使得代理B工件的最大完工時間不超過一個給定上界的問題時間復雜性。對于流水車間,證明了問題的NP-難性,對具有優(yōu)勢機器關系的兩個特殊情況,分別給出了最優(yōu)算法。對于開放車間與異序作業(yè)車間,分別證明了問題的NP-難性。
[Abstract]:Production scheduling refers to a given set of workpieces and machines which, under the constraints of the production process, determine the sequence and time of the workpieces on each machine, so as to achieve the optimal energy, resources, or efficiency. The previous scheduling research is mainly focused on all the workpieces as a whole to consider the consistent performance indicators as a target. However, with the development of economy and the improvement of people's consumption level, the demand for individuation and diversification of the customers is getting higher and higher. The traditional scheduling theory is no longer suitable for the scheduling problem under the new demand. Therefore, it is urgent to study the multi agent production scheduling problem considering the customer diversity demand. Degree is that each customer's requirements correspond to one agent. All agents compete on a common machine to process their own workpieces at the same time, making the target of each agent achieve the best. This paper, based on the process of different production stages in the steel production, extracts a series of problems in the multi agent production scheduling. The problem of double agent single machine scheduling for deteriorating workpieces with linear deteriorating two agent single machine batch processor scheduling problem, multi agent cooperative game problem on single machine batch machine and double agent two machine shop scheduling problem with linear deteriorating workpieces are studied in theory. For the solvable problem, the optimal algorithm or distribution mechanism is given; for the difficult problem, the NP- hard proof, the special case of the difficult problem, the structure characteristics and the properties of the optimal solution are analyzed, and the method of solving the polynomial or pseudo polynomial time is constructed. The specific internal capacity is summarized as follows: 1) for the linear deteriorating workpiece and The problem of the release time double agent single machine scheduling considers the same and different two cases of the same release time of the workpiece: (1) when the release time of the work piece is the same, the maximum cost of the total weighted tardiness of the agent A makes the maximum cost of the completion time of the agent B work no more than a given upper bound, which proves the NP- difficulty of the problem. For the special case of the maximum completion time of the completion time of the proxy B work piece, the properties of the optimal solution are analyzed and the pseudo polynomial time dynamic programming algorithm is given. For all the work pieces of the proxy A with the equal weight, the optimal solution structure and properties of the broken problem are analyzed. The optimal algorithm for solving the problem of polynomial time is asked. (2) when the release time of the work piece is different, the total tardiness of the agent A is not more than a given upper bound for minimizing the number of the total tardiness of the agent B, which proves the NP- difficulty of the problem in different amount of time and time. The release time and the duration of the work, or the same agent's workpiece with the same deterioration rate and the consistent release time and the period of the two special cases, analyze the optimal solution properties, give the polynomial time dynamic programming algorithm to solve.2 respectively, for the single machine and double agent scheduling problem with the time deteriorated workpiece and machine maintenance, The learning effect depends on the learning effect of the workpiece and the learning effect that does not depend on the work piece. The learning effect of the workpiece is that the processing time of the workpiece decreases with the delay of the processing position. As follows: (1) when it depends on the learning effect of the work piece, it is aimed at minimizing the penalty for the work piece, the tardiness penalty, and the beginning of the common time window. The problem of the inter cost and the sum of the size and cost of the time window, the optimal solution properties are analyzed, the problem is converted to the assignment problem, and then the optimal solution is obtained in polynomial time. For the three special cases, the structure of the optimal solution is analyzed, and the more effective solution method is given. (2) the needle is not dependent on the learning effect of the workpiece. In order to minimize the two problems of the total weighted completion time and the maximum delay, it is proved that the optimal solution.3 of the WSPT and EDD rules can still be obtained under certain conditions. The scheduling problem of a double agent single machine bounded batch processor with linear deteriorating jobs is based on the same and different release time based on the work piece, and two of the work group batch. The agent's workpiece can be compatible with the same batch and cannot be compatible in the same batch, considering that the maximum completion time (or the number of total tardiness artifacts) of the agent A workpiece in different circumstances makes the maximum completion time (or the number of total tardiness artifacts) of the proxy B workpiece not more than eight of a given upper bound. The time complexity of the same problem is given. For the solvable problem, a polynomial time optimal algorithm is given. For the difficult problem, the Np- hard proof is given, the general condition or special case of the difficult problem is given. The properties of the optimal solution are analyzed, the pseudo polynomial or the polynomial time solution method.4) is given for the double agent with the linear deteriorating work. The scheduling problem of single machine unbounded batch processor is based on the compatibility between the two agents and the non compatibility of the same batch in the same batch, considering the same release time and the two different situations as follows: (1) when the release time of the work piece is the same, the total cost of minimizing the completion time of the agent A work piece is minimized. The maximum cost (or total cost) of the completion time of the agent B is not more than a given upper bound, and the optimal solution properties of the problem are analyzed. The optimal solution of the dynamic programming algorithm is given respectively. (2) the maximum completion time of the agent A work is made to minimize the maximum completion time of the agent to make the maximum completion of the agent B workpiece. The structure and properties of a given upper bound are not exceeded, the structure and properties of the optimal solution are analyzed, and the solution method of the optimal solution.5) is given. In view of the cooperative game problem of the multi agent production scheduling on a single machine batch machine, the optimal solution of the multi agent production scheduling is studied, and the reasonable allocation mechanism of the multi generation rational cooperation and cost saving is designed. The existence of multi agent cooperative game and job cooperative game kernel. For the special situation of multi agent production scheduling, it is proved that the corresponding multi agent cooperative game and the job cooperative game are all convex game.6). For the double agent two machine shop scheduling problem with linear deteriorating workpieces, the flow shop and open shop are considered respectively. In the environment of the job shop, the objective function is to minimize the maximum completion time of the agent A job making the maximum completion time of the agent B workpiece not more than the time complexity of the problem of a given upper bound. For the flow shop, the NP- difficulty of the problem is proved, and the optimum for the two special cases with the dominant machine relationship is given. Algorithm. For open shop and heterogeneous job shop, the NP- difficulty of the problem is proved respectively.
【學位授予單位】：東北大學
【學位級別】：博士
【學位授予年份】：2015
【分類號】：TB497
本文編號：2159547
[Abstract]:Production scheduling refers to a given set of workpieces and machines which, under the constraints of the production process, determine the sequence and time of the workpieces on each machine, so as to achieve the optimal energy, resources, or efficiency. The previous scheduling research is mainly focused on all the workpieces as a whole to consider the consistent performance indicators as a target. However, with the development of economy and the improvement of people's consumption level, the demand for individuation and diversification of the customers is getting higher and higher. The traditional scheduling theory is no longer suitable for the scheduling problem under the new demand. Therefore, it is urgent to study the multi agent production scheduling problem considering the customer diversity demand. Degree is that each customer's requirements correspond to one agent. All agents compete on a common machine to process their own workpieces at the same time, making the target of each agent achieve the best. This paper, based on the process of different production stages in the steel production, extracts a series of problems in the multi agent production scheduling. The problem of double agent single machine scheduling for deteriorating workpieces with linear deteriorating two agent single machine batch processor scheduling problem, multi agent cooperative game problem on single machine batch machine and double agent two machine shop scheduling problem with linear deteriorating workpieces are studied in theory. For the solvable problem, the optimal algorithm or distribution mechanism is given; for the difficult problem, the NP- hard proof, the special case of the difficult problem, the structure characteristics and the properties of the optimal solution are analyzed, and the method of solving the polynomial or pseudo polynomial time is constructed. The specific internal capacity is summarized as follows: 1) for the linear deteriorating workpiece and The problem of the release time double agent single machine scheduling considers the same and different two cases of the same release time of the workpiece: (1) when the release time of the work piece is the same, the maximum cost of the total weighted tardiness of the agent A makes the maximum cost of the completion time of the agent B work no more than a given upper bound, which proves the NP- difficulty of the problem. For the special case of the maximum completion time of the completion time of the proxy B work piece, the properties of the optimal solution are analyzed and the pseudo polynomial time dynamic programming algorithm is given. For all the work pieces of the proxy A with the equal weight, the optimal solution structure and properties of the broken problem are analyzed. The optimal algorithm for solving the problem of polynomial time is asked. (2) when the release time of the work piece is different, the total tardiness of the agent A is not more than a given upper bound for minimizing the number of the total tardiness of the agent B, which proves the NP- difficulty of the problem in different amount of time and time. The release time and the duration of the work, or the same agent's workpiece with the same deterioration rate and the consistent release time and the period of the two special cases, analyze the optimal solution properties, give the polynomial time dynamic programming algorithm to solve.2 respectively, for the single machine and double agent scheduling problem with the time deteriorated workpiece and machine maintenance, The learning effect depends on the learning effect of the workpiece and the learning effect that does not depend on the work piece. The learning effect of the workpiece is that the processing time of the workpiece decreases with the delay of the processing position. As follows: (1) when it depends on the learning effect of the work piece, it is aimed at minimizing the penalty for the work piece, the tardiness penalty, and the beginning of the common time window. The problem of the inter cost and the sum of the size and cost of the time window, the optimal solution properties are analyzed, the problem is converted to the assignment problem, and then the optimal solution is obtained in polynomial time. For the three special cases, the structure of the optimal solution is analyzed, and the more effective solution method is given. (2) the needle is not dependent on the learning effect of the workpiece. In order to minimize the two problems of the total weighted completion time and the maximum delay, it is proved that the optimal solution.3 of the WSPT and EDD rules can still be obtained under certain conditions. The scheduling problem of a double agent single machine bounded batch processor with linear deteriorating jobs is based on the same and different release time based on the work piece, and two of the work group batch. The agent's workpiece can be compatible with the same batch and cannot be compatible in the same batch, considering that the maximum completion time (or the number of total tardiness artifacts) of the agent A workpiece in different circumstances makes the maximum completion time (or the number of total tardiness artifacts) of the proxy B workpiece not more than eight of a given upper bound. The time complexity of the same problem is given. For the solvable problem, a polynomial time optimal algorithm is given. For the difficult problem, the Np- hard proof is given, the general condition or special case of the difficult problem is given. The properties of the optimal solution are analyzed, the pseudo polynomial or the polynomial time solution method.4) is given for the double agent with the linear deteriorating work. The scheduling problem of single machine unbounded batch processor is based on the compatibility between the two agents and the non compatibility of the same batch in the same batch, considering the same release time and the two different situations as follows: (1) when the release time of the work piece is the same, the total cost of minimizing the completion time of the agent A work piece is minimized. The maximum cost (or total cost) of the completion time of the agent B is not more than a given upper bound, and the optimal solution properties of the problem are analyzed. The optimal solution of the dynamic programming algorithm is given respectively. (2) the maximum completion time of the agent A work is made to minimize the maximum completion time of the agent to make the maximum completion of the agent B workpiece. The structure and properties of a given upper bound are not exceeded, the structure and properties of the optimal solution are analyzed, and the solution method of the optimal solution.5) is given. In view of the cooperative game problem of the multi agent production scheduling on a single machine batch machine, the optimal solution of the multi agent production scheduling is studied, and the reasonable allocation mechanism of the multi generation rational cooperation and cost saving is designed. The existence of multi agent cooperative game and job cooperative game kernel. For the special situation of multi agent production scheduling, it is proved that the corresponding multi agent cooperative game and the job cooperative game are all convex game.6). For the double agent two machine shop scheduling problem with linear deteriorating workpieces, the flow shop and open shop are considered respectively. In the environment of the job shop, the objective function is to minimize the maximum completion time of the agent A job making the maximum completion time of the agent B workpiece not more than the time complexity of the problem of a given upper bound. For the flow shop, the NP- difficulty of the problem is proved, and the optimum for the two special cases with the dominant machine relationship is given. Algorithm. For open shop and heterogeneous job shop, the NP- difficulty of the problem is proved respectively.
【學位授予單位】：東北大學
【學位級別】：博士
【學位授予年份】：2015
【分類號】：TB497
【相似文獻】
相關期刊論文 前10條
1 金霽;顧燕紅;唐國春;;最大完工時間排序的兩人合作博弈[J];上海第二工業(yè)大學學報;2011年01期
2 曹國梅;;一類無界的不相容工件族分批排序加權總完工時間問題[J];常熟理工學院學報;2009年04期
3 鄭文;;工序完成時間不確定的統(tǒng)籌圖分析[J];重慶工商大學學報(自然科學版);2013年06期
4 趙傳立,張慶靈,唐恒永;具有簡單線性惡化加工時間的Flow shop調(diào)度問題[J];東北大學學報;2002年09期
5 趙傳立,張慶靈,唐恒永;極小化加權完工時間和的調(diào)度問題[J];東北大學學報;2003年06期
6 鐘雪靈;王國慶;王雄志;;極小化最大提前完工時間的單機排序問題[J];武漢大學學報(工學版);2011年01期
7 蘭繼斌;關于CON交貨期的一個最優(yōu)問題[J];廣西大學學報(自然科學版);1996年01期
8 王先甲,萬仲平;時間—資源權衡協(xié)調(diào)問題的多目標優(yōu)化決策模型[J];中國工程科學;2005年02期
9 陳家棟;流水型多工序排序優(yōu)化中總作業(yè)時間的算法問題[J];成組生產(chǎn)系統(tǒng);1989年02期
10 廖小平;劉有根;李小平;;最小化最長完工時間和總完工時間的無等待流水調(diào)度混合進化算法(英文)[J];Journal of Southeast University(English Edition);2008年04期
相關會議論文 前2條
1 張樹霞;曹志剛;張玉忠;;極小化最大完工時間的離散可控排序(英文)[A];中國運籌學會第八屆學術交流會論文集[C];2006年
2 陳克兵;高成修;;可變加工時間的單機排序(英文)[A];中國運籌學會第七屆學術交流會論文集（上卷）[C];2004年
相關博士學位論文 前7條
1 趙曉麗;多代理生產(chǎn)調(diào)度問題的理論研究[D];東北大學;2015年
2 馬英;考慮維護時間的機器調(diào)度問題研究[D];合肥工業(yè)大學;2010年
3 李曙光;批調(diào)度與網(wǎng)絡問題的組合算法[D];山東大學;2007年
4 馬冉;最小化加權完工時間和的在線排序研究[D];鄭州大學;2015年
5 何程;多目標分批排序及其相關課題[D];鄭州大學;2009年
6 張國輝;柔性作業(yè)車間調(diào)度方法研究[D];華中科技大學;2009年
7 鄭俊麗;船舶分段制造車間的模塊空間調(diào)度模型及算法[D];上海交通大學;2011年
相關碩士學位論文 前10條
1 孔祥玉;作業(yè)時空受限的生產(chǎn)與運輸調(diào)度問題研究[D];沈陽大學;2015年
2 柴幸;最小化最大加權完工時間的平行分批在線排序問題[D];鄭州大學;2015年
3 邱言玲;工件加工中的排序博弈方法[D];西安電子科技大學;2014年
4 朱曉燦;基于Hadoop的試驗檢測計劃總完工時間極小化研究[D];西安電子科技大學;2015年
5 林琳;基于分枝定界的動態(tài)流水車間最大完工時間問題研究[D];東北大學;2015年
6 衛(wèi)志剛;可自由離線批處理機最小化加權完工時間和排序[D];鄭州大學;2011年
7 尹婷;鋼鐵生產(chǎn)中連續(xù)批調(diào)度的策略研究[D];武漢科技大學;2011年
8 夏勁偉;GPU中針對任務完工時間最小化問題的研究[D];東北大學;2012年
9 曹志剛;分批排序、可拒絕排序及離散可控排序中的若干問題[D];曲阜師范大學;2006年
10 曹順娟;同類機半在線機器覆蓋問題研究[D];浙江大學;2006年
，本文編號：2159547
本文鏈接：http://www.wukwdryxk.cn/guanlilunwen/gongchengguanli/2159547.html
最近更新
教材專著
