机器带有循环时间窗口的排序问题
The Scheduling Problem with Cyclic Time Windows on Machines
DOI: 10.12677/AAM.2021.102042, PDF,   
作者: 曹庭锴, 刘 敏：云南民族大学数学与计算机科学学院，云南 昆明；张同全：云南民族大学预科教育学院，云南 昆明
关键词: NP困难性；最小化最大完工时间；近似算法；循环时间窗口；排序问题；NP-Hardness； Minimizing Makespan； Approximation Algorithm； Cyclic Time Window； Scheduling Problem
摘要: 给定一个在有限数量机器上加工的作业集合，如何合理地安排作业在机器上加工以达到最优解就称之为排序问题，排序问题是经典的组合优化问题之一。机器带有循环时间窗口的排序问题是在我们已知的经典排序问题基础上，给定机器上的循环时间窗口，目标是求解机器带有循环时间窗口的排序问题的最小化最大完工时间所用的天数。本文分析了问题的NP困难性，给出了一种求解机器带有循环时间窗口的排序问题的近似算法，最后证明了当k>m时，算法的最坏情况近似比为3/2，当k≤m时，算法具有一个最优平凡解。
Abstract: Given a set of jobs which would be processed on a limited number of machines, how to reasonably arrange the processing of jobs on machines to achieve the optimal solution is the scheduling problem. The scheduling problem with cyclic time windows on machines is based on the classic scheduling problem and given the cyclic time windows on machines, the aim is to minimize makespan for the scheduling problem with cyclic time windows on machines. We analyze the NP-Hardness and present an approximation algorithm for the problem. We prove that the algorithm has a worst-case approximation ratio 3/2 when k>m, and has a trivial optimal solution when k≤m.
文章引用：曹庭锴, 刘敏, 张同全. 机器带有循环时间窗口的排序问题[J]. 应用数学进展, 2021, 10(2): 367-370. https://doi.org/10.12677/AAM.2021.102042

参考文献

[1] Smith, W. (1956) Various Optimizers for Single-Stage Production. Naval Research Logistics Quarterly, 3, 59-66. [Google Scholar] [CrossRef] 
[2] Conway, R., Maxwell, W. and Miller, L. (1967) Theory of Scheduling. Addison-Wesley, Hoboken.
[3] Graham, R. (1966) Bounds for Certain Multiprocessor Anomalies. Bell System Technical Journal, 45, 1563-1581. [Google Scholar] [CrossRef] 
[4] Braun, O., Chung, F. and Graham, R. (2013) Single-Processor Scheduling with Time Restrictions. Journal of Scheduling, 17, 399-403. [Google Scholar] [CrossRef] 
[5] Yang, D.L., Lai, C.J. and Yang, S.J. (2014) Scheduling Problems with Multiple due Windows Assignment and Controllable Processing Times on a Single Machine. International Journal of Production Economics, 150, 96-103. [Google Scholar] [CrossRef] 
[6] Zhao, C.L. and Tang, H.Y. (2012) A Note to Due-Window Assignment and Single Machine Scheduling with Deteriorating Jobs and a Rate-Modifying Activity. Computers & Operations Research, 39, 1300-1303. [Google Scholar] [CrossRef] 
[7] Zhang, Y., Dan, Y.R., Dan, B., et al. (2019) The Order Scheduling Problem of Product-Service System with Time Windows. Computer and Industrial Engineering, 133, 253-266. [Google Scholar] [CrossRef] 
[8] Mosheiov, G., Sarig, A., Strusevich, V.A., et al. (2018) Two-Machine Flow Shop and Open Shop Scheduling Problems with a Single Maintenance Window. European Journal of Operational Research, 271, 388-400. [Google Scholar] [CrossRef] 
[9] Zhang, G.C., Cai, X.Q. and Wong, C.K. (2000) Linear Time-Approximation Algorithms for Bin Packing. Operation Research Letters, 26, 217-222. [Google Scholar] [CrossRef] 

为你推荐