摘要
在传统的调度理论研究中,待加工任务的加工时间通常被看作是固定且已知的离散量,调度算法仅仅需要确定任务的机床分配,以及每台机床上任务的加工顺序,以实现对于特定目标函数的优化。然而,在很多现实生产环境中,任务加工时间可以通过在加工过程中分配和消耗一定数量的额外资源加以控制。这些资源包括人力资源、电力、燃气和资金预算等。可控任务加工时间的引入能够减少调度理论研究与现实生产应用之间的差异,同时增加调度算法的灵活性。然而,由于加入了更多的计算变量,调度问题的计算复杂度也随之急剧增加。事实上,作为传统的固定任务加工时间条件下的调度问题的扩展,绝大多数任务加工时间可控条件下的调度问题均具有NP难度。由于这一原因,尽管这一领域中最早的研究报告可追溯到1980年,就目前为止,多数研究仍然主要集中于相对较为简单的问题之上,其中绝大多数为单机床环境下的调度问题,与实际的应用需求相比,仍有较大差距。
理论研究与应用需求之间的巨大差距促成了本文的研究工作。本文所做研究主要集中于若干相对而言较为接近现实生产环境的,任务加工时间可控条件下的单机床调度问题与多机床调度问题。由于这类问题大都具有MP难度,和相对较为复杂的约束条件,难以在有限时间内求得最优解,因此本文致力于结合现代优化算法和经典优化算法,力图在可接受计算时间内,为具有现实意义的大规模问题构造令人满意的近优解。本文所完成的工作仅仅是这一充满挑战与乐趣的研究领域中的一小部分,包括了以下内容：
1.单机床环境下,具有独立任意到达时间和交货日期的任务的调度问题。调度算法旨在避免交货延时,同时最小化总资源消耗量。
(a)首先,为离散时间条件下、连续时间线性资源消耗函数条件下,和连续时间非线性凸资源消耗函数条件下的资源分配问题构造了多项式时间最优算法；
(b)其次,构造了用于搜索加工序列的分支定界算法,该算法能够在可接受计算时间内为中小规模问题构造最优解；
(c)最后,构造了用于搜索加工序列的禁忌搜索算法,该算法能够在可接受计算时间内为较大规模问题构造最优解或近优解。
2.单机床环境下,最小化总加工延迟时间调度问题。调度算法旨在控制所有任务的总交货延迟时间不大于一定预设值,同时最小化总资源消耗量。文中为所有任务具有相同交货时间这一特例构造了多项式时间最优算法。
3.并行机床环境下,具有独立任意到达时间和交货日期的任务的调度问题。调度算法旨在避免交货延时,同时最小化总资源消耗量。文中通过禁忌搜索算法对单机床调度算法加以扩展,使之能够在可接受计算时间内为较大规模问题构造最优解或近优解。
4.并行机床环境下,具有加工顺序约束条件的任务调度问题。调度算法旨在提供最晚完成时间不大于预设值的解,同时最小化总资源消耗量。(a)首先,在离散时间条件下构造了一个基于贪婪法则的资源分配算法；(b)其次,构造了一个禁忌搜索算法,用于在可接受计算时间内,为较大规模问题提供近优解。
如前所述,本文所做工作仅仅是对可控任务加工时间条件下的调度问题的初步尝试与探索,在这一领域中,仍然存在有大量的研究工作有待深入,而这也正是这一领域充满吸引力的原因所在。因此,我们将致力于在今后的工作中继续深化对于这一类问题的研究,以期在理论和实践应用中取得更大的成果。
In most traditional deterministic scheduling problems, job-processing times are re-garded as discrete constant known in advance, and the scheduling algorithm only needs to assign jobs to machines and to determine the job-processing permutation on each machine. However, in many realistic manufacturing environments, job-processing times can be con-trolled by allocating extra resource to jobs. Examples of such resource includes human resource, electricity power, gas and cash. The introduction of controllable job-processing times shortens the gap between theoretical research and realistic application, and enhances the flexibility of the scheduling algorithm. However, as more decision variables are added, the computational complexity of the scheduling problems also increases greatly. In fact, as the generalization of the traditional scheduling problems that have constant job-processing times, most of the scheduling problems with controllable job-processing times are NP-hard. For this reason, although the first research report of this field can be traced back to 1980, so far most research work still concerns on relatively simple scheduling problems, most of them focus on single machine environments.
The great gap between realistic requirement and theoretical research inspired our work. In this paper, we concern on several single machine and multi-machine deterministic scheduling problems with controllable job-processing times, and provide optimal or near optimal solution for problems of the real-world size. The accomplished work is only the start of a long-term research on this interesting and valuable field, further research work will be continued. Following research result will be introduced in this paper:
1. Single machine scheduling with independent job release dates and due dates. The scheduling algorithm is intended to avoid delay of shipment and to minimize total resource consumption.
(a) We introduced polynomial time optimal resource allocation algorithms for schedul-ing problems in discrete time environment, and problems in continuous time envi- ronment with linear resource consumption function and non-linear convex resource consumption function;
(b) We introduced a branch and bound algorithm for searching for the optimal job-processing permutation for small-and media-sized problems;
(c) We introduced a tabu-search algorithm for searching for the optimal or near op-timal job-processing permutation for the real-world-sized problems.
2. Single machine scheduling with total tardiness criteria. The scheduling algorithm is intended to make sure that total tardiness will not exceed a given requirement while the total resource consumption is minimized. We introduced a polynomial time optimal algorithm for the special case where jobs have a common due date.
3. Parallel machine scheduling with independent job release dates and due dates. The algorithm is intended to avoid delay of shipment and to minimize total resource con-sumption. We extended the researching result on single machine scheduling problem to parallel machines, and introduced a tabu-search algorithm to provide optimal or near optimal solution for the real-world-sized problems.
4. Parallel machine scheduling with job-processing precedence constraints. The algo-rithm is intended to provide a solution with makespan no larger than the requirement and minimum total resource consumption.
(a) We introduced a greedy algorithm for the resource allocation problem in discrete time environment;
(b) We introduced a tabu-search algorithm to provide solution for real-world-sized problems.
The research work of this paper is just the beginning of our work in the field of scheduling jobs with controllable job-processing times. In this field, there exist still a great number of research work that is waiting for exploration, which is the main reason that the field is full of attraction. Thus, in the following work we will devote ourselves deeper into this field, and work for further achievement both in theory and in application.
引文
[1]R. Armstrong, S. Gu, L. Lei. Solving a class of two-resource allocation problems by equivalent load method[J]. Journal of Operations Research Society.1997,48(8):818-825.
[2]J.R. Barker, G.B. McMahon. Scheduling the general job-shop[J]. Management Science.1985, 31(5):594-598.
[3]J.W. Barnes. A tabu search experience in production scheduling[J]. Annals of Operations Re-search.1993,41(3):141-156.
[4]E. Balas. Project scheduling with resource constraints[J]. Applications of Mathematical Program-ming Technique.1968,37(5):156-172.
[5]C.E. Bell, K. Park. Solving resource-constrained project scheduling problems by A* search [J]. Naval Research Logistics Quarterly.1990,37(1):61-84.
[6]D. Biskup, H. Jahnke. Common due date assignment for scheduling on a single machine with jointly reducible processing times[J]. International Journal of Production Economics.2001, 69(3):317-322.
[7]R.E. Burkard, Y. He. A note on multifit scheduling for uniform machines [J]. Computing.1998, 61(3):277-283.
[8]U. Bilge, F. Kirac, M. Kurtulan, P. Pekgun. A tabu search algorithm for parallel machine total tardiness problem [J]. Computers and Operations Research.2004,31(3):397-414.
[9]J. Carlier. The one-machine sequencing problem[J]. European Journal of Operations Research. 1982, 11(1):42-47.
[10]T.C.E. Cheng, Z.L. Chen, C.L. Li. Single-machine scheduling with trade-off between number of tardy jobs and resource allocation [J]. Operations Research Letters.1996,19(5):237-242.
[11]T.C.E. Cheng, M.Y. Kovalyov. Single machine batch scheduling with deadlines and resource dependent processing times[J]. Operations Research Letters.1995,17(5):243-249.
[12]T.C.E. Cheng, A. Janiak, M.Y. Kovalyov. Single machine batch scheduling with resource depen-dent setup processing times[J]. European Journal of Operations Research.2004,135(1):177-183.
[13]T.C.E. Cheng, M.Y. Kovalyov, N.V. Shakhlevich. Scheduling with controllable release dates and processing times:Makespan minimization[J]. European Journal of Operations Research.2006, 175(1):751-768.
[14]T.C.E. Chenga, C. Oguz, X.D. Qi. Due-date assignment and single machine scheduling with compressible processing times[J]. International Journal of Production Economics.1996,43(1):107-113.
[15]T.C.E Cheng, M.Y. Kovalyov, N.V. Shakhlevich. Scheduling with controllable release dates and processing times:Total completion time minimization[J]. European Journal of Operations Re-search.2006,175(2):769-781.
[16]N. Christofides, R. Alvarez-Valdes, J.M. Tamarit. Project scheduling with resource constraints: a branch and bound approach[J]. European Journal of Operations Research.1987,29(3):262-273.
[17]Z-L. Chen, W.B. Powell. Solving parallel machine scheduling problems by column generation[J]. Informs Journal of Computing.1999, 11(1):78-94.
[18]Z-L. Chen. Simultaneous job scheduling and resource allocation on parallel machines[J]. Annals of Operations Research.2004,129(4):135-153.
[19]Z-L. Chen, Q. Lu, G. Tang. Single machine scheduling with discretely controllable processing times[J]. Operations Research Letters.1997,21(2):69-76.
[20]R. Cheng, M. Gen, T. Tozawa. Minmax earliness tardiness scheduling in identical parallel machine system using genetic algorithms [J]. Computers & Industrial Engineering.1995,29(1):513-517.
[21]D. Cao, M. Chen, G. Wan. Parallel machine selection and job scheduling to minimize machine cost and job tardiness[J]. Computers and Operations Research.2005,32(8):1995-2012.
[22]J. Du, J.Y.-T. Leung. Minimizing total tardiness on one macine is NP-hard. Mathematics of Operations Research [J].1990,15(1):483-495.
[23]J. Du, J.Y.-T. Leung. Scheduling tree-structured tasks on two processors to minimize schedule length[J]. SIAM Journal of Discrete Mathematics.1989,2(2):179-196.
[24]M. Dorigo, V. Maniezzo, A. Colorni. Ant system:optimization by a colony of cooperating agents[J]. IEEE Transactions on System Man, and Cybernetics-Part B.1996,26(1):29-41.
[25]R. Frank. A search procedure for Hamilton paths and circuits [J]. Journal of the Association for Computing Machinery.1974,44(4):576-580.
[26]D.R. Fulkerson. A network computation for project cost curves[J]. Management Science.1961, 7(2):167-178.
[27]R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G Kan Rinnooy. Optimization and approximation in deterministic sequencing and scheduling:a survey [J]. Annals of Discrete Mathematics.1979, 5(1):287-326.
[28]R.L. Graham. Bounds for certain multiprocessing anomalies [J]. Bell System Technical Journal. 1966,45(9):1563-1581.
[29]F. Glover. Tabu search. Part Ⅰ[J]. ORSA Journal of Computing.1989, 1(1):190-206.
[30]F. Glover. Tabu search. Part Ⅱ[J]. ORSA Journal of Computing.1990,2(1):4-32.
[31]F. Glover. Tabu search:a tutorial[J]. Interfaces.1990,29(4):74-94.
[32]V. Gordon, J.M. Proth, C.B. Chu. A survey of the state-of-the-art of common due date assignment and scheduling research[J]. European Journal of Operations Research.2002,139(1):1-25.
[33]V. Gordon, J.M. Proth, C.B. Chu. Due date assignment and scheduling: SLK, TWK and other due date assignment models[J]. Production Planning and Control.2002,13(1):117-132.
[34]T. Gonzalez, S. Sahni. Flowshop and jobshop schedules:complexity and approximation[J]. Op-erations Research.1978,26(1):36-52.
[35]J.N.D. Gupta, K.Kruger, V. Lauff, F. Werner, Y.N. Sotskov. Heuristics for hybrid flow shops with controllable processing times and assignable due dates[J]. Computers and Operations Research. 2002,29(10):1417-1439.
[36]S.L. Hakimi. Recent progress and new problems in applied graph theory[C]. IEEE Regio Six Conference Record.1966,3(1):635-643.
[37]D. Hochbaum. Approximation algorithms for NP-hard problems[M]. Boston:PWS Publishing Company,1995.
[38]H. Hoogeveen, G.J. Woeginger. Some comments on sequencing with controllable processing times[J]. Computing.2002,68(2):181-192.
[39]H. Hoogeveen. Multicriteria scheduling [J]. European Journal of Operations Research.2005, 167(3):592-623.
[40]A. Janiak. One-machine scheduling problems with resource constraints[J]. Lecture Notes in Con-trol and Information Sciences.1986,84(1):358-364.
[41]A. Janiak. Minimization of the blooming mill standstills-mathematical model, suboptimal al-gorithms[J]. Mechanika.1989,8(2):37-49.
[42]A. Janiak. Single machine scheduling problem with common deadline and resource dependent release dates[J]. European Journal of Operations Research.1991,53(3):317-325.
[43]A. Janiak, E. Kozan, M. Lichtenstein, C. Oguz. Metaheuristic approaches to the hybrid flow shop scheduling problem with a cost-related criterion[J]. International Journal of Production Economics.2007,105(2):407-424.
[44]A. Janiak, M.Y. Kovalyov. Single machine group scheduling with resource dependent setup and processing times[J]. European Journal of Operations Research.2005,162(1):112-121.
[45]A. Janiak. Minimization of the makespan in a two-machine problem under given resource con-straints[J]. European Journal of Operations Research.1998,107(1):325-337.
[46]K. Jansen, M. Mastrolilli. Approximation schemes for parallel machine scheduling problem with controllable processing times[J]. Operations Research.2004,31(1):1565-1581.
[47]K. Jansen, M. Mastrolilli, R. Solis-Oba. Approximation schemes for job shop scheduling problems with controllable processing times[J]. European Journal of Operations Research.2005,167(2):297-319.
[48]J. Jungwattanakita, M. Reodechaa, P. Chaovalitwongsea, F. Wernerb. A comparison of scheduling algorithms for flexible flow shop problems with unrelated parallel machines, setup times, and dual criteria[J]. Computers and Operations Research.2007,31(1):314-334.
[49]M.R. Garey, D.S. Johnson. "Strong" NP-completeness results:motivation, examples, and impli-cations [J]. Journal of the ACM.1978,25(3):499-508.
[50]M. Kaspi, D. Shabtay. A bicriterion approach to time cost trade-offs in scheduling with con-vex resource-dependent job processing times and release dates[J]. Computers and Operations Research.2006,33(1):3015-3033.
[51]R.K. Kayan, M.S. Akturk. A new bounding mechanism for the CNC machine scheduling problems with controllable processing times[J]. European Journal of Operations Research.2005,167(3):624-643.
[52]C. Koulamas, G.J. Kyparisis. Scheduling on uniform parallel machines to minimize maximum lateness[J]. Operations Research Letters.2000,26(4):175-179.
[53]C.Y. Lee, L. Lei. Multiple-project scheduling with controllable project duration and hard resource constraint:some solvable cases [J]. Annals of Operations Research.2001,102(2):287-307.
[54]J.K. Lenstra, A.H.G. Rinnooy, P. Brucker. Computational complexity of discrete optimization problems [J]. Annals of Discrete Mathematics.1977, 1(1):343-362.
[55]Z.A. Lomnicki. A branch and bound algorithm for the exact solution of the three-machine schedul-ing problem[J]. Operational Research Quarterly,16(1):89-100.
[56]P.B. Luh, D.J. Hoitomt, E. Max and K.R. Pattipati. Parallel machine scheduling using Lagrangian relaxation [J]. Computer Integrated Manufacturing.1988,24(2):244-248.
[57]D.J. Hoitomi, P.B. Luh, E. Max, K.R. Pattipati. Scheduling jobs with simple precedence con-straints on parallel machines [J]. Control Systems Magazine, IEEE.1990,10(2):34-40.
[58]D.J. Hoitomt, P.B. Luh, K.R. Pattipati. A Lagrangian relaxation approach to job shop scheduling problems [J]. Robotics and Automation.1990:1944-1949.
[59]D.J. Hoitomi, P.B. Luh, K.R. Pattipati. A practical approach to job-shop scheduling problems[J]. Robotics and Automation.1993,9(1):1-13.
[60]E.L. Lawler. A pseudopolynomial time algorithm for sequencing jobs to minimize total tardi-ness[J]. Annals of Discrete Mathematics. Annals of Discrete Mathematics.1977,1(1):331-341.
[61]S.D. Limana, S.S. Panwalkarb, S. Thongmeea. A single machine scheduling problem with common due window and controllable processing times[J]. Annals of Operations Research.1997,70(1):145-154.
[62]M. Laguna, J.L.G. Velarde. A search heuristic for just-in-time scheduling in parallel machines[J]. Journal of Intelligent Manufacturing.1991,2(4):253-260.
[63]C.L. Monma, A. Schrijver, M.J. Todd, V.K. Wei. Convex resource allocation problems on directed acyclic graphs:duality,complexity,special cases and extensions[J]. Mathematics of Operations Research.1990,15(4):736-748.
[64]J.M. Moore. An n job, one machine sequencing algorithm for minimizing the number of late jobs[J]. Management Science.1968,15(1):102-109.
[65]G.B. McMahon, M. Florian. On scheduling with ready times and due dates to minimize maximum lateness[J]. Operations Research.1975,23(3):475-482.
[66]L. Min, W. Cheng. A genetic algorithm for minimizing the makespan in the case of scheduling identical parallel machines[J]. Artificial Intelligence in Engineering.1999,13(4):399-403.
[67]L. Min, W. Cheng. Genetic algorithms for the optimal common due date assignment and the optimal scheduling policy in parallel machine earliness tardiness scheduling problems [J]. Robotics and Computer-Integrated Manufacturing.2006,22(4):279-287.
[68]E. Nowicki. An approximation algorithm for the m-machine permutation flow shop scheduling problem with controllable processing times[J]. European Journal of Operations Research.1993, 70(3):342-349.
[69]E. Nowicki, S. Zdrzalka. A Note on Minimizing Maximum Lateness in a One-machine Sequencing Problem With Release Dates[J]. European Journal of Operations Research.1986,23(2):266-267.
[70]C.T.D. Ng, T.C.E. Cheng, M.Y. Kovalyov. Single machine batch scheduling with jointly compressible setup and processing times[J]. European Journal of Operations Research.2004, 153(3):211-219.
[71]M. Pinedo. Scheduling:theory, algorithms, and systems[M].北京清华大学学研大厦:清华大学出 版社,2003.
[72]N. Piersma, W. Van Dijk. A local search heuristic for unrelated parallel machine scheduling with efficient neighborhood search[J]. Machematical and Computer Modelling.1996,24(9):11-19.
[73]D. Shabtay. Single and a two-resource allocation algorithms for minimizing the maximal lateness in a single machine-scheduling problem[J]. Computers and Operations Research.2004,31(8):1303-1315.
[74]D. Shabtay, M. Kaspi. Minimizing the total weighted flowtime in a single machine with control-lable processing times[J]. Computers and Operations Research.2004,31(13):2279-2280.
[75]D. Shabtay, M. Kaspi. Parallel machine scheduling with a convex resource consumption func-tion[J]. European Journal of Operations Research.2006,173(1):92-107.
[76]D. Shabtay, M. Kaspi. Minimizing the makespan in open-shop scheduling problem with a convex resource-dependent processing times[J]. Naval Research Logistics.2006,3(3):204-216.
[77]D. Shabtay, G. Steiner. Single machine batch scheduling to minimize total completion time and resource consumption costs[J]. Journal of Scheduling.2005,10(4):255-261.
[78]D. Shabtay, M. Kaspi, G. Steiner. The no-wait two-machine flow-shop scheduling problem with convex resource-dependent processing times[J]. HE Trans.2007,39(5):539-557.
[79]S.C. Scott, T.R. Jefferson. Allocation of resources in project management[J]. International Jour-nal of Systems Science. 1995,26(2):413-420.
[80]J.M.J. Schutten, R.A.M. Leussink. Parallel machine scheduling with release dates, due dates and family setup times[J]. International Journal of Production Economics.1996,46(1):119-125.
[81]D. Shabtay, G. Steiner. A survey of scheduling with controllable processing times[J]. Discrete Applied Mathematics.2007,155(13):1643-1666.
[82]S-O Shim, Y-D Kim. A branch and bound algorithm for an identical parallel machine scheduling problem with a job splitting property[J]. Computers and Operations Research.2008,35(3):863-875.
[83]R.G. Vickson. Two single mchine sequencing problems involving controllable job processing times[J]. AIIE Trans.1980,12(3):258-262.
[84]V. Valls and M.A. Perez and M.S. Quintanilla. A tabu search approach to machine scheduling [J]. European Journal of Operations Research.1998,106(1):277-300.
[85]B. Wardono, Y. Fathi. A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities[J]. European Journal of Operations Research.2004,155(2):380-401.
[86]J.D. Wisner, S.P Siferd. A survey of US manufacturing practices in make-to-order machine shops[J]. Production and Inventory Management Journal.1995, 1(1):1-7.
[87]G. Wan, B.P.C. Yen, C.L. Li. Single machine scheduling to minimize total compression plus weighted flow cost is NP-hard[J]. Information Processing Letters.2001,79(6):273-280.
[88]G.J. Woeginger. Heuristics for parallel machine scheduling with delivery times[J]. Acta Informat-ica.1994,31(6):503-512.
[89]B. Wardono, Y. Fathi. A tabu search algorithm for the multi-stage parallel machine problem with limited buffer capacities[J]. European Journal of Operations Research.2004,155(2):380-401.
[90]K. Xu, Z. Feng, L. Ke. A branch and bound algorithm for scheduling jobs with controllable processing times on a single machine to met due dates[J]. Annals of Operations Research.2010, 181(1):303-324.
[91]K. Xu, Z. Feng, L. Ke. A tabu-search algorithm for scheduling jobs with controllable processing times on a single machine to meet due-dates[J]. Computers and Operations Research.2010, 37(11):1924-1938.
[92]K. Xu, Z. Feng, L. Ke. Single machine scheduling with total tardiness criterion and convex controllable processing times[J]. Annals of Operations Research.2010, In publish.
[93]王小平,曹立明.遗传算法-理论、应用与软件实现[M].中国西安：西安交通大学出版社,2005年7月.
[94]段海滨.蚁群算法-原理及其应用[M].中国北京：科学出版社.2005年12月.
[95]钟嵬,殷志文,娄娜.赶工问题的一个新的最优算法[J].复旦学报(自然科学版).2001,40(4):456-460.
[96]黄明娜,刘永淞,张向荣.施工赶工计划优化[J].基建优化.2003,24(6):18-21.
[97]刘伟,王羽.关于赶工费用的不完全信息博弈分析[J].重庆交通学院学报.2006,25(1):132-141.
[98]闻振卫.偏序集最小顶点割算法与最小费用赶工问题[J].运筹与管理.2005,14(1):68-74.
[99]郭强,贾继红.求解PERT问题的一种简便算法.运筹与管理[J].2000,9(4):29-32.
[100]谢鹰,王明义.用试探法求解DCPM问题的一种新算法[J].系统工程理论与实践.1984,3(2):35-40.
[101]曹英知.网络计划最低费用日程的数学模型[J].系统工程理论与实践.1985,4(1):47-50.
[102]陈嵩强,周焕文.次关键路线法[J].系统工程理论与实践.1990,3(1):5-10.
[103]杨伟,刘彦生.决策关键路线法(DCPM)的改进算法[J].系统工程理论与实践.1987,4(1):71-77.
[104]闻振卫.最优箭线图的判定与唯一性[J].系统工程理论与实践.1999,4(3):1-10.
[105]王吉波.工件加工时间可变的现代排序问题[D].大连：大连理工大学,2005.
[106]任传荣.两类加工时间可变的排序问题[D].上海：上海大学,2006.
[107]田颖,江平宇,周光辉,赵刚.基于遗传算法的工艺规划与调度集成方法[J].西安交通大学学报.2006,40(9)：1041-1044.
[108]杨剑峰,蒋静坪.蚁群算法及其在组合优化问题中的应用[J].科技通报.2006,22(4):553-556.
[109]王笑蓉.蚁群优化的理论模型及在生产调度中的应用研究[D].杭州：浙江大学,2003.