以分支定界法求取具時間窗口限制之單一批次加工機台最小化完工時間;A branch and bound algorithm for single batch processing machine with time window constraint to minimize makespan

NCU Institutional Repository > 管理學院 > 工業管理研究所 > 博碩士論文 > Item 987654321/85621

jsp.display-item.identifier=請使用永久網址來引用或連結此文件: http://ir.lib.ncu.edu.tw/handle/987654321/85621

题名:	以分支定界法求取具時間窗口限制之單一批次加工機台最小化完工時間;A branch and bound algorithm for single batch processing machine with time window constraint to minimize makespan
作者:	郭哲瑋;GUO, ZHE-WEI
贡献者:	工業管理研究所
关键词:	單機台;時間窗口;批量;分支定界法;排程;最晚完工時間;Single machine;Batch processing;Time window;Makespan;Branch and bound algorithm
日期:	2021-07-14
上传时间:	2021-12-07 11:09:18 (UTC+8)
出版者:	國立中央大學
摘要:	本研究主旨在探討單一批次加工機台在工件具時間窗口限制下極小化完工時間之排程問題。此單一機台具有固定的批次容量上限，每個工件具有一定的釋放時間和工件大小。在工件被釋放後必須在特定時間內開始加工；此特性稱為時間窗口。我們建立一多層分離圖來表示此排程問題。在多層分離圖中，上層的批次節點之間已事先給定了表示加工順序的連結弧線；下層的每個工件節點和上層所有批次節點間皆有往來的虛擬弧線以此表示待定的指派關係。我們提出一個分支定界演算法去選定層間不同的虛擬弧線成為連結弧線來尋找這個問題的一個最佳解。 ;We study a scheduling problem on the single batch processing machine to minimize the makespan. The single batch processing machine has a stable batch capacity indicating the total size of any formed batch cannot exceed the capacity. Each job has a time window to indicate the maximum waiting time of the job. We establish a multiple-layer disjunctive graph to represent this scheduling problem. In a multiple-layer disjunctive graph, the conjunctive arcs in the upper-layer have been given to represent the processing sequence of batch nodes. The disjunctive arcs in the inter-layer represent the problem of the assignment of jobs to the batches. We purpose a branch and bound algorithm to solve the problem.
显示于类别:	[工業管理研究所 ] 博碩士論文

文件中的档案:

档案	描述	大小	格式	浏览次数
index.html		0Kb	HTML	100	检视/开启

在NCUIR中所有的数据项都受到原著作权保护.

社群 sharing

数据加载中.....