《工业调度算法中的贪婪与公平》由会员分享，可在线阅读，更多相关《工业调度算法中的贪婪与公平（6页珍藏版）》请在金锄头文库上搜索。
1、论文名称：工业调度算法中的贪婪与公平摘要从18世纪80年代到以后的三代人里，一场史无前例的、意义深远的革命在整 个英格兰展开。英国工业革命标志着人类社会发展史上一个全新时代的开始，拉开 了整个世界向工业化社会转变的“现代化”帷幕。英国工业革命的成功使各国看到 了振兴的希望，纷纷变法图强，从此以后，工业革命在不同国家、不同地区展开， 至今方兴未艾。而工业生产中各行业大机器生产的目标总是在不断地缩短生产成本 不断地优化效率。产业的管理人员和技术人员在长期反复的加工过程中尝试着对于 原材料生产的顺序进行更改以便减小成本。而对于原材料、工件、资源的加工顺序 的更改和变换久而久之就形成了调度这门学科。工
2、业调度当中经过理论研究和实践 探索不断形成了某种生产方式生产模型的最优算法或者近似最优算法。而工业调度中这些算法的目的就在于使得生产成本最优，使得每台机器最后的 完成时间相等，从这哲学角度来说这就是一种贪婪。让每台机器最后完工的时间保 持一致这在现实生产中是很难达到的，而采用调度算法让每台机器最后完工时间达 到一致无疑是一种贪婪。但是从另外一种角度来说，每台机器完工时间一致，这样 就不会存在一台机器加工大部分的工件最后导致这台机器完成时间最长，而其他机 器相应的加工的工件数就比较少，最后的完成时间也相对较小。因此，再采用调度 算法以后，每台机器都有着平等的机会加工所有的工件，每台机器都得到充分
3、的使 用，这从某种角度来说也是一种物尽其用、人尽其责，这也就是一种公平。贪婪与公平无疑是一种矛盾对立的统一，一方面要想实现贪婪无疑会破坏公平 的制度，而想要维持公平就很难实现贪婪；另一方面，贪婪其实也就是一种公平， 每个人通过努力都可以实现自己的最大价值从而拥有公平的机会实现自己的价值， 而公平也就是一种贪婪，每个人都实现自己的最大价值，这种理想化的状态就是一 种贪婪。因为，社会的资源是有限的它不能让每个人都实现自己的价值因此公平也 就是一种贪婪。而工业调度中算法的目的就是让贪婪与公平达到很好的统一，而当 这两者达到统一的时候往往就会使得成本最优。本文首先通过对工业革命和工业调度算法的历程以及
4、工业调度中相关问题的 简单描述以及算法的简单介绍，然后从中分析工业调度算法当中所蕴含的贪婪与公 平之间的哲学思想，最后根据这种关系来对人性的贪婪与公平做一个新的诠释，让 工业调度算法中的贪婪与公平之间的哲学思想得到推广同时让其他行业的从业人 员有一定的借鉴意义。关键词：工业调度贪婪与公平哲学思想矛盾统一目录第一章背景介绍41.1工业革命41.2工业调度41.3工业调度中的相关算法4第二章 工业调度中的贪婪与公平52.1贪婪与公平的矛盾52.2贪婪与公平的统一5第三章人性贪婪与公平的启示6第一章背景介绍1.1工业革命18世纪80年代开始，一场史无前例的、意义深远的革命在整个英格兰展开。 “从那时
5、起，世界不再是以前的世界了。”从英国的工业革命开始，地球上就开始 存在着两类主要的文明：工业文明和农业文明。当然中间还有很多过渡地带，因为 不同国家的工业化程度不同，有的很高级而更多的甚至还没有开始工业化。工业革 命是近代工业化的实际开端，是传统农业社会向近代工业社会过渡的转折点。工业 革命是人类历史的伟大飞跃，工业革命所建立起来的工业文明，成为延续了几千年 的传统农业文明的终结者，它不仅从根本上提升了社会的生产力，创造出巨量的社 会财富，而且从根本上变革了农业文明的所有方面，完成了社会的重大转型。经济、 政治、文化、精神，以及社会结构和人的生存方式等等，无不发生了翻天覆地的变 革。所谓工业革
6、命，其实是不同层次的统一，首先是产业和经济革命，然后是社会 革命，最后是文化革命。不能把工业革命仅仅当作是产业革命，而应当从社会革命 和文化革命着眼来进行全面把握。事实上，如果没有社会革命的支撑，工业革命无 法最终完成。工业革命与社会结构的根本性变化互为表里。实际上工业社会的一切 都以工业大生产为基础进行，一方面国家建立起关联度极高、分工极为严密的产业 体系，产生了大批的“自由劳动者”产业工人（包括蓝领和白领），同时工业 化要求从业者有较高的教育，因此国家建立起完整而系统的国民教育体系，使得教 育和职业训练社会化。另一方面，国家作为大企业利益的集中体现，与经济管理高 度整合，管理能力和国家权力
7、大大增强。如此一来，整个国家和社会高度组织化， 就像一台巨大的机器，日夜不停地产生出令人生畏的能量。1.2工业调度自从工业革命诞生以来，原始的小工作作坊式的生产模式被大规模生产以及后 来的机器生产模式所取代，各工业行业都是采用大规模机器生产人力资源只是简单 的机器操作和完成机器无法完成的工作，而那些单一、繁重、危险、重复、简单的 工作逐渐的被机器所取代。如钢铁的冶炼和萃取、玻璃的制作、原材料的流水线加 工、产品的制作和组装、轮船码头货物的搬运大都采用并行或者串行机器流水线操 作。而一件产品的每个工件（job）的加工时间往往是不同的，因此工件的加工顺 序往往会影响产品的最终出厂和完成时间，因此工
8、件的加工顺序会影响产品的制作 成本，也就影响了交货日期和顾客的等待时间。因此工业行业中的从业人员包括技 术人员管理人员都会对工件的加工顺序进行研究合理的设计，使得工件按照工件的 加工时间递增或者递减的某种方式某种模型来加工使得成本降低、优化目标。这种 对于工件加工顺序的安排，资源的处理就形成了工业调度。工业调度的研究不断地 发展以逐渐形成一种领域和学科。1.3工业调度中的相关算法本文简单介绍工业调度中的一个基本算法-LPT算法，即最长加工时间最先加 工的算法。假设有M台机器可以加工工件，当所有的工件来了以后，每个工件都有 自己的基本加工时间，LPT算法就是首先按照工件的加工时间进行由大到小进行
9、排 列然后最长的加工时间先加工在任意一个机器之上，次长的加工在另外一个空闲的 机器上，按照加工时间最长最先加工而依次加工的工件选择空闲的机器进行加工。 而这里最一般的最小化目标函数是制造期（Cmax），制造期的定义为max （C1,C2,C3，Cn），和最后一项离开系统的工作完成时间相等。最小的制造期通常意味着机器的高利用率。而目标函数制造期理想化最优的情 况下是每台机器总共加工工件的时间相等，也就是每台机器都能得到合理的利用而 不会闲置，也就是每台机器的制造期都一致，但是由于每个工件的加工时间是不一 样的，这样的话，这种理想化的状态是不可能实现的，因UtLPT算法不可能达到最 优，但是LPT
10、算法的设计初衷就是基于人性的贪婪，想要达到理想化状态每台机器 得到充分的使用也就是公平的理念。但是两者往往却是矛盾的。第二章工业调度中的贪婪与公平2.1贪婪与公平的矛盾在第一章的介绍中，调度算法譬如LPT算法设计的初衷就是基于人性的贪婪想 要让每台机器得到充分的利用，让目标函数最优。而目标函数最优也就是意味着每 台机器都有机会发挥自己的价值，这也就是公平的含义。制造业调度中的相关算法 大部分都无法达到最优化目标也就是每台机器的加工时间相等，算法实现的结果往 往是及其接近最优化结果而无法达到最优结果，这就是说明两者之间的矛盾，两者 是无法同时实现的。也就说明了贪婪与公平之间的矛盾。2.2贪婪与公
11、平的统一按照制造业调度算法譬如LPT来说，算法的理想化结果就是让每台机器的加工时 间一致，也就说如果贪婪得到满足的话最终就达到了公平。此外，一些其他的算法 尤其是多项式算法是可以使目标函数达到最优的。也就意味着贪婪最终结果就是公 平，而如果每台机器都能实现自己的价值，都能公平的发挥自己的效应，那么也就 是达到最优化目标，而最优化目标和贪婪的结果也是一致的。因此公平中蕴含着贪 婪，两者之间不再是对立而是统一的。第三章人性贪婪与公平的启示从制造业调度算法当中可以看到贪婪的目的就是实现公平，而想要达到公平这 其实也就是一种贪婪。这和一般的理念（人性的贪婪往往会破坏公平的机制）有所 不同。当然人是无法
12、和机器加工相比较的，但是从这些思想当中却还是可以有所启 迪的。人性的贪婪往往是无节制无限制的，但是整个社会的资源是有限的，所以一个 人的贪婪往往占据获得了大部分的资源，这样就使得其他的人无法获得自己想要的 资源，因此也就不能实现公平。但是，事实上如此么？显然不是，一个人应该或者 值得或者多少资源显然不是由他个人意愿所决定的，不能说是一个人想要多获得什 么就能获得什么。有人说，如果把当今天社会的资源重新均匀分配不出几年，最终 每个人所获得的资源的情况还是会和没有分配之前保持一样。所以，人性的贪婪就 是为了达到一种公平，达到物尽其用，人尽其责。只不过每个人的能力、所获得的 资源、可以实现的价值不像
13、机器那样差别不大，而是千差万别也是受到各种因素的 影响，即使每个人获得的资源有很大的差别，实现的价值也有大有小，但并不能说 明这是一种不公平，不公平的只是表象，内在的思想和外在的东西对等就是一种公 平，这种公平简直再公平不过了。强者欺凌弱者，脆弱的生命犹如切割机修剪疯枝一样被无形地消磨，高贵的姿 态始终站在世界的顶端洋洋得意。富者富丽堂皇，随意挥霍；穷者省吃俭用，勤勤 恳恳。有人乞讨，有人施舍；有人扛着满是灰尘的麻袋，有人躺在豪华的办公椅上； 有人啃着发霉的馒头，有人喝着洋酒夹着雪茄。这一切的局面都是由人的贪婪所决 定的，人性贪婪的不同最终决定了你所拥有的东西，你理应获得什么就会获得什么， 你
14、得到的东西就是你应该得到的，你失去的东西也不是你应得的。这一切的现象就 像草原上雄狮撕扯瘦弱的斑马，河岸旁微风轻轻地抚摸绿叶杨柳那般理所当然，那 般怡然自得，那般潇潇洒洒。贪婪了就不要抱怨不公，因为不管怎样你已经处于一种公平之中。公平之中的 我们其实就是最初那个贪婪的念头所决定所影响的。而这念头的叠加就是整个群体 整个社会背后的思想、背后的推动力量，这个不知名的东西推动着我们，至于推向 何方，远不是我们这一代所能够看到。我们每个人就应该像那制造业中加工工件的每个机器一样，尽职尽责，不再抱 怨。让“人类”安排那一个个工件，我们只需要加工就可，因为“人类”已经再想 办法或者已经给我们安排了最优的算法使得我们集体的努力达到最优目标。
