若干排序问题研究
摘要
排序问题是一类重要的组合优化问题,随着在实际领域的应用以及理论研究方面的不断深入,衍生出各种不同类型的排序问题模型。本文主要研究几类不同的排序问题,侧重于不同模型下近似算法的设计以及算法的最坏情况界估计。本文总共分为五章。
第一章对组合优化问题、排序问题以及算法复杂性的相关概念作了简单介绍,然后对主要工作成果进行了梳理。
第二章讨论m台平行机上极小化完工时间平方和问题Pm‖∑Gj2。我们利用非凸二次规划估计GSPT算法给出的排序目标值,进而给出了GSPT算法解决该问题的最坏情况界,当m为偶数时,最坏情况界为当m为奇数时,最坏情况界为
第三章研究工件加工部分可分的平行机排序问题。工件可被分割成加工时间为整数的若干部分,同一工件的不同部分可在同一时刻于不同机器上加工,目标为极小化加权总完工时间。我们给出了一个最坏情况界为4/3近似算法。
第四章在保密计算的框架之下研究两类经典的排序问题Pm‖Cmax与Bm||Cmax。在以上问题中,工件分属于不同的单位,不同单位相互之间也不希望泄漏彼此保有的信息。我们的工作实现了在不暴露隐私的前提下将问题转化为可以公开的排序问题,并且在求解公开的排序问题之后,各单位能够给出自己的加工策略,以使多方能安全合作。
第五章探讨两类随机排序问题1‖∑Uj和F2|dj=d|ΣUj。对工件加工时间所服从的正态分布和伽马分布作了比文献已有研究更一般的假设,设计了相应的算法。初步的数值试验保证了所得算法的有效性
Scheduling is one of the most important branches in combinatorial optimization. With the fast development of practical application and theoretical research, various scheduling models can be derived from the original classic. This article launch the research of several different kinds of scheduling problems and focus on approximation algorithm design and estimation of the worst-case ratio. This paper is divided into five chapters.
In Chapter1, we first introduce the corresponding concepts, theories and computa-tional complexity briefly. And then we summarize our main research results.
In Chapter2, we discuss the scheduling problem of minimizing the sum of quadratic completion times on m parallel machines Pm||ΣCj2. We estimate the scheduling ob-jective value given by the GSPT rule, based on non-convex quadratic programming tech-nique. Then the worst-case ratio according to the GSPT rule is obtained as: if m is even, and,if m is odd.
In Chapter3, we concentrate on the scheduling problem of minimizing the weighted total completion time on parallel machines where the processing time of each job can be divided divided into several parts whose processing time are integers. Different parts of the same job can be processed at the same time on different machines. We give approximation algorithm with the worst-case ratio4/3.
In Chapter4, we consider two classical scheduling problems Pm||Cmax and Rm||Cmax in the case of privacy-preserving. Consider the situation that the parameters in problems Pm||Cmax and Rm||Cmax are partitioned into groups. Each group is owned by a distinct private entity that is unwilling to share or make public its own data. We construct secure programs based on the privately held data without revealing it. Each unit is capable of their processing strategies after the secure programs is solved and hence the units can cooperate securely.
In Chapter5, we discuss two stochastic scheduling problems1|ΣUj and F2|dj=
第一章对组合优化问题、排序问题以及算法复杂性的相关概念作了简单介绍,然后对主要工作成果进行了梳理。
第二章讨论m台平行机上极小化完工时间平方和问题Pm‖∑Gj2。我们利用非凸二次规划估计GSPT算法给出的排序目标值,进而给出了GSPT算法解决该问题的最坏情况界,当m为偶数时,最坏情况界为当m为奇数时,最坏情况界为
第三章研究工件加工部分可分的平行机排序问题。工件可被分割成加工时间为整数的若干部分,同一工件的不同部分可在同一时刻于不同机器上加工,目标为极小化加权总完工时间。我们给出了一个最坏情况界为4/3近似算法。
第四章在保密计算的框架之下研究两类经典的排序问题Pm‖Cmax与Bm||Cmax。在以上问题中,工件分属于不同的单位,不同单位相互之间也不希望泄漏彼此保有的信息。我们的工作实现了在不暴露隐私的前提下将问题转化为可以公开的排序问题,并且在求解公开的排序问题之后,各单位能够给出自己的加工策略,以使多方能安全合作。
第五章探讨两类随机排序问题1‖∑Uj和F2|dj=d|ΣUj。对工件加工时间所服从的正态分布和伽马分布作了比文献已有研究更一般的假设,设计了相应的算法。初步的数值试验保证了所得算法的有效性
Scheduling is one of the most important branches in combinatorial optimization. With the fast development of practical application and theoretical research, various scheduling models can be derived from the original classic. This article launch the research of several different kinds of scheduling problems and focus on approximation algorithm design and estimation of the worst-case ratio. This paper is divided into five chapters.
In Chapter1, we first introduce the corresponding concepts, theories and computa-tional complexity briefly. And then we summarize our main research results.
In Chapter2, we discuss the scheduling problem of minimizing the sum of quadratic completion times on m parallel machines Pm||ΣCj2. We estimate the scheduling ob-jective value given by the GSPT rule, based on non-convex quadratic programming tech-nique. Then the worst-case ratio according to the GSPT rule is obtained as: if m is even, and,if m is odd.
In Chapter3, we concentrate on the scheduling problem of minimizing the weighted total completion time on parallel machines where the processing time of each job can be divided divided into several parts whose processing time are integers. Different parts of the same job can be processed at the same time on different machines. We give approximation algorithm with the worst-case ratio4/3.
In Chapter4, we consider two classical scheduling problems Pm||Cmax and Rm||Cmax in the case of privacy-preserving. Consider the situation that the parameters in problems Pm||Cmax and Rm||Cmax are partitioned into groups. Each group is owned by a distinct private entity that is unwilling to share or make public its own data. We construct secure programs based on the privately held data without revealing it. Each unit is capable of their processing strategies after the secure programs is solved and hence the units can cooperate securely.
In Chapter5, we discuss two stochastic scheduling problems1|ΣUj and F2|dj=
引文
[1]F. Afrati, E. Bampis, C. Chekuri, D. Karger, C. Kenyon, S. Khanna, I. Milis, M. Queyranne, M. Skutella, C. Stein, M. Sviridenkom. Approximation schemes for min-imizing average weighted completion time with release dates, Proceedings of the 40th Annual IEEE Symposium on Foundations of Computer Science,1999:32-43.
[2]J.M. Akker, J.A. Hoogeveen. Minimizing the number of late jobs in a stochastic set-ting using a chance constraint, Journal of Scheduling,2008(11):59-69.
[3]R.K. Ahuja, T.L. Magnanti, J.B. Orlin. Network Flows:Theory, Algorithms, and Ap-plications, Prentice-Hall,1993.
[4]P. Brucker. Scheduling Algorithms, Springer,2007.
[5]E. Barnes, V. Chen, B. Gopalakrishnan, E.L. Johnson. A least-squares primal-dual algorithm for solving linear programming problems, Operations Research letters, 2002(30):289-294.
[6]R. Canetti. Seurity and composition of multiparty cryptographic protocols. Journal of Cryptology,2000(13):143-202.
[7]W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver. Combinational Opti-mization, Wiley-Interscience,1997.
[8]F.D. Croce, C. Koulamas. A note on minimizing the sum of quadratic comple-tion times on two identical parallel machines, Information Processing Letters, 2012(112):738-742.
[9]F.D. Croce, J.N.D. Gupta, R. Tadei. Minimizing tardy jobs in a flow shop with com-mon due date, European Journal of Operational Research,2000(120):375-381.
[10]F.D. Croce, C. Koulamas. Minimizing the sum of quadratic completion times on two identical parallel machines, MISTA 2011 Conference Proceedings,2011:240-244.
[11]G.H. Cheng, G.H. Huang, Y.P. Li, M.F. Cao, Y.R. Fan. Planning of municipal sol-id waste management systems under dual uncertainties:a hybrid interval stochas-tic programming approach, Stochatic Enviromental Research and Risk Assessment, 2009(23):707-720.
[12]C. Clifton, A. Iyer, R. Cho, W. Jiang, M. Kantarcioglu, J. Vaidya. An approach to identifying beneficial collaboration securely in decentralized logistics systems, Man-ufacturing and Service Operations Management,2008:108-125.
[13]T.C.Cheng, Z.Liu, Parallel machine scheduling to minimize the sum of quadratic completion times, ⅡE Transactions,2004(36):11-17.
[14]R. Conway, W. Maxwell, L. Miller. Theory of scheduling, Dover Publications,2003.
[15]B. Chen, C.N. Potts, G.J. Woeginger. A review of machine scheduling:Complexity, algorithms and approximability, Handbook of combinatorial optimization (D.Z. Du and P.M. Pardalos eds.), Kluwer Academic Publishers,1998.
[16]A. Elyasi, N. Salmasi. Stochastic scheduling with minimizing the number of tardy jobs using chance constrained programming, Mathematical and Computer Modelling, 2013(57):1154-1164.
[17]A. Elyasi, N. Salmasi. Stochastic flow-shop scheduling with minimizing the expected number of tardy jobs, The International Journal of Advanced Manufacturing Tech-nology,2013(66):337-346.
[18]X. Feng, Y. He, Z. Zhang. The numerical rank of a matrix and its applications, Ap-plied Mathematics and Computation,2008(196):416-421.
[19]A. Fishkin, K. Jansen, L. Porkolab. On minimizing average weighted completion time:A ptas for scheduling general multiprocessor tasks, Proceedings of the 13th International Symposium on Fundamentals of Computation Theory,2001:495-507.
[20]B. Fortz, M. Poss. Easy distribution for combinatorial optimization problems with probabilistic constraints, Operations Research Letters,2010(38):545-549.
[21]X. Feng, Z. Zhang. The rank of a random matrix, Applied Mathematics and Compu-tation,2007(185):689-694.
[22]D. Hochbaum. Approximation Algorithms for NP-Hard problems, PWS Publishing Company,1997.
[23]P. Hansen, C. Meyer. Improved compact linearizations for the unconstrained quadrat-ic 0-1 minimization problem, Discrete Applied Mathematics,2009(157):1267-1290.
[24]M.R. Garey, D.S. Johnson. Computers and intractability:a guide to the theory of NP-completeness, W.H. Freeman and Company,1979.
[25]R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy. Optimization and approx-imation in deterministic sequencing and scheduling:A survey. Annals of Discrete Mathematics,1979(5):287-326.
[26]O. Goldreieh. The Foundations of Cryptography:Basic Applieations, Cambridge U-niversity Press,2004(2).
[27]N. Immorlica, L. Li, V.S. Mirrokni, A. Schulz. Coordination mechanisms for selfish scheduling. Theoretical Computer Science,2009(410):1589-1598.
[28]S.M. Johnson. Optimal two and three stage production schedules with setup times included, Naval Research Logistics Quarterly,1954(1):61-68.
[29]Kursad Agpak, Hadi Gokcen. A chance-constrained approach to stochastic line bal-ancing problem, European Journal of Operational Research,2007(180):1098-1115.
[30]B. Korte, J. Vygen. Combinatorial Optimization:Theory and Algorithms, Springer, 2007.
[31]E.L. Lawler. Combinatorial optimization:networks and matroids, Holt, Rinehart and Winston,1976.
[32]W. Li. Dual-primal algorithm for linear optimization, Optimization Methods and Software,2013(28):327-338.
[33]O.L. Mangasarian. Nonlinear programming. McGraw-Hill,1969.
[34]O.L. Mangasarian. Privacy-preserving linear programming, Optimization Letters, 2011(5):165-172.
[35]O.L. Mangasarian. Privacy-preserving horizontally partitioned linear programs, Op-timization Letters,2012(6):431-436.
[36]W.L. Maxwell. On sequencing n jobs on one machine to minimize the number of late jobs, Management Science,1970(16):295-297.
[37]C.N. Potts, V.A. Strusevich. Fifty years of scheduling:a survey of milestones, Journal of the Operational Research Society, (2009)60:41-68.
[38]A. Prekopa. Stochastic Programming, Kluwer,1995.
[39]V. Portougal, D. Trietsch. Johnson's problem with stochastic processing times and optimal service level, European Journal of Operational Research,2006(169):751-760.
[40]V.E.Smith. Various optimizers for single stage production, Naval Research Logistics Quarterly,1956(3):59-66.
[41]D.K. Seo, C.M. Klein, W. Jang. Single machine stochastic scheduling to minimize the expected number of tardy jobs using mathematical programming models, Computers and Industrial Engineering,2005(48):153-161.
[42]E. Suthampan, S. Maneewongvatana. Privacy preserving decision tree in multi party environment, Lecture Notes in Computer Science,2005(3689):727-732.
[43]M. Skutella, G. Woeginger. A ptas for minimizing the weighted sum of job comple-tion times on parallel machines, Proceedings of the 31th Annual ACM Symposium on Theory of Computing,1999:400-407.
[44]D. Trietsch, K.R. Baker. Minimizing the number of tardy jobs with stochastically-ordered processing times, Journal of Scheduling,2008(11):71-73.
[45]Z.Y. Tan, A. Zhang. Online and Semi-online Scheduling. Handbook of Combinatorial Optimization,2013:2191-2252.
[46]唐恒永,赵传立.排序引论,北京：科学出版社,2002
[47]V.V. Vazirani. Approximation Algorithms, Springer,2003.
[48]J. Vaidya, C. Clifton, M. Zu. Privacy Preserving Data Mining, Springer,2009.
[49]Q.L. Wei, H. Yan. Generalized optimal theory and models, Science Press,2003.
[50]Woeginger G. When does a dynamic programming formulation guarantee the exis-tence of a fully polynomial time approximation scheme (FPTAS)? INFORMS Journal on Computing 2000(12):57-74.
[51]谢金星,邢文训,王振波.网络优化(第2版),北京：清华大学出版社,2009.
[52]A. Yao. Protocols for Secure Computation, Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science.1982:160-164.
[53]姚恩瑜,何勇,陈仕平.数学规划与组合优化,杭州：浙江大学出版社,2001.
[54]Q. Zhang, W. Wu, M. Li. Minimizing the total weighted completion time of fully parallel jobs with integer parallel units[J]. Theoretical Computer Science,2013(507): 34-40.
[2]J.M. Akker, J.A. Hoogeveen. Minimizing the number of late jobs in a stochastic set-ting using a chance constraint, Journal of Scheduling,2008(11):59-69.
[3]R.K. Ahuja, T.L. Magnanti, J.B. Orlin. Network Flows:Theory, Algorithms, and Ap-plications, Prentice-Hall,1993.
[4]P. Brucker. Scheduling Algorithms, Springer,2007.
[5]E. Barnes, V. Chen, B. Gopalakrishnan, E.L. Johnson. A least-squares primal-dual algorithm for solving linear programming problems, Operations Research letters, 2002(30):289-294.
[6]R. Canetti. Seurity and composition of multiparty cryptographic protocols. Journal of Cryptology,2000(13):143-202.
[7]W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver. Combinational Opti-mization, Wiley-Interscience,1997.
[8]F.D. Croce, C. Koulamas. A note on minimizing the sum of quadratic comple-tion times on two identical parallel machines, Information Processing Letters, 2012(112):738-742.
[9]F.D. Croce, J.N.D. Gupta, R. Tadei. Minimizing tardy jobs in a flow shop with com-mon due date, European Journal of Operational Research,2000(120):375-381.
[10]F.D. Croce, C. Koulamas. Minimizing the sum of quadratic completion times on two identical parallel machines, MISTA 2011 Conference Proceedings,2011:240-244.
[11]G.H. Cheng, G.H. Huang, Y.P. Li, M.F. Cao, Y.R. Fan. Planning of municipal sol-id waste management systems under dual uncertainties:a hybrid interval stochas-tic programming approach, Stochatic Enviromental Research and Risk Assessment, 2009(23):707-720.
[12]C. Clifton, A. Iyer, R. Cho, W. Jiang, M. Kantarcioglu, J. Vaidya. An approach to identifying beneficial collaboration securely in decentralized logistics systems, Man-ufacturing and Service Operations Management,2008:108-125.
[13]T.C.Cheng, Z.Liu, Parallel machine scheduling to minimize the sum of quadratic completion times, ⅡE Transactions,2004(36):11-17.
[14]R. Conway, W. Maxwell, L. Miller. Theory of scheduling, Dover Publications,2003.
[15]B. Chen, C.N. Potts, G.J. Woeginger. A review of machine scheduling:Complexity, algorithms and approximability, Handbook of combinatorial optimization (D.Z. Du and P.M. Pardalos eds.), Kluwer Academic Publishers,1998.
[16]A. Elyasi, N. Salmasi. Stochastic scheduling with minimizing the number of tardy jobs using chance constrained programming, Mathematical and Computer Modelling, 2013(57):1154-1164.
[17]A. Elyasi, N. Salmasi. Stochastic flow-shop scheduling with minimizing the expected number of tardy jobs, The International Journal of Advanced Manufacturing Tech-nology,2013(66):337-346.
[18]X. Feng, Y. He, Z. Zhang. The numerical rank of a matrix and its applications, Ap-plied Mathematics and Computation,2008(196):416-421.
[19]A. Fishkin, K. Jansen, L. Porkolab. On minimizing average weighted completion time:A ptas for scheduling general multiprocessor tasks, Proceedings of the 13th International Symposium on Fundamentals of Computation Theory,2001:495-507.
[20]B. Fortz, M. Poss. Easy distribution for combinatorial optimization problems with probabilistic constraints, Operations Research Letters,2010(38):545-549.
[21]X. Feng, Z. Zhang. The rank of a random matrix, Applied Mathematics and Compu-tation,2007(185):689-694.
[22]D. Hochbaum. Approximation Algorithms for NP-Hard problems, PWS Publishing Company,1997.
[23]P. Hansen, C. Meyer. Improved compact linearizations for the unconstrained quadrat-ic 0-1 minimization problem, Discrete Applied Mathematics,2009(157):1267-1290.
[24]M.R. Garey, D.S. Johnson. Computers and intractability:a guide to the theory of NP-completeness, W.H. Freeman and Company,1979.
[25]R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy. Optimization and approx-imation in deterministic sequencing and scheduling:A survey. Annals of Discrete Mathematics,1979(5):287-326.
[26]O. Goldreieh. The Foundations of Cryptography:Basic Applieations, Cambridge U-niversity Press,2004(2).
[27]N. Immorlica, L. Li, V.S. Mirrokni, A. Schulz. Coordination mechanisms for selfish scheduling. Theoretical Computer Science,2009(410):1589-1598.
[28]S.M. Johnson. Optimal two and three stage production schedules with setup times included, Naval Research Logistics Quarterly,1954(1):61-68.
[29]Kursad Agpak, Hadi Gokcen. A chance-constrained approach to stochastic line bal-ancing problem, European Journal of Operational Research,2007(180):1098-1115.
[30]B. Korte, J. Vygen. Combinatorial Optimization:Theory and Algorithms, Springer, 2007.
[31]E.L. Lawler. Combinatorial optimization:networks and matroids, Holt, Rinehart and Winston,1976.
[32]W. Li. Dual-primal algorithm for linear optimization, Optimization Methods and Software,2013(28):327-338.
[33]O.L. Mangasarian. Nonlinear programming. McGraw-Hill,1969.
[34]O.L. Mangasarian. Privacy-preserving linear programming, Optimization Letters, 2011(5):165-172.
[35]O.L. Mangasarian. Privacy-preserving horizontally partitioned linear programs, Op-timization Letters,2012(6):431-436.
[36]W.L. Maxwell. On sequencing n jobs on one machine to minimize the number of late jobs, Management Science,1970(16):295-297.
[37]C.N. Potts, V.A. Strusevich. Fifty years of scheduling:a survey of milestones, Journal of the Operational Research Society, (2009)60:41-68.
[38]A. Prekopa. Stochastic Programming, Kluwer,1995.
[39]V. Portougal, D. Trietsch. Johnson's problem with stochastic processing times and optimal service level, European Journal of Operational Research,2006(169):751-760.
[40]V.E.Smith. Various optimizers for single stage production, Naval Research Logistics Quarterly,1956(3):59-66.
[41]D.K. Seo, C.M. Klein, W. Jang. Single machine stochastic scheduling to minimize the expected number of tardy jobs using mathematical programming models, Computers and Industrial Engineering,2005(48):153-161.
[42]E. Suthampan, S. Maneewongvatana. Privacy preserving decision tree in multi party environment, Lecture Notes in Computer Science,2005(3689):727-732.
[43]M. Skutella, G. Woeginger. A ptas for minimizing the weighted sum of job comple-tion times on parallel machines, Proceedings of the 31th Annual ACM Symposium on Theory of Computing,1999:400-407.
[44]D. Trietsch, K.R. Baker. Minimizing the number of tardy jobs with stochastically-ordered processing times, Journal of Scheduling,2008(11):71-73.
[45]Z.Y. Tan, A. Zhang. Online and Semi-online Scheduling. Handbook of Combinatorial Optimization,2013:2191-2252.
[46]唐恒永,赵传立.排序引论,北京：科学出版社,2002
[47]V.V. Vazirani. Approximation Algorithms, Springer,2003.
[48]J. Vaidya, C. Clifton, M. Zu. Privacy Preserving Data Mining, Springer,2009.
[49]Q.L. Wei, H. Yan. Generalized optimal theory and models, Science Press,2003.
[50]Woeginger G. When does a dynamic programming formulation guarantee the exis-tence of a fully polynomial time approximation scheme (FPTAS)? INFORMS Journal on Computing 2000(12):57-74.
[51]谢金星,邢文训,王振波.网络优化(第2版),北京：清华大学出版社,2009.
[52]A. Yao. Protocols for Secure Computation, Proceedings of the 23rd IEEE Symposium on Foundations of Computer Science.1982:160-164.
[53]姚恩瑜,何勇,陈仕平.数学规划与组合优化,杭州：浙江大学出版社,2001.
[54]Q. Zhang, W. Wu, M. Li. Minimizing the total weighted completion time of fully parallel jobs with integer parallel units[J]. Theoretical Computer Science,2013(507): 34-40.