柔性开放车间调度算法研究
|
摘要
在制造领域,调度是生产管理的核心和关键技术,合理的调度可以缩短制造期、减少资源浪费,提高经济效益。随着生产过程的日益复杂和竞争的加剧,调度的作用越来越重要。
柔性开放车间调度问题(FOSSP)是生产中常见的调度问题,也是亟待解决的高难度组合优化问题。本文主要研究加工可中断、不可中断和具有机器使用限制三种情况下的柔性开放车间调度问题(Om(P)|pmtn,ri|Cmax、Om(P)||Cmax和Om(P)|r,aN,I|Cmax)的数建模和近似调度算法设计。针对问题特点,分别采用网络流和半匹配理论设计了相应的近似调度算法,并给出了算法的最坏情况界等性能参数。
本文主要研究内容包括以下五个方面：
1.研究了柔性开放车间调度问题的数学建模方法。分析了可中断、不可中断和具有机器使用限制三种情况下柔性开放车间生产过程的约束条件,将它们形式化的表示为一组约束函数,以制造期最短为优化目标,建立了上述三种柔性开放车间调度问题的混合整数规划模型,为算法验证奠定了基础。
2.以制造期最短为优化目标,给出了基于网络流的Om(P)|pmtn,ri|Cmax(?)司题调度算法。算法将Om(P)|pmtn,ri|Cmax问题分解为资源分配和工件排序两个子问题,首先将调度问题转化为网络流模型,通过最大流算法确定使机器满负荷工作的资源分配方案。为了提高最大流算法的效率,研究了融入加工领域知识的活跃顶点选择策略,采用最小负载优先和最大工作量优先启发式规则设计了高效率的最大流算法。针对最大流存在陷入局部优化的情况,给出了优化方法。在最大流的基础上,通过加工时间矩阵的减量集合确定工件的加工顺序
3.针对Om(P)||Gmax问题求解难度大的特点,给出了以稠密调度为目标的近似调度算法求解方案,该方案将调度问题分解为资源匹配和调度优化两个子问题,每次资源匹配所有工件都仅完成一个操作,那么具有m个操作的工件集合需要进行m次资源匹配,通过连接各资源匹配结果得到初步调度解,最后对初步调度解进行优化,消除不必要的机器空闲时间,得到稠密调度解。在两个子问题中,资源匹配是核心问题,文中采用赋权二分图进行建模,通过半匹配求得负载差异最小的资源匹配结果,并且针对小规模和大规模问题分别设计了基于最优增广路径和基于遗传算法的最优半匹配算法。在资源匹配的基础上,本文给出了初步调度解的构造方法及其优化方法。
4.研究了Om(P)|r,aN.I|Cmax问题制造期下界的计算方法。由于存在机器使用限制,无法通过简单的方法获得制造期的下界。因此,本文通过约束松弛将原问题转化为机器使用限制下可中断柔性开放车间调度问题(Om(P)|r,aN.I,pmtn|Cmax),Om(P)|r,aN.I,pmtn|Cmax易于解决,将它的最短制造期作为Om(P)|r,aN.I|Cmax问题制造期的下界。具体的解决方法是首先建立Om(P)|r,aN.I,pmtn|Cmax|司题的混合整数规划模型,在此基础上将模型中的约束条件转化为弧的容量约束,得到问题的网络流模型。然后,通过最大流算法求得它的制造期,以此作为Om(P)|r,aN.I|Cmax问题的制造期下界。
5.针对Om(P)|r,aN.1|Cmax问题,给出了最坏情况界为2的稠密调度算法。Om(P)|r,aN1|Cmax问题允许机器在制造期内含有一个不可用时间窗,并且被中断工件在机器恢复可用后可以继续加工。文中将机器的不可用时间窗定义为虚拟工件,它的加工起止时间等于不可用时间窗的开始时间和结束时间。为了降低问题的难度,首先在不考虑虚拟工件的情况下进行资源匹配,进而通过分析虚拟工件与资源匹配制造期间的关系,得到三种模式关系。针对每种模式的特点,给出了考虑虚拟工件后的资源匹配调整方法。在此基础上,设计了Om(P)|r,aN.1|Cmax问题的稠密调度算法。
在算法性能研究方面,本文从理论和算例试验两个方面分析了上述三种柔性开放车间调度算法的性能。在理论上,分析了调度算法的时间复杂度和最坏情况界,并通过随机产生的算例验证了算法的正确性,结果表明算法能够求得调度问题的有效解,并且制造期满足最坏情况界指标。
Scheduling is the core content and key technology in production managerment. Proper and effective scheduling can help minimize makespan, waste of resources, and increase economic benefit. With the upgrading of market competition and complexity of production process, scheduling is playing an increasingly important role in the manufacturing industry.
Flexible open shop scheduling problem (FOSSP) is one of the most well-known scheduling problems. Meanwhile, FOSSP is one of the most difficult combinatorial optimization problems. Mathematical modeling and approximation algorithms for FOSSP with preemptive constraint, non-preemptive constraint and machine availability constraint (Om(P)|pmtn,r1|Cmax、Om(P)||Cmax and Om(P)|r, aN.I|Cmax) were studied systemly in this thesis. Three approximation algorithms for the three FOSSP problems were proposed, which were based on network flow and semi-matching theory. And the performance parameters of the three algorithms were analysised, such as worse-case ratio and time complexity
The main contents are as following:
1. Mathematical modeling methods of FOSSP were studied. Constraint conditions of Om(P)|pmtn, ri|Cmax、Om(P)||Cmax and Om(P)|r,aN.1|Cmax problems were analysis, which were represented by constraint functions. Then three mixed integer programming models with the objective of minimizing the makespan for Om(P)|pmtn, ri|Cmax、Om(P)||Cmax and Om(P)|r,aN |Cmax problems were established, which set a foundation for scheduling algorithm verification.
2. A network flow based algorithm for Om(P)|pmtn, ri|Cmax problem was presented, which decomposed Om(P)|pmtn,ri|Cmax, problem into resource allocation and job sequencing two sub-problems. Firstly, the maximum flow model was developed to model the resource allocation and time constraints. and the maximum flow was the solution of the resource allocation, which made machine in full load condition. Moreover a new pre-flow push algorithm and optimization method for the maximum flow model were putforward, which used the least load first rule and the largest task first rule in active node selection. Based on the solution of machine allocation problem got by pre-flow push algorithm, the sequences of the tasks processed by each machine were determined by calculating the matrix of the processing times and decrementing set.
3. Due to the complexity of Om(P)||Cmax problem, a dense scheduling algorithm was developed, which decomposed Om(P)||Cmax problem into resource matching and optimization two sub-problems. Only one operation of each job was completed in each resource matching, so m times of resource matching should be done for jobs set containing m operations. Initial solution was got by connecting resource matching results. Resource matching was modeled by a semi-matching on weighted bipartite graph, and two semi-matching algorithms were developed. For small scale scheduling problem, a balanced semi-matching algorithm based on augmenting path was presented, and a balanced semi-matching algorithm genetic algorithm was developed for large scale scheduling problem. Meanwhile, initial solution and scheduling optimization method was presented.
4. The lower bound on makespan in Om(P)|r, aN.1|Cmax problem was studied. By relaxing the non-preemptive constraint, Om(P)|r, aN.1|Cmax problem can be converted into Om(P)|r, aN.1, pmtn |Cmax problem that can be solved easier, and the makespan of Om(P)|r, aN.1, pmtn|C problem can be served as the lower bound on makespan in Om(P)|r, aN.1|Cmax problem. The concrete procedure was that, firstly, the mixed integer programming model with the objective of minimizing the makespan for Om(P)|r, aN. 1,pmtn\Cmax problems was established, which was used as foundation to develope the maximum flow model for Om(P)|r, aN 1, pmtn|C, problem. Then, the makespan of Om(P)|r, aN.1, pmtn|Cmax problem can be got by maximum flow algorithm, which were the lower bound on makespan in Om(P)|r, aN. 1|Cmax problem.
5. We developed a dense scheduling algorithm for Om(P)|r. aN.1|Cmax problem with a worst-case performance ratio less than 2. In Om(P)|r, aN.1|Cmax problem, each machine has a fixed and known unavailable period, and job interrupted by unavailable period can continue to be processed on the same machine after the machine has become available. In this thesis, the unavailable periods were treated as special jobs, which were called virtual jobs. In order to reduce the difficulty, resource matchings were done firstly without consideration of virtual job. Then, the relationship between makespan of resource matching and virtual job was analysis, and three modes were got. The method Based on the analysis, a dense algorithm for Om(P)|r, aN.1|Cmax problem were developed.
The performances of the three algorithms developed in this paper were analysis from two aspects:firstly, worse case ratio and time complexity were analysis; then, the validity of the developed scheduling algorithms were illustrated by randomly generated examples.
柔性开放车间调度问题(FOSSP)是生产中常见的调度问题,也是亟待解决的高难度组合优化问题。本文主要研究加工可中断、不可中断和具有机器使用限制三种情况下的柔性开放车间调度问题(Om(P)|pmtn,ri|Cmax、Om(P)||Cmax和Om(P)|r,aN,I|Cmax)的数建模和近似调度算法设计。针对问题特点,分别采用网络流和半匹配理论设计了相应的近似调度算法,并给出了算法的最坏情况界等性能参数。
本文主要研究内容包括以下五个方面：
1.研究了柔性开放车间调度问题的数学建模方法。分析了可中断、不可中断和具有机器使用限制三种情况下柔性开放车间生产过程的约束条件,将它们形式化的表示为一组约束函数,以制造期最短为优化目标,建立了上述三种柔性开放车间调度问题的混合整数规划模型,为算法验证奠定了基础。
2.以制造期最短为优化目标,给出了基于网络流的Om(P)|pmtn,ri|Cmax(?)司题调度算法。算法将Om(P)|pmtn,ri|Cmax问题分解为资源分配和工件排序两个子问题,首先将调度问题转化为网络流模型,通过最大流算法确定使机器满负荷工作的资源分配方案。为了提高最大流算法的效率,研究了融入加工领域知识的活跃顶点选择策略,采用最小负载优先和最大工作量优先启发式规则设计了高效率的最大流算法。针对最大流存在陷入局部优化的情况,给出了优化方法。在最大流的基础上,通过加工时间矩阵的减量集合确定工件的加工顺序
3.针对Om(P)||Gmax问题求解难度大的特点,给出了以稠密调度为目标的近似调度算法求解方案,该方案将调度问题分解为资源匹配和调度优化两个子问题,每次资源匹配所有工件都仅完成一个操作,那么具有m个操作的工件集合需要进行m次资源匹配,通过连接各资源匹配结果得到初步调度解,最后对初步调度解进行优化,消除不必要的机器空闲时间,得到稠密调度解。在两个子问题中,资源匹配是核心问题,文中采用赋权二分图进行建模,通过半匹配求得负载差异最小的资源匹配结果,并且针对小规模和大规模问题分别设计了基于最优增广路径和基于遗传算法的最优半匹配算法。在资源匹配的基础上,本文给出了初步调度解的构造方法及其优化方法。
4.研究了Om(P)|r,aN.I|Cmax问题制造期下界的计算方法。由于存在机器使用限制,无法通过简单的方法获得制造期的下界。因此,本文通过约束松弛将原问题转化为机器使用限制下可中断柔性开放车间调度问题(Om(P)|r,aN.I,pmtn|Cmax),Om(P)|r,aN.I,pmtn|Cmax易于解决,将它的最短制造期作为Om(P)|r,aN.I|Cmax问题制造期的下界。具体的解决方法是首先建立Om(P)|r,aN.I,pmtn|Cmax|司题的混合整数规划模型,在此基础上将模型中的约束条件转化为弧的容量约束,得到问题的网络流模型。然后,通过最大流算法求得它的制造期,以此作为Om(P)|r,aN.I|Cmax问题的制造期下界。
5.针对Om(P)|r,aN.1|Cmax问题,给出了最坏情况界为2的稠密调度算法。Om(P)|r,aN1|Cmax问题允许机器在制造期内含有一个不可用时间窗,并且被中断工件在机器恢复可用后可以继续加工。文中将机器的不可用时间窗定义为虚拟工件,它的加工起止时间等于不可用时间窗的开始时间和结束时间。为了降低问题的难度,首先在不考虑虚拟工件的情况下进行资源匹配,进而通过分析虚拟工件与资源匹配制造期间的关系,得到三种模式关系。针对每种模式的特点,给出了考虑虚拟工件后的资源匹配调整方法。在此基础上,设计了Om(P)|r,aN.1|Cmax问题的稠密调度算法。
在算法性能研究方面,本文从理论和算例试验两个方面分析了上述三种柔性开放车间调度算法的性能。在理论上,分析了调度算法的时间复杂度和最坏情况界,并通过随机产生的算例验证了算法的正确性,结果表明算法能够求得调度问题的有效解,并且制造期满足最坏情况界指标。
Scheduling is the core content and key technology in production managerment. Proper and effective scheduling can help minimize makespan, waste of resources, and increase economic benefit. With the upgrading of market competition and complexity of production process, scheduling is playing an increasingly important role in the manufacturing industry.
Flexible open shop scheduling problem (FOSSP) is one of the most well-known scheduling problems. Meanwhile, FOSSP is one of the most difficult combinatorial optimization problems. Mathematical modeling and approximation algorithms for FOSSP with preemptive constraint, non-preemptive constraint and machine availability constraint (Om(P)|pmtn,r1|Cmax、Om(P)||Cmax and Om(P)|r, aN.I|Cmax) were studied systemly in this thesis. Three approximation algorithms for the three FOSSP problems were proposed, which were based on network flow and semi-matching theory. And the performance parameters of the three algorithms were analysised, such as worse-case ratio and time complexity
The main contents are as following:
1. Mathematical modeling methods of FOSSP were studied. Constraint conditions of Om(P)|pmtn, ri|Cmax、Om(P)||Cmax and Om(P)|r,aN.1|Cmax problems were analysis, which were represented by constraint functions. Then three mixed integer programming models with the objective of minimizing the makespan for Om(P)|pmtn, ri|Cmax、Om(P)||Cmax and Om(P)|r,aN |Cmax problems were established, which set a foundation for scheduling algorithm verification.
2. A network flow based algorithm for Om(P)|pmtn, ri|Cmax problem was presented, which decomposed Om(P)|pmtn,ri|Cmax, problem into resource allocation and job sequencing two sub-problems. Firstly, the maximum flow model was developed to model the resource allocation and time constraints. and the maximum flow was the solution of the resource allocation, which made machine in full load condition. Moreover a new pre-flow push algorithm and optimization method for the maximum flow model were putforward, which used the least load first rule and the largest task first rule in active node selection. Based on the solution of machine allocation problem got by pre-flow push algorithm, the sequences of the tasks processed by each machine were determined by calculating the matrix of the processing times and decrementing set.
3. Due to the complexity of Om(P)||Cmax problem, a dense scheduling algorithm was developed, which decomposed Om(P)||Cmax problem into resource matching and optimization two sub-problems. Only one operation of each job was completed in each resource matching, so m times of resource matching should be done for jobs set containing m operations. Initial solution was got by connecting resource matching results. Resource matching was modeled by a semi-matching on weighted bipartite graph, and two semi-matching algorithms were developed. For small scale scheduling problem, a balanced semi-matching algorithm based on augmenting path was presented, and a balanced semi-matching algorithm genetic algorithm was developed for large scale scheduling problem. Meanwhile, initial solution and scheduling optimization method was presented.
4. The lower bound on makespan in Om(P)|r, aN.1|Cmax problem was studied. By relaxing the non-preemptive constraint, Om(P)|r, aN.1|Cmax problem can be converted into Om(P)|r, aN.1, pmtn |Cmax problem that can be solved easier, and the makespan of Om(P)|r, aN.1, pmtn|C problem can be served as the lower bound on makespan in Om(P)|r, aN.1|Cmax problem. The concrete procedure was that, firstly, the mixed integer programming model with the objective of minimizing the makespan for Om(P)|r, aN. 1,pmtn\Cmax problems was established, which was used as foundation to develope the maximum flow model for Om(P)|r, aN 1, pmtn|C, problem. Then, the makespan of Om(P)|r, aN.1, pmtn|Cmax problem can be got by maximum flow algorithm, which were the lower bound on makespan in Om(P)|r, aN. 1|Cmax problem.
5. We developed a dense scheduling algorithm for Om(P)|r. aN.1|Cmax problem with a worst-case performance ratio less than 2. In Om(P)|r, aN.1|Cmax problem, each machine has a fixed and known unavailable period, and job interrupted by unavailable period can continue to be processed on the same machine after the machine has become available. In this thesis, the unavailable periods were treated as special jobs, which were called virtual jobs. In order to reduce the difficulty, resource matchings were done firstly without consideration of virtual job. Then, the relationship between makespan of resource matching and virtual job was analysis, and three modes were got. The method Based on the analysis, a dense algorithm for Om(P)|r, aN.1|Cmax problem were developed.
The performances of the three algorithms developed in this paper were analysis from two aspects:firstly, worse case ratio and time complexity were analysis; then, the validity of the developed scheduling algorithms were illustrated by randomly generated examples.
引文
[1]Graves S C. A review of production scheduling. Operations Research.1981.29(4): 646-675P
[2]邢文训,谢金星.现代优化设计方法(第二版),北京：清华大学出版社,2005：28-34
[3]Prins C. Competitive genetic algorithms for the open-shop scheduling problem. Mathematical Methods of Operations Research.2000,52:389-411P
[4]Conway R W, Maxwell, W L, Miller, L W. Theory of Scheduling; Massachusetts Addison Wesley Publishing Company,1968:42-51P
[5]Colemman E G. Computer and Job Shop Scheduling Theory. Wiley, New York:A Wiley-Interscience Publication,1976:289-296 P
[6]Gonzalez T, Sahni S. Open shop scheduling to minimize finish time. Journal of the ACM (JACM) archive.1976,23(4):665-679P
[7]Du J Z, Leung Y T. Minimizing mean flow time in two-machine open shops and flow shops. Journal of Algorithms.1993,14:24-44P
[8]Liu C Y. Bulfin R L. On the complexity of preemptive open-shop scheduling problems. Operations Research Letter.1985,4:71-74P
[9]Brasel H, Hennes H. On the open-shop problem with preemption and minimizing the average completion time. European Journal of Operational Research.2004,157(3): 607-619P
[10]Brasel H, Shakhlevich N. On the solution region for certain scheduling problems with preemption. Annals of Operations Research.1998,83(0),1-22P
[11]Lin H T, Lee H T, Pan W J, et al. Heuristics for scheduling in a no-wait open shop with movable dedicated machines. International Journal of Production Economics. 2008,111(2):368-377P
[12]Werra D, Kis T, Kubiak W. Preemptive open shop scheduling with multiprocessors: polynomial cases and applications. Journal of Scheduling.2008,11(1):75-83P
[13]Queyranne M, Sviridenko M. A (2+ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective. Journal of Algorithms.2002, 45(2):202-212P
[14]Gandhi R, Halldorsson M M, Kortsarz G, Shachnai H. Improved results for data migration and open shop scheduling. ACM Transactions on Algorithms.2006.2(1): 1-15P
[15]Lushchakova I N. Two machine preemptive scheduling problem with release dates. equal processing times and precedence constraints. European Journal of Operational Research.2006.171(1):107-122P
[16]Breit J. Schmidt G. Strusevich V A. Two-machine open shop scheduling with an availability constraint. Operations Research Letters.2001.29(2):65-77P
[17]Liu C Y. Bulfin R L. Scheduling ordered open shops. Computers & Operations Research.1987.14(3):257-264P
[18]Drobouchevitch. I G. Strusevich. V A. Two-stage open shop scheduling with a bottleneck machine. European Journal of Operational Research.2001.128:159-174P
[19]Liaw C F. An efficient tabu search approach for the two-machine preemptive open shop scheduling problem. Computers and Operations Research.2003.30(14): 2081-2095P
[20]Liaw C F. Scheduling preemptive open shops to minimize total tardiness. European Journal of Operational Research.2005.162(1):173-183P
[21]俞国胜.一个多项式时间可解的自由作业排序问题.应用数学学报.1996,19(3)：469-472页
[22]Achugbue J O. Chin F Y. Scheduling the open shop to minimize mean flow time. S1AM J. on Computing.1982.11:709-720P
[23]Gonzalez T. Sahni S. Open shop scheduling to minimize finish time. ACM.1976.23: 665-679P
[24]Liu C Y. Bulfin R L. Scheduling open shops with unit execution times to minimize functions of due dates. Operations Research.1988.36(4):553-559P
[25]Brucker P. Jurisch B. Tautenhahn T. Werner F. Scheduling unit time open shops to minimize the weighted number of late jobs. Operations Research Letters.1993.14(5): 245-250P
[26]Baki M F. Vickson R G. One-Operator.two-machine open shop and flow shop problems with setup times for machines and weighted number of tardy jobs objective. Optimization Methods and Software.2004.19(2):165-178P
[27]Kyparisis. G J. Koulamas C. Flow shop and open shop scheduling with a critical machine and two operations per job. European Eurnal of Operational Research.2000. 127:120-125P
[28]Brucker P. Hurink J. Jurisch B. Wostmann B. A branch & bound algorithm for the open-shop problem. Discrete Applied Mathematics.1997.76:43-59P
[29]Liaw C F. Cheng C Y. The total completion time open shop scheduling problem with a given sequence of jobs on one machine. Computers & Operations Research.2002.29: 1251-1266P
[30]Ulrich D. Erwin P. loan P H. Solving the open shop scheduling problem. Journal of Scheduling.2001.4(3):157-174P
[31]Fang H L. Ross P. Corne D. A promising hybrid GA/heuristic approach for open-shop scheduling problems.1 lth European Conference on Artificial Intelligence. Amsterdam. The Netherlands.1994. Springer.1995:590-594P
[32]Li aw C F. A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research.2000.124(15):28-42P
[33]Senthilkumar P. Shahbudeen P. GA based heuristic for the open job shop scheduling problem. International Journal of Advanced Manufacturing Technology.2006.30: 297-301P
[34]Khuri S. Miryala S R. Genetic algorithm for solving open shop scheduling problems. Lecture Notes in Computer Science.1999.1695:357-368P
[35]Lowa C. Yeha Y. Genetic algorithm-based heuristics for an open shop scheduling problem with setup processing and removal times separated. Robotics and Computer-Integrated Manufacturing.2009.25:314-322P
[36]Blum C. Beam-ACO-Hybridizing ant colony optimization with beam search: an application to open shop scheduling. Computers & Operation.2005.32:1565-1591P
[37]Sha D Y. Hsu C Y. A new particle swarm optimization for the open shop scheduling problem. Computers & Operations Research.2008.35:3243-3261 P
[38]Sha D Y. Lin H H. Hsu C Y. A modified particle swarm optimization for multi-objective open shop scheduling. Proceedings of the International MultiConference of Engineers and Computer Scientist. Hong Kong. Newswood Limited,2010:1-5P
[39]高亮.高海兵.周驰.基于粒子群优化的开放式车间调度.机械工程学报.2006.42(2)：129-134贝
[40]陈荣军.工件有到达时间的两机器自由作业稠密间间表.运筹学学报.2003.7(1)：73-77页
[41]Chen B. Strusevich V A. Approximation algorithms for three machine open shop scheduling. Journal on Computing.1993.5:321-326P
[42]陈荣军,俞文.有到达时间的三机器自由作业稠密时间表性能比.数学理论与用.2003,23(2)：1-5页
143] Chen B. Yu W. How good is a dense shop schedule? Acta Mathematical Application. 2001.17(1)：121-128P
[44]陈秀宏.俞文鱿.自由作业稠密时间表的性能比上界.华东理工大学学报.2000.26(6)：670-674页
[45]陈荣军,唐国春.自由作业稠密时间表的性质研究.数学的实践与认识.2009.39(5)：166-173页
[46]陈荣军,唐国春.自由作业加工总长排序问题的稠密时间表.系统工程.2007.25(9)：107-110页
[47]项思明,唐国春.加工时间依赖于机器的自由作业序问题.运筹学学报.1998.2(1)：71-78页
[48]杨益民.关于一类两台机器自由作业的排序问题.系统工程学报.2007.22(3)：287-292页
[49]Modarres M. Ghandehari M. Applying circular doloring to open shop scheduling Civil and Mechanical Engineering.2008.15(5):652-660P
[50]Tang L. Bai D. A new heuristic for open shop total completion time problem. Applied Mathematical Modeling.2010.34:735-743P
[51]刘朝晖.俞文鱿.关于工件组的两机自由作业时间表问题.华东理工大学学报.2000.26(6)：665-669页
[52]韩兵.席裕庚.多机器总完成时间和makespan近似最优的开放式车间调度方法.控制理论与应用.2003,Vol.20(6)：859-864页
[53]Brasel H, Herms A. Morig M. Tautenhahn T. Tusch J. Werner F. Heuristic constructive algorithms for open shop scheduling to minimize mean flow time. European Journal of Operational Research.2008.189(3):856-870P
[54]Sevastianov S V. Woeginger G J. Linear time approximation scheme for the multiprocessor open shop problem. Discrete Applied Mathematics.2001.114(1-3): 273-288P
[55]Adiri I. Amit N. Openshop and flowshop scheduling to minimize sum of completion times. Computers & Operations Research.1984.11(3):275-284P
[56]Masuda T. Hiroaki I. Two machine open shop scheduling problem with bi-criteria. Discrete Applied Mathematics.1994.52:253-259P
[57]Kyparisis G.J. Koulamas C. Open shop scheduling with makespan and total completion time criteria. Computers & Operations Research.2000.27:15-27P
[58]Gupta.J N D. Werner F. Wulkenhaar G. Two-machine open shop scheduling with secondary criterion. International Transactions in Operational Research.2003.10(3): 267-294P
[59]Seyed H H D. Amir A I. Mohsen A S. Minimizing weighted mean flow time in open shop scheduling with time-dependent weightsand intermediate storage cost. International Journal on Computer Science and Engineering.2010.2(3):457-460P
[60]Mao W Z. Multi-operation multi-machine scheduling. Lecture Notes in Computer Science.1995.919:33-38P
[61]Jansen K. Sviridenko M I. Polynomial time approximation schemes for the multiprocessor open and flow shop scheduling problem. Lecture Notes in Computer Science.2000.1770/2000.455-465P
[62]Matta M E. A genetic algorithm for the proportionate multiprocessor open shop. Computers & Operations Research. September 2009.36(9):2601-2618P
[63]Matta M E. Elmaghraby S E. Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop. European Journal of Operational Research. 2010.201(3):720-728P
[64]Chen B. Strusevich V A. Worst-case analysis of heuristics for open shops with parallel machines. European Journal of Operational Research 1993.70:379-390P
165] Schuurman P. Woeginger G J. Approximation algorithms for the multiprocessor open shop scheduling problem. Operations Research Letters. May 1999.24(4):157-163P
[66]Doulabi S H H. A mixed integer linear formulation for the open, shop earliness-tardiness scheduling problem. Applied Mathematical Sciences.2010.4(35): 1703-1710P
[67]Allaoui H. Artiba A. Goncalves G. Elmaghraby S E. Scheduling n jobs and preventive maintenance in a single machine subject to breakdowns to minimize the expected total earliness and tardiness costs. Proceedings of the 17th World Congress the International Federation of Automatic Control. Korea. World Congress.2008:15843-15848P
[68]Pinedo M. Scheduling:Theory. Algorithms and Systems. New Jersey:Prentice Hall. 2002:1-20.75-96.148-160.395-399P
[69]Kubiak W. Blazewicz J. Formanowicz P. Breit J. Schmidt G. Two-machine flow shops with limited machine availability. European Journal of Operational Research.2002. 136(3):528-540P
[70]Chen J S. Using integer programming to solve the machine scheduling problem with a flexible maintenance activity. Journal of Statistics & Management Systems.2006.9: 87-104P
[711 Lee C Y. Machine scheduling with an availability constraint. Journal of Global Optimization.1996.9:363-382P
[72]Lee C Y. Two-machine flowshop scheduling with availability constraints. European Journal of Operational Research.1999.114:420-429P
[73]Kubzin M A. Potts C N. Strusevich V A. Approximation results for flow shop scheduling problems with machine availability constraints. Computers & Operations Research.2009.36:379-390P
[74]Sadfi C. Kacem 1. Wei L. Total weighted completion scheduling problem with availability constraints. Computers & Industrial Engineering.2009:134-137P
[75]Megow N. Verschae J. Short note on scheduling on a single machine with one non-availability period. European Journal of Operational Research.2009.23:21-26P
[76]马英.杨善林.储诚斌.机器在一段时间不可用条件下的单机调度问题.合肥工业大学学报.2007.30(8)：1010-1014页
[77]马英,左春荣.带不可用时间窗和恶化加工时间的几个多项式可解问题.合肥业大学学报.2009,32(3)：378-382页
[78]Ji M. He Y. Cheng T C E. Scheduling linear deteriorating jobs with an availability constraint on a single machine. Theoretical Computer Science.2006.362(1):115-126 P
[79]Mellouli A Sadfi C. Chu C B. Kacem I. Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times. European Journal of Operational Research.2009.197:1150-1165P
[80]李红英.苏纯洁.机器使用有限制的两台同类机排序.华东理工大学学报.2005,31(4)：512-516页
[81]马英,左春荣.杨善林.带不可用时间窗的两台同类机加权完工时间和调度.中国科学技术大学学报.2009.39(6)：665-671贝
[82]Formanowicz P. Selected deterministic scheduling problems with limited machine abailability. Pro Dialog.2001.13:91-105P
[83]Aggoune R. Minimizing the makespan for the flow shop scheduling problem with availability constraints. European Journal of Operational Research.2004.53: 534-543P
[84]Yao X D. Xie X L. Fu M C. Marcus S I. Optimal joint preventive maintenance and production policies. Naval Research Logistics.2005.52:668-681P
[85]廖丽满.黄俊维.机器使用限制下双阶段混合型流程工厂之排程Journal of Technology.2010.25(3):195-203页
[86]Paz P G. Jose M F. Scheduling permutation flowshops with initial availability constraint: Analysis of solutions and constructive heuristics. Computers & Operations Research.2009,36:2866-2876P
[87]Azem S, Aggoune R, Dauzere-Peres S. Disjunctive and time-indexed formulations for non-preemptive job shop scheduling with resource availability constraints. Industrial Engineering and Engineering Management,2007 IEEE International Conference on, Singapore,2007. IEEE IEEM,2007:787-791P
[88]Ploydanai K, Mungwattana A. Algorithm for solving job shop scheduling problem based on machine availability constraint. International Journal on Computer Science and Engineering.2010,2(5):1919-1925P
[89]Aggoune R. An improved solution algorithm for two-job shop scheduling problems with availability constraints. Proceedings of the International ZMultiConference of Engineers and Computer Scientists,2010. Hong Kong, IMECS 2010:25-30P
[90]Yahyaoui A, Fnaiech N, Fnaiech F. New shifting method for job shop scheduling subject to invariant constraints of resources availability.IEEE IECON,2009: 3387-3392
[91]Taghavi-Fard M T, Saidy H R D. Flexible job shop scheduling under availability constraints. Journal of Industrial Engineering International.2009,5(8):52-60P
[92]Breit J, Schmidt G. Non-preemptive two-machine open shop scheduling with non-availability constraints. Math Meth Oper Res.2003,57:217-234P
[93]蒋义伟.可中断平行机排序问题研究.浙江大学博士论文.2007：24-26页
[94]Harris T E, Ross F S. Foundamentals of a method for evaluating rail net capacities, Research Memorandum RM-1573, The RAND Corporation, Santa Monica,California,1955:63-71P
[95]阿胡亚(Ahuja R K)等.网络流：理论、算法与应用(英文版).北京：机械工业出版社,2005：1-86,166-288页
[96]Ford L R, Fulkerson D R. Maximum flow through a network. Canadian Journal of Math.1956, (8):399-404P
[97]Edmonds J, Karp R M. Theoretical improvements in algorithmic efficiency for networks flow problems. J Assoc Comput Mach.1972,19(2):248-264P
[98]Ahuja R K, Orlin J B. Distance-directed augmenting path alogorithms for the maximum flow problem. Naval Research Logistics Quarterly.1991,38(2):413-430P
[99]Dinic E A. Algorithm for Solution of a Problem of maximum flow in networks with power estimation. Soviet Math Dokl.1970.01(11):1277-1280P
[100]Karzanov A V. Determining the maximum flow in a network by the method of preflows. Soviet Math Dokl.1974. (15):434-437P
[101]Goldberg A V. Tarjan R E. A new approach to the maximum flow problem. Assoc Comput Mach.1988.35(4):921-940P
[102]张宪超.网络最大流问题算法研究.中国科技大学博士论文.2000：21-68页
[103]张宪超,陈国良,万颖瑜.网络最大流问题研究进展.计算机研究与发展.2003,40(9)：1281-1292页
[104]Gharbi A. Haouari M. Optimal parallel machines scheduling with availability constraints. Discrete Applied Mathematics.2005.148(1):1-34P
[105]Jacek B. Maciej D. Piotr F. Wieslaw K. Schmidt G. Scheduling preemptable tasks on parallel processors with limited availability. Parallel Computing.2000.26(9): 1195-1211P
[106]Gupta J N D. Ruiz-Torres A J. Generating efficient schedules for identical parallel machines involving flow-time and tardy jobs'. European Journal of Operations Research.2005.167(3):679-695P
[107]喻小光,战德巨.聂兰顺.初佃辉.徐晓飞.柔性资源约束的资源水平项目调度问题.计算机集成制造系统.2010.16(9)：1967-1976页
[108]Harvey N. Ladner R. Lovasz L. Tamir T. Semi-matchings for bipartite graphs and load balancing. Journal of Algorithms.2006.59(1):53-78P
[109]Low C P. On load-balanced semi-matchings for weighted bipartite graphs. Lecture Notes in Computer Science.2006.3959:159-170P
[110]Low C P. An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs. Information Processing Letters.2006.100:154-161P
[111]Harada Y. Ono H. Sadakane K. Yamashita M. Optimal balanced semi-matchings for weighted bipartite graphs. IPSJ Digital Courier.2007.3:693-702P
[112]Horn W A. Minimizing average flow-time with parallel machines. Operations Research.1973.21(3):846-847P
[113]李文权,王炜,杜文.林忠勋.铁路技术站调机运用模型及算法.系统工程学报.2000,15(1)：38-46页
[114]Baljeet M. loanis N. Mario A N. Aggregation convergecast scheduling in wireless sensor networks. Wireless Networks.2010.17(2):319-335P
[115]Graham R L. Lawler E L. Lenstra J K. Optimization and approximation in deterministic sequencing and scheduling:a survey. Annals of Discrete Mathematics. 1979.5:287-326P
[116]Graves S. Rinnooy Kan A H G. Zipkin P H. Handbooks in operations research and management science. Vol 4:Logistics of Production and Inventory. North Holland: Elsevier,1993:59-132P
[117]Sedeno-noda A, Alcaide D, Gonzalez-martin C. Network flow approaches to pre-emptive open-shop scheduling problems with time-windows. European Journal of Operational Research.2006,174(3):1501-1518P
[118]Ciupala L A. About wave algorithms for network flows problems. International Journal of Computers.2008,2(1):291-296P
[119]Ahuja R K, Orlin J B, Stein C. Improved algorithms for bipartite network flow. SIAM Journal on Computing.1994,23(5):906-933P
[120]Barany I, Fiala T, Nearly optimum solution of multimachine scheduling problems. Szigma Mathematika Kozgazdasagi Folyoirat.1982,17:177-191P
[121]Xie T, Sung A, Qin X, Lin M, Yang L. Real time scheduling with quality of security constraints. International Journal of High Performance Computing and Networking. 2006,4(3):188-197P
[122]Rajakumar S, Arunachalam V P, Selladurai V. Workflow balancing strategies in parallel machine scheduling. The International Journal of Advanced Manufacturing Technology.2004,23:366-374P
[123]Esquivel S C, Zuppa F, Gallard R H. Multirecombinated evolutionary algorithms for the flow shop scheduling problem, Lecture Notes In Computer Science.2000,1917: 263-272P
[124]Senthilkumar P. Shahbudeen P. GA based heuristic for the open job shop scheduling problem. International Journal of Advanced Manufacturing Technology.2006,30: 297-301P
[125]Taillard E. Benchmarks for basic scheduling problems. European Journal of Operational Research.1993,64:278-285P
[126]俞文鱿,应刚.关于二台机器自由作业的总流程问题.华东理工大学应用数学研究所.运筹学学报.2003,7(1)：73-77页
[127]Simonis H. Calculating lower bounds on a resource scheduling problem. CP Workshop ASIAN,1996,30:1-12P
[128]Lee C Y. Parallel machines scheduling with non-simultaneous machine available time. Discrete Applied Mathematics.1991,30:53-61P
[2]邢文训,谢金星.现代优化设计方法(第二版),北京：清华大学出版社,2005：28-34
[3]Prins C. Competitive genetic algorithms for the open-shop scheduling problem. Mathematical Methods of Operations Research.2000,52:389-411P
[4]Conway R W, Maxwell, W L, Miller, L W. Theory of Scheduling; Massachusetts Addison Wesley Publishing Company,1968:42-51P
[5]Colemman E G. Computer and Job Shop Scheduling Theory. Wiley, New York:A Wiley-Interscience Publication,1976:289-296 P
[6]Gonzalez T, Sahni S. Open shop scheduling to minimize finish time. Journal of the ACM (JACM) archive.1976,23(4):665-679P
[7]Du J Z, Leung Y T. Minimizing mean flow time in two-machine open shops and flow shops. Journal of Algorithms.1993,14:24-44P
[8]Liu C Y. Bulfin R L. On the complexity of preemptive open-shop scheduling problems. Operations Research Letter.1985,4:71-74P
[9]Brasel H, Hennes H. On the open-shop problem with preemption and minimizing the average completion time. European Journal of Operational Research.2004,157(3): 607-619P
[10]Brasel H, Shakhlevich N. On the solution region for certain scheduling problems with preemption. Annals of Operations Research.1998,83(0),1-22P
[11]Lin H T, Lee H T, Pan W J, et al. Heuristics for scheduling in a no-wait open shop with movable dedicated machines. International Journal of Production Economics. 2008,111(2):368-377P
[12]Werra D, Kis T, Kubiak W. Preemptive open shop scheduling with multiprocessors: polynomial cases and applications. Journal of Scheduling.2008,11(1):75-83P
[13]Queyranne M, Sviridenko M. A (2+ε)-approximation algorithm for the generalized preemptive open shop problem with minsum objective. Journal of Algorithms.2002, 45(2):202-212P
[14]Gandhi R, Halldorsson M M, Kortsarz G, Shachnai H. Improved results for data migration and open shop scheduling. ACM Transactions on Algorithms.2006.2(1): 1-15P
[15]Lushchakova I N. Two machine preemptive scheduling problem with release dates. equal processing times and precedence constraints. European Journal of Operational Research.2006.171(1):107-122P
[16]Breit J. Schmidt G. Strusevich V A. Two-machine open shop scheduling with an availability constraint. Operations Research Letters.2001.29(2):65-77P
[17]Liu C Y. Bulfin R L. Scheduling ordered open shops. Computers & Operations Research.1987.14(3):257-264P
[18]Drobouchevitch. I G. Strusevich. V A. Two-stage open shop scheduling with a bottleneck machine. European Journal of Operational Research.2001.128:159-174P
[19]Liaw C F. An efficient tabu search approach for the two-machine preemptive open shop scheduling problem. Computers and Operations Research.2003.30(14): 2081-2095P
[20]Liaw C F. Scheduling preemptive open shops to minimize total tardiness. European Journal of Operational Research.2005.162(1):173-183P
[21]俞国胜.一个多项式时间可解的自由作业排序问题.应用数学学报.1996,19(3)：469-472页
[22]Achugbue J O. Chin F Y. Scheduling the open shop to minimize mean flow time. S1AM J. on Computing.1982.11:709-720P
[23]Gonzalez T. Sahni S. Open shop scheduling to minimize finish time. ACM.1976.23: 665-679P
[24]Liu C Y. Bulfin R L. Scheduling open shops with unit execution times to minimize functions of due dates. Operations Research.1988.36(4):553-559P
[25]Brucker P. Jurisch B. Tautenhahn T. Werner F. Scheduling unit time open shops to minimize the weighted number of late jobs. Operations Research Letters.1993.14(5): 245-250P
[26]Baki M F. Vickson R G. One-Operator.two-machine open shop and flow shop problems with setup times for machines and weighted number of tardy jobs objective. Optimization Methods and Software.2004.19(2):165-178P
[27]Kyparisis. G J. Koulamas C. Flow shop and open shop scheduling with a critical machine and two operations per job. European Eurnal of Operational Research.2000. 127:120-125P
[28]Brucker P. Hurink J. Jurisch B. Wostmann B. A branch & bound algorithm for the open-shop problem. Discrete Applied Mathematics.1997.76:43-59P
[29]Liaw C F. Cheng C Y. The total completion time open shop scheduling problem with a given sequence of jobs on one machine. Computers & Operations Research.2002.29: 1251-1266P
[30]Ulrich D. Erwin P. loan P H. Solving the open shop scheduling problem. Journal of Scheduling.2001.4(3):157-174P
[31]Fang H L. Ross P. Corne D. A promising hybrid GA/heuristic approach for open-shop scheduling problems.1 lth European Conference on Artificial Intelligence. Amsterdam. The Netherlands.1994. Springer.1995:590-594P
[32]Li aw C F. A hybrid genetic algorithm for the open shop scheduling problem. European Journal of Operational Research.2000.124(15):28-42P
[33]Senthilkumar P. Shahbudeen P. GA based heuristic for the open job shop scheduling problem. International Journal of Advanced Manufacturing Technology.2006.30: 297-301P
[34]Khuri S. Miryala S R. Genetic algorithm for solving open shop scheduling problems. Lecture Notes in Computer Science.1999.1695:357-368P
[35]Lowa C. Yeha Y. Genetic algorithm-based heuristics for an open shop scheduling problem with setup processing and removal times separated. Robotics and Computer-Integrated Manufacturing.2009.25:314-322P
[36]Blum C. Beam-ACO-Hybridizing ant colony optimization with beam search: an application to open shop scheduling. Computers & Operation.2005.32:1565-1591P
[37]Sha D Y. Hsu C Y. A new particle swarm optimization for the open shop scheduling problem. Computers & Operations Research.2008.35:3243-3261 P
[38]Sha D Y. Lin H H. Hsu C Y. A modified particle swarm optimization for multi-objective open shop scheduling. Proceedings of the International MultiConference of Engineers and Computer Scientist. Hong Kong. Newswood Limited,2010:1-5P
[39]高亮.高海兵.周驰.基于粒子群优化的开放式车间调度.机械工程学报.2006.42(2)：129-134贝
[40]陈荣军.工件有到达时间的两机器自由作业稠密间间表.运筹学学报.2003.7(1)：73-77页
[41]Chen B. Strusevich V A. Approximation algorithms for three machine open shop scheduling. Journal on Computing.1993.5:321-326P
[42]陈荣军,俞文.有到达时间的三机器自由作业稠密时间表性能比.数学理论与用.2003,23(2)：1-5页
143] Chen B. Yu W. How good is a dense shop schedule? Acta Mathematical Application. 2001.17(1)：121-128P
[44]陈秀宏.俞文鱿.自由作业稠密时间表的性能比上界.华东理工大学学报.2000.26(6)：670-674页
[45]陈荣军,唐国春.自由作业稠密时间表的性质研究.数学的实践与认识.2009.39(5)：166-173页
[46]陈荣军,唐国春.自由作业加工总长排序问题的稠密时间表.系统工程.2007.25(9)：107-110页
[47]项思明,唐国春.加工时间依赖于机器的自由作业序问题.运筹学学报.1998.2(1)：71-78页
[48]杨益民.关于一类两台机器自由作业的排序问题.系统工程学报.2007.22(3)：287-292页
[49]Modarres M. Ghandehari M. Applying circular doloring to open shop scheduling Civil and Mechanical Engineering.2008.15(5):652-660P
[50]Tang L. Bai D. A new heuristic for open shop total completion time problem. Applied Mathematical Modeling.2010.34:735-743P
[51]刘朝晖.俞文鱿.关于工件组的两机自由作业时间表问题.华东理工大学学报.2000.26(6)：665-669页
[52]韩兵.席裕庚.多机器总完成时间和makespan近似最优的开放式车间调度方法.控制理论与应用.2003,Vol.20(6)：859-864页
[53]Brasel H, Herms A. Morig M. Tautenhahn T. Tusch J. Werner F. Heuristic constructive algorithms for open shop scheduling to minimize mean flow time. European Journal of Operational Research.2008.189(3):856-870P
[54]Sevastianov S V. Woeginger G J. Linear time approximation scheme for the multiprocessor open shop problem. Discrete Applied Mathematics.2001.114(1-3): 273-288P
[55]Adiri I. Amit N. Openshop and flowshop scheduling to minimize sum of completion times. Computers & Operations Research.1984.11(3):275-284P
[56]Masuda T. Hiroaki I. Two machine open shop scheduling problem with bi-criteria. Discrete Applied Mathematics.1994.52:253-259P
[57]Kyparisis G.J. Koulamas C. Open shop scheduling with makespan and total completion time criteria. Computers & Operations Research.2000.27:15-27P
[58]Gupta.J N D. Werner F. Wulkenhaar G. Two-machine open shop scheduling with secondary criterion. International Transactions in Operational Research.2003.10(3): 267-294P
[59]Seyed H H D. Amir A I. Mohsen A S. Minimizing weighted mean flow time in open shop scheduling with time-dependent weightsand intermediate storage cost. International Journal on Computer Science and Engineering.2010.2(3):457-460P
[60]Mao W Z. Multi-operation multi-machine scheduling. Lecture Notes in Computer Science.1995.919:33-38P
[61]Jansen K. Sviridenko M I. Polynomial time approximation schemes for the multiprocessor open and flow shop scheduling problem. Lecture Notes in Computer Science.2000.1770/2000.455-465P
[62]Matta M E. A genetic algorithm for the proportionate multiprocessor open shop. Computers & Operations Research. September 2009.36(9):2601-2618P
[63]Matta M E. Elmaghraby S E. Polynomial time algorithms for two special classes of the proportionate multiprocessor open shop. European Journal of Operational Research. 2010.201(3):720-728P
[64]Chen B. Strusevich V A. Worst-case analysis of heuristics for open shops with parallel machines. European Journal of Operational Research 1993.70:379-390P
165] Schuurman P. Woeginger G J. Approximation algorithms for the multiprocessor open shop scheduling problem. Operations Research Letters. May 1999.24(4):157-163P
[66]Doulabi S H H. A mixed integer linear formulation for the open, shop earliness-tardiness scheduling problem. Applied Mathematical Sciences.2010.4(35): 1703-1710P
[67]Allaoui H. Artiba A. Goncalves G. Elmaghraby S E. Scheduling n jobs and preventive maintenance in a single machine subject to breakdowns to minimize the expected total earliness and tardiness costs. Proceedings of the 17th World Congress the International Federation of Automatic Control. Korea. World Congress.2008:15843-15848P
[68]Pinedo M. Scheduling:Theory. Algorithms and Systems. New Jersey:Prentice Hall. 2002:1-20.75-96.148-160.395-399P
[69]Kubiak W. Blazewicz J. Formanowicz P. Breit J. Schmidt G. Two-machine flow shops with limited machine availability. European Journal of Operational Research.2002. 136(3):528-540P
[70]Chen J S. Using integer programming to solve the machine scheduling problem with a flexible maintenance activity. Journal of Statistics & Management Systems.2006.9: 87-104P
[711 Lee C Y. Machine scheduling with an availability constraint. Journal of Global Optimization.1996.9:363-382P
[72]Lee C Y. Two-machine flowshop scheduling with availability constraints. European Journal of Operational Research.1999.114:420-429P
[73]Kubzin M A. Potts C N. Strusevich V A. Approximation results for flow shop scheduling problems with machine availability constraints. Computers & Operations Research.2009.36:379-390P
[74]Sadfi C. Kacem 1. Wei L. Total weighted completion scheduling problem with availability constraints. Computers & Industrial Engineering.2009:134-137P
[75]Megow N. Verschae J. Short note on scheduling on a single machine with one non-availability period. European Journal of Operational Research.2009.23:21-26P
[76]马英.杨善林.储诚斌.机器在一段时间不可用条件下的单机调度问题.合肥工业大学学报.2007.30(8)：1010-1014页
[77]马英,左春荣.带不可用时间窗和恶化加工时间的几个多项式可解问题.合肥业大学学报.2009,32(3)：378-382页
[78]Ji M. He Y. Cheng T C E. Scheduling linear deteriorating jobs with an availability constraint on a single machine. Theoretical Computer Science.2006.362(1):115-126 P
[79]Mellouli A Sadfi C. Chu C B. Kacem I. Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times. European Journal of Operational Research.2009.197:1150-1165P
[80]李红英.苏纯洁.机器使用有限制的两台同类机排序.华东理工大学学报.2005,31(4)：512-516页
[81]马英,左春荣.杨善林.带不可用时间窗的两台同类机加权完工时间和调度.中国科学技术大学学报.2009.39(6)：665-671贝
[82]Formanowicz P. Selected deterministic scheduling problems with limited machine abailability. Pro Dialog.2001.13:91-105P
[83]Aggoune R. Minimizing the makespan for the flow shop scheduling problem with availability constraints. European Journal of Operational Research.2004.53: 534-543P
[84]Yao X D. Xie X L. Fu M C. Marcus S I. Optimal joint preventive maintenance and production policies. Naval Research Logistics.2005.52:668-681P
[85]廖丽满.黄俊维.机器使用限制下双阶段混合型流程工厂之排程Journal of Technology.2010.25(3):195-203页
[86]Paz P G. Jose M F. Scheduling permutation flowshops with initial availability constraint: Analysis of solutions and constructive heuristics. Computers & Operations Research.2009,36:2866-2876P
[87]Azem S, Aggoune R, Dauzere-Peres S. Disjunctive and time-indexed formulations for non-preemptive job shop scheduling with resource availability constraints. Industrial Engineering and Engineering Management,2007 IEEE International Conference on, Singapore,2007. IEEE IEEM,2007:787-791P
[88]Ploydanai K, Mungwattana A. Algorithm for solving job shop scheduling problem based on machine availability constraint. International Journal on Computer Science and Engineering.2010,2(5):1919-1925P
[89]Aggoune R. An improved solution algorithm for two-job shop scheduling problems with availability constraints. Proceedings of the International ZMultiConference of Engineers and Computer Scientists,2010. Hong Kong, IMECS 2010:25-30P
[90]Yahyaoui A, Fnaiech N, Fnaiech F. New shifting method for job shop scheduling subject to invariant constraints of resources availability.IEEE IECON,2009: 3387-3392
[91]Taghavi-Fard M T, Saidy H R D. Flexible job shop scheduling under availability constraints. Journal of Industrial Engineering International.2009,5(8):52-60P
[92]Breit J, Schmidt G. Non-preemptive two-machine open shop scheduling with non-availability constraints. Math Meth Oper Res.2003,57:217-234P
[93]蒋义伟.可中断平行机排序问题研究.浙江大学博士论文.2007：24-26页
[94]Harris T E, Ross F S. Foundamentals of a method for evaluating rail net capacities, Research Memorandum RM-1573, The RAND Corporation, Santa Monica,California,1955:63-71P
[95]阿胡亚(Ahuja R K)等.网络流：理论、算法与应用(英文版).北京：机械工业出版社,2005：1-86,166-288页
[96]Ford L R, Fulkerson D R. Maximum flow through a network. Canadian Journal of Math.1956, (8):399-404P
[97]Edmonds J, Karp R M. Theoretical improvements in algorithmic efficiency for networks flow problems. J Assoc Comput Mach.1972,19(2):248-264P
[98]Ahuja R K, Orlin J B. Distance-directed augmenting path alogorithms for the maximum flow problem. Naval Research Logistics Quarterly.1991,38(2):413-430P
[99]Dinic E A. Algorithm for Solution of a Problem of maximum flow in networks with power estimation. Soviet Math Dokl.1970.01(11):1277-1280P
[100]Karzanov A V. Determining the maximum flow in a network by the method of preflows. Soviet Math Dokl.1974. (15):434-437P
[101]Goldberg A V. Tarjan R E. A new approach to the maximum flow problem. Assoc Comput Mach.1988.35(4):921-940P
[102]张宪超.网络最大流问题算法研究.中国科技大学博士论文.2000：21-68页
[103]张宪超,陈国良,万颖瑜.网络最大流问题研究进展.计算机研究与发展.2003,40(9)：1281-1292页
[104]Gharbi A. Haouari M. Optimal parallel machines scheduling with availability constraints. Discrete Applied Mathematics.2005.148(1):1-34P
[105]Jacek B. Maciej D. Piotr F. Wieslaw K. Schmidt G. Scheduling preemptable tasks on parallel processors with limited availability. Parallel Computing.2000.26(9): 1195-1211P
[106]Gupta J N D. Ruiz-Torres A J. Generating efficient schedules for identical parallel machines involving flow-time and tardy jobs'. European Journal of Operations Research.2005.167(3):679-695P
[107]喻小光,战德巨.聂兰顺.初佃辉.徐晓飞.柔性资源约束的资源水平项目调度问题.计算机集成制造系统.2010.16(9)：1967-1976页
[108]Harvey N. Ladner R. Lovasz L. Tamir T. Semi-matchings for bipartite graphs and load balancing. Journal of Algorithms.2006.59(1):53-78P
[109]Low C P. On load-balanced semi-matchings for weighted bipartite graphs. Lecture Notes in Computer Science.2006.3959:159-170P
[110]Low C P. An approximation algorithm for the load-balanced semi-matching problem in weighted bipartite graphs. Information Processing Letters.2006.100:154-161P
[111]Harada Y. Ono H. Sadakane K. Yamashita M. Optimal balanced semi-matchings for weighted bipartite graphs. IPSJ Digital Courier.2007.3:693-702P
[112]Horn W A. Minimizing average flow-time with parallel machines. Operations Research.1973.21(3):846-847P
[113]李文权,王炜,杜文.林忠勋.铁路技术站调机运用模型及算法.系统工程学报.2000,15(1)：38-46页
[114]Baljeet M. loanis N. Mario A N. Aggregation convergecast scheduling in wireless sensor networks. Wireless Networks.2010.17(2):319-335P
[115]Graham R L. Lawler E L. Lenstra J K. Optimization and approximation in deterministic sequencing and scheduling:a survey. Annals of Discrete Mathematics. 1979.5:287-326P
[116]Graves S. Rinnooy Kan A H G. Zipkin P H. Handbooks in operations research and management science. Vol 4:Logistics of Production and Inventory. North Holland: Elsevier,1993:59-132P
[117]Sedeno-noda A, Alcaide D, Gonzalez-martin C. Network flow approaches to pre-emptive open-shop scheduling problems with time-windows. European Journal of Operational Research.2006,174(3):1501-1518P
[118]Ciupala L A. About wave algorithms for network flows problems. International Journal of Computers.2008,2(1):291-296P
[119]Ahuja R K, Orlin J B, Stein C. Improved algorithms for bipartite network flow. SIAM Journal on Computing.1994,23(5):906-933P
[120]Barany I, Fiala T, Nearly optimum solution of multimachine scheduling problems. Szigma Mathematika Kozgazdasagi Folyoirat.1982,17:177-191P
[121]Xie T, Sung A, Qin X, Lin M, Yang L. Real time scheduling with quality of security constraints. International Journal of High Performance Computing and Networking. 2006,4(3):188-197P
[122]Rajakumar S, Arunachalam V P, Selladurai V. Workflow balancing strategies in parallel machine scheduling. The International Journal of Advanced Manufacturing Technology.2004,23:366-374P
[123]Esquivel S C, Zuppa F, Gallard R H. Multirecombinated evolutionary algorithms for the flow shop scheduling problem, Lecture Notes In Computer Science.2000,1917: 263-272P
[124]Senthilkumar P. Shahbudeen P. GA based heuristic for the open job shop scheduling problem. International Journal of Advanced Manufacturing Technology.2006,30: 297-301P
[125]Taillard E. Benchmarks for basic scheduling problems. European Journal of Operational Research.1993,64:278-285P
[126]俞文鱿,应刚.关于二台机器自由作业的总流程问题.华东理工大学应用数学研究所.运筹学学报.2003,7(1)：73-77页
[127]Simonis H. Calculating lower bounds on a resource scheduling problem. CP Workshop ASIAN,1996,30:1-12P
[128]Lee C Y. Parallel machines scheduling with non-simultaneous machine available time. Discrete Applied Mathematics.1991,30:53-61P