两台并行机器上进行多属性准备时间的工序设置问题
Scheduling with Multi-Attribute Preparation Times on Two Parallel Machines
DOI: 10.12677/AAM.2018.710154, PDF,    国家自然科学基金支持
作者: 熊辉：广东广业开元科技有限公司，广东 广州；广州临观教育信息有限公司，广东 广州；梁培锋, 王晓佳, 朱彬：广东广业开元科技有限公司，广东 广州
关键词: 并行机器；工序设置；多重属性准备时间；启发式演算；变邻域搜索；Parallel Machines； Scheduling Problem； Multi-Attribute Preparation Times； Heuristic Algorithm； Variable Neighborhood Search
摘要: 本文研究聚氯乙烯皮革(PVCL)工厂的多重属性准备时间的工序设置问题。针对于两台同样的并行机器，按顺序生产具有不同层次、不同属性、不同工种的PVCL制品，目标函数是设置一个加工排序，使得最大完工时间极小化。首先提出一个建构式的启发式演算法，与工厂现行排序法做比较，以评估此算法的绩效；继续提出变邻域搜寻算法，以进一步改善启发式算法所求得的解，并与混合整数规划模型做比较。实验结果证明，本文的启发式演算法显著性地优于现行PVCL工厂所使用的排序方法，而VNS算法的运行结果也证实能有效改善启发式演算法所求得的解。
Abstract: The scheduling problem with multi-attribute preparation times studied here is from the polyvinyl chloride leather (PVCL) plant. On two identical parallel machines, the products are processed in sequence of different levels, attributes, and jobs. The objective is to determine a schedule for two identical parallel machines to minimize the makespan. A constructive heuristic is firstly proposed and evaluated by comparing with the current scheduling method used by the case plant. To further improve the solution, a variable neighborhood search (VNS) meta-heuristic is presented and compared with a mixed integer programming model. The computational results show that the heuristic outperforms the current scheduling method with a significant improvement, and the VNS can further improve the solution.
文章引用：熊辉, 梁培锋, 王晓佳, 朱彬. 两台并行机器上进行多属性准备时间的工序设置问题[J]. 应用数学进展, 2018, 7(10): 1325-1333. https://doi.org/10.12677/AAM.2018.710154

参考文献

[1] Abreu, C.F., May, J.H., Spangler, W.E., et al. (2008) Conflict Identification and Reconciliation in a Collaborative Manufacturing Scheduling Task. International Journal of Information Technology & Decision Making, 7, 147-174. [Google Scholar] [CrossRef] 
[2] Chen, W.J. (2009) Scheduling with Dependent Setups and Maintenance in a Textile Company. Computers & Industrial Engineering, 57, 867-873. [Google Scholar] [CrossRef] 
[3] Lee, C.H., Liao, C.J. and Chao, C.W. (2012) Scheduling with Multi-Attribute Setup Times. Computers & Industrial Engineering, 63, 494-502. [Google Scholar] [CrossRef] 
[4] Logendran, R., McDonell, B. and Smucker, B. (2007) Scheduling Unrelated Parallel Machines with Sequence-Dependent Setups. Computers & Operations Research, 34, 3420-3438. [Google Scholar] [CrossRef] 
[5] Chen, J.F. (2006) Minimization of Maximum Tardiness on Unrelated Parallel Machines with Process Restrictions and Setups. The International Journal of Advanced Manufacturing Technology, 29, 557-563. [Google Scholar] [CrossRef] 
[6] Abdekhodaee, A.H., Wirth, A. and Gan, H.S. (2006) Scheduling Two Parallel Machines with a Single Server: The General Case. Computers & Operations Research, 33, 994-1009. [Google Scholar] [CrossRef] 
[7] Chan, F.T.S. and Choy, K.L. (2011) A Genetic Algorithm-Based Scheduler for Multiproduct Parallel Machine Sheet Metal Job Shop. Expert Systems with Applications, 38, 8703-8715. [Google Scholar] [CrossRef] 
[8] Chuang, M.C., Liao, C.J. and Chao, C.W. (2010) Parallel Machine Scheduling with Preference of Machines. International Journal of Production Research, 48, 4139-4152. [Google Scholar] [CrossRef] 
[9] Sun, K. and Li, H. (2010) Scheduling Problems with Multiple Maintenance Activities and Non-Preemptive Jobs on Two Identical Parallel Machines. International Journal of Production Economics, 124, 151-158. [Google Scholar] [CrossRef] 
[10] Pinedo, M. (2012) Scheduling: Theory, Algorithms, and Systems. 3rd Edition, Springer, Berlin. [Google Scholar] [CrossRef] 
[11] Liao, C.J., Shyu, C.C. and Tseng, C.T. (2009) A Least Flexibility First Heuristic to Coordinate Setups in a Two- Or Three-Stage Supply Chain. International Journal of Production Economics, 117, 127-135. [Google Scholar] [CrossRef] 
[12] Gravel, M., Price, W.L. and Gagné, C. (2002) Scheduling Continuous Casting of Aluminum Using a Multiple Objective Ant Colony Optimization Metaheuristic. European Journal of Operational Research, 143, 218-229. [Google Scholar] [CrossRef] 
[13] Imran, A., Salhi, S. and Wassan, N.A. (2009) A Variable Neighborhood-Based Heuristic for the Heterogeneous Fleet Vehicle Routing Problem. European Journal of Operational Research, 197, 509-518. [Google Scholar] [CrossRef] 
[14] Hansen, P., Mladenović, N. and Pérez, J.A.M. (2010) Variable Neighbourhood Search: Methods and Applications. Annals of Operations Research, 175, 367-407. [Google Scholar] [CrossRef] 

为你推荐