带时间窗口的单工件排序问题
The Scheduling Problem of Single Job with Time Windows
DOI: 10.12677/AAM.2020.912251, PDF,   
作者: 刘 敏, 曹庭锴：云南民族大学数学与计算机科学学院，云南 昆明；张同全：云南民族大学预科教育学院，云南 昆明
关键词: 排序；循环时间窗口；NP-难；近似算法；Scheduling； Cycle Time Windows； NP-Hard； Approximate Algorithm
摘要: 排序是为加工若干个工件或者完成若干项任务而对资源按时间进行高效率的分配，本文讨论一个工件的情况下对多台机器进行排序，从而使加工时间最短的问题。在这个问题中给定一个时间窗口作为约束，机器只能在规定的时间窗口内运行。分析该问题是NP-难问题，并给出一个近似算法，讨论该近似算法的近似比不超过3/2，该近似算法的时间复杂度为O(m2)。
Abstract: Scheduling is the efficient allocation of resources according to time in order to process a number of jobs or complete a number of tasks. This paper discusses the problem of scheduling multiple machines in the case of one job so as to minimize the processing time. In this problem, we give a time window as a constraint; machines can only run within the time window. The problem is NP-hard and an approximate algorithm is given. The approximate ratio of the approximate algorithm is not more than 3/2. The time complexity of this algorithm is O(m2).
文章引用：刘敏, 曹庭锴, 张同全. 带时间窗口的单工件排序问题[J]. 应用数学进展, 2020, 9(12): 2161-2165. https://doi.org/10.12677/AAM.2020.912251

参考文献

[1] 刘洋. 基于动态约束满足的一类含时间窗口的多资源动态调度模型与方法[C]//中国运筹学会. 中国运筹学会第七届学术交流会论文集(中卷). 北京: 中国运筹学会, 2004: 155-163.
[2] Lee, C.-Y. (1996) Machine Scheduling with an Availability Constraint. Journal of Global Optimization, 9, 395-416. [Google Scholar] [CrossRef] 
[3] Vickson, R.G. and Alfredsson, B.E. (1980) Two Single Machine Sequencing Problems Involving Controllable Job Processing Time. IIE Transactions, 12, 258-292. [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] Zhang, A., Chen, Y., Chen, L. and Chen, G.T. (2018) On the NP-Hardness of Scheduling with Time Restrictions. Discrete Optimization, 28, 54-62. [Google Scholar] [CrossRef] 
[6] Khatami, M., Salehipour, A. and Hwang, F.J. (2019) Makespan Minimization for the M-Machine Ordered Flow Shop Scheduling Problem. Computer and Operation Research, 111, 400-414. [Google Scholar] [CrossRef] 
[7] Book, R.V. (1980) Review: Michael R. Garey and David S. Johnson, Computers and intractability: A Guide to the Theory of NP-Completeness. Bulletin (New Series) of the American Mathematical Society, 3, 898-904. [Google Scholar] [CrossRef] 
[8] Zhang, G.C., Cai, X.Q. and Wong, C.K. (2000) Linear Time-Approximation Algorithm for Bin Packing. Operations Research Letters, 26, 217-222. [Google Scholar] [CrossRef] 

为你推荐