两个多重目标排序问题的多项式时间算法
２０１０年３月
第２７卷第２期
重庆师范大学学报（自然科学版）
ＪｏｕｒｎａｌｏｆＣｈｏｎｇｑｉｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅ）
Ｍａｒ．２０１０
Ｖ０１．２７Ｎｏ．２
器筹拳与控制鲻
釜誊筹学与控制鲻ＤＯＩ：１０．３９６９／Ｊ．ＩＳＳＮ．１６７２—６６９３．２０１０．０２．００２两个多重目标排序问题的多项式时间算法’
彭洪洁１，唐国春１’２
（１．重庆师范大学数学学院，重庆４０００４７；２．上海第二工业大学管理工程研究所，上海２０１２０９）摘要：多目标排序是排序论的一个重要分支，在解决经济、管理、工程、军事、社会等领域出现的复杂问题中起着越来越重要的作用。本文研究以误工个数∑Ｕ为第１目标，∑埘ｆｃｆ或者∑埘Ｚ为第２目标的多重目标排序问题，分别给出了这两个问题在不误工工件集不改变下＿Ｔ－件加Ｘ－时间和权重满足反一致性条件（Ｐ。≤ＪＤ，ｊ峨≥ｗｊ）时复杂性为Ｏ（ｎｌｏｇ几）的多项式时间算法：对于排序问题ｌＩ（Ｐ；≤Ｐ，）ｊ（埘；≥埘，）Ｉ（∑ｗｊＣＪＥ），选取排序最后一个工件ｋ满足条件：肌／ｗＩ＝ｍａｘ｛ｐ。／ｗ。Ｉｉ∈ＭＵＬ｝；对于排序问题ｌＩ（Ｐ。≤ｐ，）专（埘ｆ＞＞－ｗｊ）Ｉ（Ｅｗ：／Ｅ），选取排序最后一个工件ｋ满足：１）若Ｍ为空集，Ｐｋ／ｗＩ＝ｍ戢｛Ｐｉ／ｗ；Ｉｉ∈Ｌ｝；２）若Ｍ非空，任意选取ｋ∈Ｍ。其中Ｌ是误工工件集，肘是放在最后不误工的工件的集合。最后，证明了这两个算法可以得到相应问题的最优解。
关键词：排序；误工；算法；多目标；计算复杂性；最优性
中图分类号：０２２３文献标识码：Ａ文章编号：１６７２－６６９３（２０１０）０２—０００４?０５多目标排序是排序论的重要分支。作为多目标决策问题，多目标排序在经济、管理、工程、军事、社会等领域中起着越来越重要的作用。例如，在生产过程中，决策者不但要使误工个数∑ｕ，最小，同时还要满足顾客的需求使得总的完工时间ｙＣ，最小或者最大延误Ｌ。。最小等。在多目标排序中有两个或两个以上目标函数。如果是在第１个目标函数７。为最优的条件下，使第２个目标函数７：为最优，这样的问题称为第ｌ类多目标排序问题，得到的最优解称为多重解。１９５６年Ｓｍｉｔｈ研究在没有工件误工的、所谓完美的（Ｐｅｒｆｅｃｔ）排序中寻找使平均完工时间（也就是等价使总的完工时间）为最小的排序问题，提出寻找这种最优解的Ｓｍｉｔｈ法则或者Ｓｍｉｔｈ算法，是研究第１类多目标排序多重解的第一篇论文…。经典排序论中，使误工工件的个数为最少的排序问题通常称为误工问题旧Ｊ，是排序论中最基本的问题之一，具有重要的理论意义和实用价值。１９６８年Ｍｏｏｒｅ提出解决单台机器误工排序问题的多项式时间算法＂Ｊ，这个算法称为Ｍｏｏｒｅ算法，可以在时间Ｏ（ｎｌｏｇｎ）内得到误工问题的最优解。之后很多学者研究各种推广的误工问题Ｈ４７｜。１９７３年，Ｓｉｄｎｅｙ研究在工件的一个子集ｒ中的工件必须不误工的条件下，使误工工件的个数为最少的误工排序问题１ｌ丁Ｉ∑以，并且给出该问题复杂性为Ｄ（ｎｌｏｇｎ）的多项式时间算法——Ｓｉｄｎｅｙ算法Ｈ１。还有学者考虑以误工个数为第１目标的多重目标排序问题¨髓３Ｊ。１９７５年，Ｅｍｍｏｎｓ在文献［２０］中推广了Ｓｍｉｔｈ法则给出在误工工件集给定下使∑ｃｉ最优的多项式时间算法。１９８３年，Ｓｈａｎｔｈｉｋｕｍａｒ在文献［２１］中给出了在误工工件集给定下使乇，最优的多项式时间算法。１９９５年Ｖａｉｒａｋｔａｒａｋｉｓ和Ｌｅｅ也在文献［２２］中类似的给出了在误工工件集给定下使∑ｒ最优的多项式时间算法。最新的成果是２００７年Ｈｕｏ，Ｌｅｕｎｇ，Ｚｈａｏ等证明，误工工件个数为第１目标、使总完工时间最小的多重目标排序问题１０（∑Ｃ『／∑ｕ，）或者使总延误最小的多重目标排序问题１ｆＩ（∑乃／∑∽）都是ＮＰ困难的旧１，解决国内外学术界长期来都十分关注的两个ｏｐｅｎｐｒｏｂｌｅｍｓ（悬而未决的问题）。本文研究以误工个数∑Ｕ为第ｌ目标，∑叫ｆＧｆ或者∑ｔｆ，丹为第２目标的ｓｔｒｏｎｇｌｙ—ＮＰ?ｈａｒｄ多重目标排序问题【２】，给出了在误工工件集已知下的的多项式时间算法，并且证明在加工时间与权具有“反向一致性”的前提下可得到最优解。
?收稿日期：２００９．１０—１２修回１３期：２０１０一Ｏｌ一３ｌ
资助项目：国家自然科学基金项目（Ｎｏ．７０７３１１６００１５，Ｎｏ．０７１００１５）；运筹学与系统工程重庆市市级重点实验室资助（Ｎｏ．ＹＣ２００８０２）作者简介：彭洪洁，男，硕士研究生，研究方向为组合最优化；通讯作者：唐国春，Ｅ－ｍａｉｌ：ｇｔａｎｇ＠ｓｈｌ６３．ｎｅｔ
第２期彭洪洁，等：两个多重目标排序问题的多项式时间算法５
１初步结果
设有ｒｔ个工件．，。，．，：，…，．，。要在一台机器上加工。记这１７，个工件的集合为Ｊ＝｛．，。，以，…，Ｌ｝。在不至于混淆的情况下，也用工件．，ｉ的下标，来表示这个工件。因此，这ｎ个工件的集合也可以写成Ｊ＝｛１，２，…，ｒｔ｝。已知工件，的加工时间是Ｐｊ，权值是埘ｆ，交货期是ｄ『ｏ这些工件已经全部准备就绪，都可以进行加工。这台机器每次只能加工一个工件，并且加工不允许中断，只有当一个工件加工完成后才能加工其他工件，如果一个工件在交货期之后完工，这个工件称为是误工的，否则称为是不误工的。安排一个加工次序，使误工工件的个数为最少，这就是误工（排序）问题，用三参数表示为１ＩＩ∑Ｕｉ幢Ｊ。如果要求某些指定的工件必须不误工，以丁表示指定必须不误工的工件的集合，又使误工工件的个数为最少，这就是使某些工件必须不误工条件下的误工排序问题，用三参数表示为１ｒＩ∑ｕｉ心Ｊ。记工件歹在排序Ｓ＝（ｓ（１），ｓ（２），…，ｓ（ｎ））中的完工时间为ｃｉ，延误为Ｉ，带权总完工时间为∑加ｉｃ，，带权总延误为∑加疋。在误工工件个数∑ｕｆ最少的条件下，使ｙ加ｆｃｆ或者∑加，１分别为最小的多重目标排序问题，用三参数可以表示为ｌＩｌ（∑埘ｆｃ『／∑％）、１ＩＩ（∑彬，Ｉ／∑∽）眵Ｊ。不失一般性，假设工件已经按照交货期的从小到大的次序，即ＥＤＤ（Ｅａｒｌｉｅｓｔｄｕｅｄａｔｅ）序进行编号，所以有ｄ，≤ｄ：≤…≤ｄ。。这时工件，的下标是工件在ＥＤＤ序中的序号。对于工件集合．，的子集矿，在不至于混淆的情况下，盯也表示这些工件按照下标从小到大排成的排序，即工件集合盯的ＥＤＤ序。
下面引理１和引理２的证明与文献［１５］中类似，在此略去。
定义１［１列如果排序矿中每一个工件都是不误工的，则把子集盯称为是不误工子集。
引理１如果排序盯＝｛ｔ，，ｔ：，…，ｔ。｝中的工件都是不误工的，那么排序盯的ＥＤＤ序中的工件也都是不误工的。反之亦然。
定义ｌ是根据ＥＤＤ序来定义不误工子集，有了引理１可以把定义１推广到一般。
定义２【ｌ副对于工件集．，的子集∥，如果在子集盯的一个排序中这些工件都是不误工的，那么这个子集称为是不误工子集。
有了不误工子集的定义，下面给出误工工件集的定义。
定义３如果工件集．，的最大不误工子集为Ｅ，那么子集Ｌ＝Ｊ＼Ｅ称为误工问题的误工工件集。
引理２误工问题存在这样的最优解，可以分为前后两部分：１）不误工的工件的全体（不误工工件集）Ｅ按ＥＤＤ序排在前面；２）误工工件集￡，以任意次序排在后面。
文献［１６］把这种形式的最优解称为是误工排序问题的Ｅ—Ｌ最优解。那么对于推广的误工排序问题１ｌ丁Ｉ∑ｕｉ的这种形式的最优解称为是推广误工排序问题ｌＴ１∑ｕｉ的Ｅ—Ｌ最优解。
１９７３年，Ｓｉｄｎｅｙ研究在工件的一个子集ｒ中的工件必须不误工的条件下，使误工工件的个数为最少的误工排序问题１ＴＩ∑配，并且给出该问题复杂性为Ｏ（几ｌｏｇｎ）的多项式时间算法一Ｓｉｄｎｅｙ算法Ｍ１。此算法可以写成如下形式…ｏ。
步骤Ｉ设Ｅｏ＝Ｔ，Ｊ—Ｅｏ＝｛Ｊｌ，Ｊ２，…＾｝■＜五＜…＜Ｌ，ｍ＝ｎ—ｌｒｌ，令ｋ＝ｌ；
步骤２若ｋ＝ｍ＋ｌ，算法终止，（Ｅ。，．，一Ｅ。）就是最优排序；若ｋ＜ｍ＋１，转入步骤３；
步骤３设Ｆ。＝Ｅ。一。Ｕ溉｝，计算既如下：如果凡是不误工子集，令Ｅ。＝Ｅ㈦Ｕ｛．『；｝；否则，如果以不是不误工子集，令Ｅ。＝Ｆｋ、∽Ｊ｝。其中工件＾的加工时间为Ｐ，＝ＩＴＩａＸ｛Ｐ；Ｉ．『；∈Ｆｋ＼ｒ｝。色中的工件是按ＥＤＤ序排列。令ｋ＝ｋ＋１，转入步骤２。
此排序问题１ＴＩ∑ｕｉ也可以写成多目标排序的形式：１０（∑ｖ／ｒ）。为了方便起见，现假设文章的后面部分的误工工件集￡是此算法得到的。
２误工工件集给定的多项式时间算法
排序问题１ＩＩ（∑嘶ｑ／∑％）和１ＩＩ（２ｗＴ／Ｙ．ｖｊ）的一般情形是ｓｔｒｏｎｇｌｙ—ＮＰ?ｈａｒｄ‘２１，下面分别给出这两
６重庆师范大学学报（自然科学版）ｈｔｔｐ：／／ｗｗｗ．ｃｑｎｕｊ．ｃｎ第２７卷
个问题在误工工件集￡已知下的多项式时间算法。令，Ｅ＝Ｊ＼Ｌ，那么在不误工工件集不变的前提下，使带权完工时间或者带权延误最小的排序问题用三参数表示为：１ＥＪ∑加ｉｃｉ和ｌＥｌ∑埘丹，写成多目标排序形
式为ｌＪＩ（ｙ．ｗｊｃ／Ｅ）和ｌｌＩ（∑哟乃／Ｅ）。记Ｍ＝｛ｉｄｉ≥∑乃｝。
定理１对于排序问题１Ｉ（Ｐｉ≤ｐ，）号（７１）ｉ＞ｔｗｊ）Ｉ（Ｙ．ｗｊＣ／Ｅ），选取排序最后一个工件Ｊｉ｝满足条件
Ｐ＾／ｗｔ＝ｍａｘ｛Ｐｉ／ｗｆｉ∈ＭｕＬ｝
其中肘ｕ￡中的工件是误工工件或者是放在最后不误工的工件。
证明定理ｌ等价于下面的算法ｌ，证明算法ｌ可得到最优解即可。
算法１
步骤０初始化，Ｑ＝Ｎ＝（１，２，…，，１），Ｅ’＝Ｎ—Ｅ；ｒ＝，ｌ，转到第一步。
步骤ｌ求得集合Ｍ＝｛ｊ：ｃｌｊ≥∑ｉ。ＱＰ。；＿『∈Ｑ｝；找到集合膨ｕＥ’，即误工工件的集合Ｅ’，或者排在最后不误工的工件集合肼，转下一步。
步骤２找出ＭＵＥ’中的工件Ｉ｜｝满足仇／ｗ。＝ｍａｘ｛Ｐｉ／ｗ‘Ｉｉ∈ＭＬＪＥ’｝，转下一步。
步骤３置ａ，＝ｊ｝，Ｑ＝Ｑ一｛后｝，Ｅ’＝Ｑｎ｛Ｎ—Ｅ｝，ｒ＝ｒ一１，如果ｒ＝０，Ｓ＝（口。，Ⅱ：，…，口。）是最后的排序。算法终止；否则，转步骤１。证毕定理２算法１产生的排序是问题ｌＩ（Ｐ；≤Ｊｐ，）号（钾ｉ≥ｗｊ．）Ｉ（∑嘶ｑ／Ｅ）的最优解。
证明不失一般性，考虑排序Ｒ＝（６。，ｂ：，…，ｂ。），并且令ｕ＝（ｂ。，ｂ：，…，ｂ，）为排序尺的前ｒ个工件。记Ｑ＝｛Ｈ｝是ｕ中所有工件的集合。假设Ｑ中有一个工件ｂＩ满足：ｐ。／ｗＩ＝ｍａｘ｛Ｐｉ／ｗｉｉ∈ＭＵＥ７｝，ｂ。∈ＭＵＥ’，其中Ｍ＝｛歹：ｄｊ≥∑ｉ。ｏＰ，√∈Ｑ｝，Ｅ’＝Ｑｎ｛』、ｒ—Ｅ｝，那么Ｒ≠．ｓ，因此Ｒ不是算法１产生的排序。假设算法ｌ得出的解中后凡一ｒ个工件的次序与尺相同，根据算法１，在选择第ｒ个工件，应该把ｂ。作为第ｒ个工件，若把ｂ。与６，交换，其他位置不变得到的新排序为Ｒ’
Ｒ＝（ｂ１，ｂ２，…，ｂｔ—Ｉ，ｂＩ，ｂＩ＋１，…，ｂ，，ｂ，＋ｌ，…，ｂ。）
Ｒ’＝（ｂｌ，ｂ２，…，ｂ＾一ｌ，ｂ，，ｂ＾＋ｌ，…，ｂｔ，ｂ，＋ｌ，…，ｂ。）。
比较这两个排序，则有
１）Ｃｆ（Ｒ）＝Ｃｆ（Ｒ７），ｉ＝１，２，…，尼一１，那么埘ｉＣｉ（Ｒ）＝１．０ｉＣ。（Ｒ７）；
２）Ｃ，（Ｒ）＝ＣＩ（Ｒ７）；
３）Ｃ；（Ｒ）＝Ｃｉ（Ｒ’），ｉ＝ｒ＋１，…，ｎ，那么１，０ｉＣｉ（Ｒ）＝埘ｉＣｉ（尺７）。
其中ｃｉ（Ｒ）和Ｃｉ（Ｒ’）分别表示工件ｂｉ在排序尺和尺’中的完工时间。
因此，两个排序的带权总完工时间之差
∑（加ｉｃｉ（Ｒ’）一加ｊＣｉ（Ｒ））＝（ｐ，－ｐ＾）（ｔｌ，Ｉ＋ｌ＋…＋埘，一１）＋（训‘一埘，）（ｐ女＋Ｉ＋…＋ｐ，一Ｉ）＋ｗｋｐ，－ｗｒｐＩ首先证明ｒ∈肘ｕＥ７，若ｒ∈Ｅ’，已证；否则ｒ隹Ｅ’，即ｒ∈Ｅ，从而ｂ，在任何可行排序中不延误，由ｃ，（Ｒ）＝∑ｐｆ≤ｄ，知ｒ∈Ｍ。因为ｐ‘／ｗ＾－－－－ｍａｘｌｌ，ｆ／ｗｉｉ∈ＭＵＥ’｝，所以ｐｋ／ｗ＾≥ｐ，／ｗ，，有ｗｋＰ，一ｗ，ｐ＾≤ｏ，并且加工时‘Ｅｐ
间与权具有“反一致性”关系，所以Ｐ。≥ｐ，，埘。≤埘，。因此∑（彬；Ｃｉ（尺’）一埘ｉＣｉ（尺））≤ｏ。
又因６。∈ＭＵＥ’和Ｐ。≥ｐ，，所以交换工件ｂ。与ｂ，得到的新排序Ｒ７中每个工件完工时间不增加，给定的不误工工件集不变。这样说明，选取算法ｌ选择的工件可以得到一个更好的排序。由于ｒ的任意性，算法ｌ产生的排序是问题的最优解。证毕定理３对于排序问题１Ｉ（Ｐｊ≤ｐｆ）ｊ（ｔ￡７ｉ≥埘ｆ）Ｉ（∑埘丹／Ｅ），选取排序最后一个工件屉满足
１）若肘为空集，ＰＩ／ｗ＾＝ｍａｘ｛Ｐｆ／ｗｉｉ∈￡｝；
２）若肘非空，任意选取Ｊ｜｝∈Ｍ。
第２期彭洪洁，等：两个多重目标排序问题的多项式时间算法７
证明上面的定理３等价于下面算法２，证明算法２可得到最优解即可。
算法２
步骤０初始化，Ｑ＝Ｎ＝（１，２，…，ｎ），Ｅ’＝Ｎ—Ｅ；ｒ＝ｎ，转到第一步。
步骤１求得集合Ｍ＝｛．『：ｄ，≥∑；。口ｐｉ∥ＥＱ｝；找到集合ＭｕＥ’，即误工工件的集合Ｅ’，或者排在最后不误工的工件集合肘，转下一步。
步骤２如果Ｍ为空集，找出工件｜ｊ｝满足ｐＩ／ｗ。＝ｍａｘ｛ｐｉ／ｗ；ｌｉ∈Ｅ’｝；如果肘非空，在Ｍ中任意选取一个工件作为后，转下一步。
步骤３置ａ，＝ｋ，Ｑ＝Ｑ一｛ｋ｝，Ｅ’＝Ｑｎ｛Ｎ—Ｅ｝，ｒ＝ｒ—ｌ，如果ｒ＝０，Ｓ＝（ｎ。，口：，…，％）是最后的排序。算法终止；否则，转步骤１。证毕定理４算法２产生的排序是问题ｌＩ（ｐ，≤ｐｆ）穹（Ｗｊ≥加ｆ）Ｉ（∑＂疋／Ｅ）的最优解。
证明不失一般性，考虑排序Ｒ＝（ｂ。，ｂ：，…，ｂ。），并且令Ｕ＝（ｂ。，ｂ：，…，ｂ，）为排序尺的前ｒ个工件。记Ｑ＝｛Ｕ｝是Ｕ中所有工件的集合。分两种情况证明。
１）若Ｍ非空，则有ｂ。∈Ｍ，因此Ｒ≠Ｓ，那么月不是算法２产生的排序，排序尺中的工件ｂ，是误工工件。假设算法２得出的解中后ｎ—ｒ个工件的次序与月相同，根据算法２，在选择第ｒ个工件，应该选择肘中不误工工件ｂ。作为第ｒ个工件。若把ｂ。排在ｂ，的后面，其他位置不变得到的新排序为Ｒ’
Ｒ＝（ｂｌ，ｂ２，…，ｂＩ一１，ｂｔ，ｂ＾＋ｌ，…，ｂ，，ｂ，＋ｌ，…，ｂ。）
Ｒ’＝（ｂｌ，ｂ２，…，ｂｔ—ｌ，ｂ＾＋ｌ，…，ｂ，，ｂ‘，ｂ，＋ｌ，…，ｂ。）
比较这两个排序则有：排序尺’中误工工件的总完工时间不增，那么带权总完工时间不增，因为ｂ。∈Ｍ，所以排序月７中的不误工工件集不改变。那么，作以上形式的变换可得到一个更好的排序。
２）若肼为空集。假设Ｑ中有一个工件ｂ＾满足：ＪＰ。／ｗ。＝ｍａｘｍ／埘ｉｉ∈Ｅ７｝，ｂ自∈Ｅ’。与定理２证明一，样。
综上所述，再由ｒ的任意性可知算法２产生的排序是问题的最优解。证毕算法ｌ与算法２都是从最后往前逐个安排工件，每次安排工件只进行赋值运算，所以这两个算法都可以在Ｏ（ｎｌｏｇ／／，）时间内运行。
参考文献：
［１］ＳｍｉｔｈＷＥ．Ｖａｒｉｏｕｓｏｐｔｉｍｉｚｅｒｓｆｏｒｓｉｎｇｌｅ—ｓｔａｇｅｐｒｏｄｕｃｔｉｏｎ［Ｊ］．ＮａｖａｌＲｅｓｅａｒｃｈＬｏｇｉｓｔｉｃｓ，１９５６，３：５９－６６．
［２］唐国春，张峰，罗守成，等．现代排序论［Ｍ］．上海：上海科学普及出版社，２００３．
［３］ＭｏｏｒｅＪＭ．Ａｎｎ－ｊｏｂ，ｏｎｅｍａｃｈｉｎｅｓｅｑｕｅｎｃｉｎｇａｌｇｏｆｉｔｈｍｆｏｒｍｉｎｉｍｉｚｉｎｇｔｈｅｎｕｍｂｅｒｏｆｌａｔｅｊｏｂｓ［Ｊ］．ＭａｎａｇｅｍｅｎｔＳｃｉｅｎｃｅ，１９６８，１５：１０２—１０９．
［４］ＳｉｄｎｅｙＪＢ．ＡｎｅｘｔｅｎｓｉｏｎｏｆＭｏｏｒｅ’ｓｄｕｅｄａｔｅａｌｇｏｒｉｔｈｍ［Ｍ］．ＥｌｍａｇｈｒａｂｙＳＥ．ＳｙｍｐｏｓｉｕｍｏｎｔｈｅＴｈｅｏｒｙｏｆＳｃｈｅｄｕｌｉｎｇａｎｄｉｔｓＡｐ?ｐｌｉｅａｔｉｏｎｓ．Ｂｅｒｌｉｎ：Ｓｐｒｉｎｇｅｒ，１９７３：３９３－３９８．
［５］ＬａｗｌｅｒＥＬ．ＳｅｑｕｅｎｃｉｎｇｔｏＭｉｎｉｍｉｚｅｔｈｅＷｅｉｇｈｔｅｄＮｕｍｂｅｒｏｆＴａｒｄｙＪｏｂｓ［Ｊ］．ＲＡＩＲＯ，１９７６，Ｓ１０（５）：２７－３３．
［６］ＫｉｓｅＨ，ＩｂａｒａｋｔＴ，ＭｉｎｅＨ．Ａｓｏｌｖａｂｌｅｃａｓｅｏｆｔｈｅｏｎｅ?ｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｗｉｔｈｒｅａｄｙａｎｄｄｕｅｔｉｍｅｓ［Ｊ］．ＯｐｅｒａｔｉｏｎｓＲｅ?ｓｅａｒｃｈ，１９７８，２６：１２１—１２６．
［７］黄婉珍，唐国春．分支定界法求解带权误工工件数排序［Ｊ］．应用数学学报，１９９２，１５（２）：１９４－１９９．
［８］邓俊强，林诒勋．１０∑∥．最优解的唯一性及其全部最优解的生成［Ｊ］．郑州大学学报（自然科学版），１９９７，２９（４）：１８－２２．［９］越民义．组合优化导论［Ｍ］．杭州：浙江科学技术出版社。２００１．
［１０］ＰｉｎｄｏＭ．Ｓｃｈｅｄｕｌｉｎｇ：ｔｈｅｏｒｙ，ａｌｇｏｒｉｔｈｍｓ，ａｎｄｓｙｓｔｅｍｓ［Ｍ］．２ｎｄｅｄｉｔｉｏｎ．ＮｅｗＪｅｒｓｅｙ：ＰｒｅｎｔｉｃｅＨａｌｌ，２００２．
［１１］ＢｒｕｃｋｅｒＰ．Ｓｃｈｅｄｕｌｉｎｇａｌｇｏｒｉｔｈｍｓ［Ｍ］．４ｔｈｅｄｉｔｉｏｎ．Ｈｅｉｄｅｌｂｅｒｇ：Ｓｐｒｉｎｇｅｒ，２００４．
［１２］孙叶平，唐万梅，唐国春．Ｍｏｏｒｅ－Ｈｏｄｇｓｏｎ算法最优性的新证明［Ｊ］．重庆师范大学学报（自然科学版），２００７，２４（３）：４－７．［１３］孙叶平，唐国春．ＫＩＭ算法的最优性［Ｊ］．运筹学学报，２００７，ｌｌ（４）：１１６－１２０．
［１４］陈小林，苏文玉，唐国春．Ｍｏｏｒｅ?Ｈｏｄｇｓｏｎ算法的最优性［Ｊ］．上海第二工业大学学报，２００８，２５（１）：２５－２８．
ＪｏｕｒｎａｌｏｆＣｈｏｎｇｑｉｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ（ＮａｔｕｒａｌＳｃｉｅｎｃｅ）ｈｔｔｐ：／／ｗｗｗ．ｃｑｎｕｊ．ｃｎＶ０１．２７Ｎｏ．２
［１５］【１６］［１７］
１８１９２０２１
［２２］［２３］苏永英，蒋宗彩，孙叶平．推广的误工排序问题的最优算法［Ｊ］．上海第二工业大学学报，２００８，２５（３）：２０１?２０６．
唐国春．误工排序问题的研究［Ｊ］．重庆师范大学学报（自然科学版），２００９，２６（２）：１石．
彭洪洁。苏永英，唐国春．部分工件必须不误工的误工排序问题［Ｊ］．重庆师范大学学报（自然科学版），２００９，２６（２）：１８?２１．
ＥｍｍｏｎｓＨ．Ｏｎｅ—ｍａｃｈｉｎｅｓｅｑｕｅｎｃｉｎｇｔＯｍｉｎｉｍｉｚｅｃｅｒｔａｉｎｆｕｎｃｔｉｏｎｓｏｆｊｏｂｔａｒｄｉｎｅｓｓ［Ｊ］．ＯｐｎｓＲｅｓ，１９６９，１７：７０１－７１５．
ＨｅｃｋＨ。ＲｏｂｅｒｔｓＳ．Ａｎｏｔｅｏｎｅｘｔｅｎｓｉｏｎｏｆａｒｅｓｕｌｔｏｎｓｃｈｅｄｕｌｉｎｇｗｉｔｈａｓｅｃｏｎｄａｒｙｃｒｉｔｅｒｉａ［Ｊ］．ＮａｖＲｅｓＬｏｇ，１９７２，１９：４０３－４０５．ＥｍｍｏｎｓＨ．Ｏｎｅｍａｃｈｉｎｅｓｅｑｕｅｎｃｉｎｇｔｏｍｉｎｉｍｉｚｅｍｅａｎｆｌｏｗｔｉｍｅｗｉｔｈｍｉｎｉｍｕｍｎｕｍｂｅｒｔａｒｄｙ［Ｊ］．ＮＲＬ，１９７５，２２：５８５．５９２．
ＳｈａｎｔｈｉｋｕｍａＪＧ．Ｓｃｈｅｄｕｌｉｎｇｎｊｏｂｓｏｎｏｎｅｍａｃｈｉｎｅｔｏｍｉｎｉｍｉｚｅｔｈｅｍａｘｉｍｕｍｔａｒｄｉｎｅｓｓｗｉｔｈｍｉｎｉｍｕｍｎｕｍｂｅｒｔａｒｄｙ［Ｊ］．ＣｏｍｐｕｔＯｐｅｒＲｅｓ，１９８３，１０：２５５－２６６．
ＶａｉｒａｋｔａｒａｋｉｓＧＬ，ＬｅｅＣＹ．Ｔｈｅｓｉｎｇｌｅ－ｍａｃｈｉｎｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｔＯｍｉｎｉｍｉｚｅｔｏｔａｌｔａｒｄｉｎｅｓｓｓｕｂｊｅｃｔｔｏｍｉｎｉｍｕｍｎｕｍｂｅｒｏｆｔａｒｄｙｊｏｂｓ［Ｊ］．ＩＩＥＴｒａｍ，１９９５，２７：２５０－２５６．
ＨｕｏＹＭ，ＬｅｕｎｇＪＹＴ，ＺｈａｏＨＲ．Ｃｏｍｐｌｅｘｉｔｙｏｆｔｗｏｄｕａｌｃｒｉｔｅｒｉａｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓ［Ｊ］．ＯｐｅｒａｔｉｏｎｓＲｅｓｒａｒｃｈＬｅｔｔｅｒｓ，２００７，３５：２１ｌ一２２０．
基ＯｐｅｒａｔｉｏｎｓＲｅｓｅａｒｃｈａｎｄＣｙｂｅｒｎｅｔｉｃｓ矗
秽’’礴
ＴｗｏＰｏｌｙｎｏｍｉａｌ－ＴｉｍｅＡｌｇｏｒｉｔｈｍｓｆｏｒＤｕａｌＳｃｈｅｄｕｌｉｎｇＰｒｏｂｌｅｍｓ
ＰＥＮＧＨｏｎｇ－ｊｉｅｌ．ＴＡＮＧＧｕｏ．ｃｈｕｎｌ’２
（１．ＣｏｌｌｅｇｅｏｆＭａｔｈｅｍａｔｉｃｓＳｃｉｅｎｃｅ，ＣｈｏｎｇｑｉｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｃｈｏｎｇｑｉｎｇ４０００４７；
２．ＩｎｓｔｉｔｕｔｅｏｆＭａｎａｇｅｍｅｎｔＥｎｇｉｎｅｅｒｉｎｇ．ＳｈａｎｇｈａｉＳｅｃｏｎｄＰｏｌｙｔｅｃｈｎｉｃＵｎｉｖｅｒｓｉｔｙ，Ｓｈａｎｇｈａｉ２０００４１，Ｃｈｉｎａ）
Ａｂｓｔｒａｃｔ：Ｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｓｗｉｔｈｍｕｌｔｉｐｌｅｏｂｊｅｃｔｉｖｅｓｐｌａｙｉｎｃｒｅａｓｉｎｇｉｍｐｏｒｔａｎｔｒｏｌｅｓｉｎｓｏｌｖｉｎｇｃｏｍｐｌｉｃａｔｅｄｐｒｏｂｌｅｍｓａｐｐｅａｒｉｎｇｉｎｔｈｅｆｉｅｌｄｓｏｆｅｃｏｎｏｍｙ，ｍａｎａｇｅｍｅｎｔ，ｅｎｇｉｎｅｅｒｉｎｇ，ｍｉｌｉｔａｒｙａｆｆａｉｒｓａｎｄｓｏｃｉｅｔｙｅｔｃ．Ｉｎｔｈｉｓｐａｐｅｒ，ｗｅｇｉｖｅｔｗｏｐｏｌｙｎｏｍｉａｌ－ｔｉｍｅａｌｇｏｒｉｔｈｍｓｗｈｅｎａｌｌｔａｒｄｙｊｏｂｓａｒｅｇｉｖｅｎｆｏｒｔｈｅｔＷＯｂｉｎａｒｙＮＰ—ｈａｒｄｐｒｏｂｌｅｍｓ１０Ｌｅｘ（∑ｑ，Ｘｗ，Ｃ，）ａｎｄ１Ｉ｜Ｌｅｘ（∑ｑ，ｘ彬ｉｒ，）．Ｆｏｒｔｈｅｐｒｏｂｌｅｍ１Ｐｌ≤岛ｊ毗≥吁ｆｔｔｘ（Ｅ，∑ｑｅ），ｓｃｈｅｄｕｌｅｊｏｂｋｌａｓｔ，ｗｈｅｒｅｐ／ｗＩ＝ｍａｘＩｐｆ／ｗｆｉ∈ＭＵ￡｝，ａｎｄＭ：｛ｉｄ。≥∑ｉ。ＪＰ；｝ｉｓｔｈｅｓｅｔｏｆｊｏｂｓｗｈｉｃｈ珊ｎｏｔｔａｒｄｙｅｖｅｎｗｈｅｎｐｒｏｃｅｓｓｅｄｌａｓｔ，ＬｉｓＳｅｔｏｆｔａｒｄｙｊｏｂｓ；Ｆｏｒｔｈｅｐｒｏｂｌｅｍ１Ｐ‘＜一ｐｉｏｗｆ≥嘶ｌＬｅｘ（Ｅ，Ｘｗ，ｒ，），ｓｃｈｅｄｕｌｅｊｏｂ｜｜｝ｌａｓｔ，ｗｈｅｒｅＰｔ／ｗｔ＝ｍａｘ｛Ｐｉ／ｗｉｉ∈Ｌ｝ｉｆＭｉｓｅｍｐｔ；ｅｌｓｅｃｈｏｏｓｅａｎｙｊｏｂｉｎＭ．Ｉｎｔｈｅｅｎｄ，ｗｅｇｉｖｅｐｒｏｏｖｅｓｏｆｔｈｅｓｃｈｅｄｕｌｅｗｈｉｃｈｇｏｔｆｒｏｍｔｈｅｐｏｌｙｎｏｍｉａｌ－－ｔｉｍｅａｌｇｏｒｉｔｈｍｉｓａｎｏｐｔｉｍａｌｓｏｌｕｔｉｏｎｆｏｒｔｈｅｓｃｈｅｄｕｌｉｎｇｐｒｏｂｌｅｍｗｉｔｈｗｅｉｇｈｔｅｄａｇｒｅｅａｂｌｅｃｏｎｄｉ??ｔｉｏｎｒｅｓｐｒｅｔｉｖｅｌｙ．
Ｋｅｙｗｏｒｄｓ：ｓｃｈｅｄｕｌｉｎｇ；ｔａｒｄｙ；ａｌｇｏｒｉｔｈｍ；ｍｕｌｔｉｐｌｅｏｂｊｅｃｔｉｖｅｓ；ｃｏｍｐｌｅｘｉｔｙ；ｏｐｔｉｍａｌｉｔｙ
（责任编辑黄颖）
两个多重目标排序问题的多项式时间算法
作者：彭洪洁， 唐国春， PENG Hong-jie， TANG Guo-chun
作者单位：彭洪洁,PENG Hong-jie(重庆师范大学,数学学院,重庆,400047)， 唐国春,TANG Guo-chun(重庆师范大学,数学学院,重庆,400047;上海第二工业大学,管理工程研究所,上海
,201209)
刊名：
重庆师范大学学报（自然科学版）
英文刊名：JOURNAL OF CHONGQING NORMAL UNIVERSITY(NATURAL SCIENCE EDITION)
年，卷(期)：2010，27(2)
被引用次数：0次
参考文献(23条)
1.Smith W E Various optimizers for single-stage production 1956
2.唐国春.张峰.罗守成现代排序论 2003
3.Moore J M An n-job,one machine sequencing algorithm for minimizing the number of late jobs 1968
4.Sidney J B An extension of Moore's due date algorithm 1973
https://www.wendangku.net/doc/3c10879021.html,wler E L Sequencing to Minimize the Weighted Number of Tardy Jobs 1976(z10)
6.Kise H.Ibarakt T.Mine H A solvable case of the one-machine scheduling problem with ready and due times 1978
7.黄婉珍.唐国春分支定界法求解带权误工工件数排序 1992(2)
8.邓俊强.林诒勋1‖∑Uj最优解的唯一性及其全部最优解的生成 1997(4)
9.越民义组合优化导论 2001
10.Pindo M Scheduling:theory,algorithms,and systems 2002
11.Brucker P Scheduling algorithms 2004
12.孙叶平.唐万梅.唐国春Moore-Hodgson算法最优性的新证明[期刊论文]-重庆师范大学学报(自然科学版) 2007(3)
13.孙叶平.唐国春KIM算法的最优性[期刊论文]-运筹学学报 2007(4)
14.陈小林.苏文玉.唐国春Moore-Hodgson算法的最优性[期刊论文]-上海第二工业大学学报 2008(1)
15.苏永英.蒋宗彩.孙叶平推广的误工排序问题的最优算法[期刊论文]-上海第二工业大学学报 2008(3)
16.唐国春误工排序问题的研究[期刊论文]-重庆师范大学学报（自然科学版） 2009(2)
17.彭洪洁.苏永英.唐国春部分工件必须不误工的误工排序问题[期刊论文]-重庆师范大学学报（自然科学版）2009(2)
18.Emmons H One-machine sequencing to minimize certain functions of job tardiness 1969
19.Heck H.Roberts S A note on extension of a result on scheduling with a secondary criteria 1972
20.Emmons H One machine sequencing to minimize mean flow time with minimum number tardy 1975
21.Shanthikuma J G Scheduling n jobs on one machine to minimize the maximum tardiness with minimum number tardy 1983
22.Vairaktarakis G L.Lee C Y The single-machine scheduling problem to minimize total tardiness subject to minimum number of tardy jobs 1995
23.Huo Y M.Leung J Y T.Zhao H R Complexity of two dual criteria scheduling problems 2007
相似文献(10条)
1.期刊论文彭洪洁.苏永英.唐国春.PENG Hong-jie.SU Yong-ying.TANG Guo-chun部分工件必须不误工的误工排
序问题-重庆师范大学学报（自然科学版）2009,26(2)
排序论中使误工工件的个数为最少的单台机器排序问题,称为误工问题,是排序论中最基本的问题之一.1973年,Sidney研究在工件的一个子集T中的工件必须不误工的条件下,使误工工件的个数为最少的误工排序问题1｜T｜∑Uj,并且给出该问题复杂性为O(n log n)的多项式算法--Sidney算法.本文把Sidney 算法改写成比较简洁的算法1,1)步骤1:设E 0=T,J－E 0=｛j1,j2,…,jm｝,j1＜j2＜…＜jm,m=n-｜T｜,令k=1:2)步骤2:若k=m+1,算法终止
,(Em,J－Em)就是最优排序:若k＜m+1,转入步骤3:3)步骤3:设Fk=Ek-1∪{jk},计算Ek如下:如果Fk是不误工子集,令Ek=Ek-1∪{jk}:否则,如果Fk不是不误工子集,令Ek+Fk\{jr}.其中工件jr的加工时间为pr=max{pi｜ji∈Fk\T}.Ek中的工件是按EDD序排列.k=k+1,转入步骤2.并用数学归纳法证明算法1产生的排序是该误工问题的最优解.
2.学位论文姜国平两机器最小总误工数分组排序问题算法研究2006
成组技术在现代生产中有着广泛的应用，对分组排序问题的研究有着重要的实际意义。本文以现代生产制造业中成组生产为实际背景，研究了一类两机器分组排序的最小总误工数问题(F2ISf1，Sf2，ddm|∑Ui)。本文证明了此问题是NP一Hard问题，因此此类问题在规模较大的情况下，要用有限的资源在合理的时间内获得最优解将比较困难。本文研究了此类问题的最优解结构和优势准则，并着重研究了此类问题的遗传算法优化。
本文的主要创新和贡献如下：
1．最优解结构性质的提出和证明。本文提出了关于此类问题最优解结构的一个引理和两个定理，并加以证明。为本文研究的遗传算法优化提供了理论支持，并有助于分支定界等算法的研究。
2．优势准则的提出和证明。本文提出了此类问题的一个优势准则，可作为分支定界算法的剪枝规则。
3．整数规划模型的提出。
4．此类问题遗传算法的提出。本文介绍了此类问题的遗传算法编码、适应度函数及尺度变换、选择算子、交叉算子和变异算子。并用VB语言编程实现，给出了计算结果。
本文的研究成果在实际生产环境中具有相当的实用价值，可以应用在企业的生产排程系统中用来解决此类问题。
3.期刊论文唐国春.TANG Guo-chun误工排序问题的研究-重庆师范大学学报（自然科学版）2009,26(2)
误工排序问题是经典排序论中最基本和最重要的问题.40年来国内外许多学者对其进行研究的兴趣有增无减,深刻的成果不断涌现.本文阐述2006年以来重庆师范大学运筹学与控制论专业的硕士研究生在研究误工排序问题上得到的成果及其意义.这些成果包括研究经典的和推广的误工问题,包括某些工件必须不误工,或者工件的就绪时间不相同、与交货期有一致性的,或者带权的误工排序问题,或者工件的加工时间与工件的权有反向一致性,或者多台平行机误工排序问题等等得到的成果.
4.期刊论文曹国梅.CAO Guo-mei单机分族分批排序的最小误工个数问题-四川理工学院学报(自然科学版)
2008,21(5)
文章研究了同一族内,给出并证明了其最优排序的性质.对工件到达时间和工期相一致时的情形,得出了一个时间复杂性为O(mb(n/m)2m)的动态规划算法.
5.期刊论文朱琪.王书宁.Zhu Qi.Wang Shuning MDD函数在单机总误工排序问题中的作用-运筹学学报2005,9(4) 本文把工件的修正工期(MDD:Modified Due Date)看成工件关于时间的函数,通过研究该函数在一定区间的性质建立了一个具有全局意义的定理,利用这个定理可以方便地导出有关单机总误工排序问题的一些重要结论.这些工作既能够很好地解释常用的MDD规则的有效性,同时也说明MDD函数可以成为解决单机总误工排序问题的基本工具.
6.期刊论文曹国梅.Cao Guomei p与d一致时的分族分批排序误工个数问题-河南科学2009,27(7)
研究了一类分族分批排序最小误工个数问题,给出并证明了最优排序的性质,证明了此问题是NP-困难的.对工件的到达时间和工期一致时的情形,给出了一个时间复杂性为O(mb(n-m)2m)的动态规划算法.
7.期刊论文叶春花.沈灏机器带中断的误工问题的近似排序算法-杭州电子科技大学学报2010,30(1)
该文讨论两台平行机排序问题,其中一台机器在不确定情况下中断,中断持续时间为D,目标为极小化误工工件数.当工件转移时间T=0时,该文提出该问题的最优算法.当转移时间T>0时为NP难问题,该文提出了一个差界为1的多项式时间的近似算法.
8.期刊论文原晋江.何程.林诒勋.Yuan Jinjiang.He Cheng.Lin Yixun最小化加权误工工件数的多代理平行分批
排序-运筹学学报2009,13(4)
考虑多代理的平行分批排序,不同代理的工件不能放在同一批中加工,目标函数是最小化加权误工工件数.本文考虑两种模型,证明了甚至当所有工件具有单位权时,这两个模型都是强NP困难的.但当代理数给定时,这两个问题都可在拟多项式时间解决,并且当工件具有单位权时,可在多项式时间解决.进一步证明当代理数固定时,两个问题都有FPTAS算法.
9.期刊论文陈小林.CHEN Xiao-lin带权的误工排序问题的最优算法-运筹与管理2009,18(3)
研究工件有不同的权(重要性)、但是与工件加工时间有反向"一致性"关系,并且在保证工件的一个子集T中的工件必须不误工的前提下,使得带权的误工工件的个数(误工造成损失的费用)为最少的排序问题1∣T,(pi≤pj ) (wi≥wj)∣∑wjUj ;提出该问题的最优算法,证明提出的算法得到的排序是最优排序,而且证明这个最优排序在所有最优排序中不误工工件总的加工时间为最小.
10.学位论文何程多目标分批排序及其相关课题2009
在过去的50年中，机器排序问题已成为组合最优化中最活跃的研究课题之一.然而，在大多数经典的排序文献中，只考虑机器一次至多加工一个工件，且目标函数只有一个.随着时间的推移，分批排序和多目标排序已蓬勃发展起来.可是将两者（分批排序和多目标排序）结合起来的研究尚不多见.由于电子加工业及其它产业的高速发展，以及决策者的不同利益需求，将分批排序与多目标排序结合起来考虑，应该提到议事日程上.
设n个无关的工件J1，J2，...，Jn，它们将在一台分批处理机上加工.工件Jj的加工时间、工期、期限和权分别为pj、dj、dj和wj（j=1，…，n）.以Sj和Gj分别表示工件Jj的开始加工时间和完工时间.给定一个序σ，Lj（σ）=Cj（σ）-dj与Lmax（σ）=maxnj=Lj（σ）分别表示工件Jj的延迟与序
σ的最大延迟.Tj=max{0，Lj}为工件Jj的延误，Uj为它的单位惩罚因子.本论文主要考虑分批处理机上同时最小化双目标排序问题.所谓的分批处理机是指机器可同时加工多个工件，放在一起加工的工件集称为一批，同一批中的工件具有相同的开工时间和完工时间.根据批的加工时间的不同定义，分批处理机又分为平行分批处理机和序列分批处理机.对前者，一批的加工时间等于这一批中最长工件的加工时间.这一模型是由半导体加工的烘烤、计算机系统及其它领域的操作抽象而来的.对后者，一批的加工时间等于这一批中所有工件的加工时间之和，且在每一批加工开始前，都有一个常数s的安装时间.这一模型起源于现实生活中这样的要求：当一批工件加工完成后，需要一段时间来调换工具、维修机器等.另一方面，两个目标函数可以代表两个决策者的不同利益.这一方向发展的基本动机源于这样的事实：质量评估通常是一个多维概念.并且决策者常常追求多个目标同时最优化一对所有目标函数找出全部的Pareto最优序.称一个可行序σ是关于目标函数f和g的Pareto最优序，是指不存在可行序π，使得，（π）≤f（σ），g（π）≤g（σ），且其中这两个不等式至少有一个严格成立.
本学位论文的主要研究成果如下：
1. 单机平行分批的双目标排序
前人分别对双目标及平行分批两方面已得到一些结果.例如，证明了同时最小化最大延迟和最大费用函数的单机排序问题可在O（n3logn）时间内解决
们考虑两方面的结合，即同时最小化最大延迟和最大完工时间的平行分批排序问题，并给出一个O（n3）时间的多项式时间算法，可以求出全部Pareto最优解.对多目标优化问题而言，求出全部Pareto最优解是最完整的解答.另外，当机器容量有界，且工件的加工时间为常数时，以总延误为主指标，次指标分别是误工工件数、加权误工工件数和加权总完工时间的分层最小化问题已有O（n3）时间算法.我们统一地给出O（nlogn）时间算法，改进了上述时间界. 2. 单机序列分批的双目标捧序
对于序列分批的单目标排序问题，当机器容量无界时，最小化最大延迟问题已有O（n2）时间的算法；最小化加权总完工时间也已有了O（n）时间的算法.对于双目标问题，没有已知结果.我们在O（n2）时间内解决了同时最小化最大延迟和最大完工时间问题.此外，对同时最小化最大完工时间和总完工时间问题，在机器容量无界或有界的情形下，我们分别给出O（m2）时间算法.以上算法均可求出全部Pareto最优解，获得完全的解答.
3. 单机双目标排序
已知最小化具有截止时间的误工工件数问题是NP-困难的.对如下特殊情形的误工工件数问题，文献中已有O（n2）时间的后向算法.（ⅰ）如果
di≤dj，那么di≤dj与pi≤pj；（ⅱ）如果pi≥pj，那么di-dj≤pi-pj.为建立统一的理论，我们提出了一种对偶算法一前向的贪婪算法，对情形（ⅰ），它有更好的时间界O（nlogn）.对情形（ⅱ），得到相同的时间界，但方法有不同特点.并且我们还研究了工件加工时间相等的情形，也找到了O（nlogn）时间算法.
因为不同的决策者对同一个工件的工期要求可能不同（它们分别代表各自的期望利益），所以可设每一个工件Jj具有两个工期d（1）j和
d（2）j（1≤j≤n）.这样，对一个给定的序σ，就诱导了两个目标函数最大延迟L（1）max与L（2）max.我们证明同时最小化关于两个工期集合的最大延迟问题可在O（n3logn）时间内解决，求出全部Pareto最优解，且时间界是紧的.
关键词：排序；平行分批处理机；序列分批处理机；多目标；Pareto最优序
本文链接：https://www.wendangku.net/doc/3c10879021.html,/Periodical_cqsfxyxb201002002.aspx
授权使用：浙江师范大学(wfshzjsf)，授权号：1b885475-7e1f-4d2c-933f-9dd60109e2fd
下载时间：2010年8月18日