《两类加工时间可变排序问题》由会员分享，可在线阅读，更多相关《两类加工时间可变排序问题（42页珍藏版）》请在金锄头文库上搜索。
1、！堡土塑盔堂亟堂焦鲨塞！摘要排序问题是一类重要的组合最优化问题在经典排序问题中，通常假设工件的加工时间是固定的常数，然而在许多实际问题中，工件的加工时间可能与工件分配到的资源、开工时间或所排的位置有着某种联系，由此产生了一些新的排序这些新的排序问题比经典排序排序问题更为复杂，绝大多数问题是一困难问题对这些一困难问题，讨论它的近似算法，并进行最坏情况分析很有必要；由于实际生活的需要，讨论这些排序问题存在多项式可解的情况也很有必要这些多项式算法，一方面可以为某些问题给出求解方法；另一方面还可以为解决其它问题提供近似算法在本文中，我们研究了两类工件加工时间可变的排序问题，主要做了以下两个方面的工作：
2、第一部分，加工时间与资源分配有关的单机排序，这是一个与资源约束有关的准时排序问题工件分配到的资源越多，其加工时间就会越少所有的工件具有共同的交货期，是个需要决策的变量目标函数是极小化包含提前惩罚、延误惩罚和工期惩罚的总惩罚函数求解这类问题实际上就是找出最优的排列、每个工件的最优资源分配量以及最优交货期，使得目标函数最小我们主要考虑了两种情况第一种情况是工件的加工时间是它所得到的资源量的非线性递减函数；第二种情况是工件的加工时间是它所得到的资源量的线性递减函数我们分析了最优性条件，尽管这个问题的一般情况的算法复杂性未知，我们探讨了多项式时间可解的情况，并给了有效算法第二部分，加工时间是开工时间的
3、简单线性关系的平行机排序，目标函数是极小化最大完工时间这个问题是一困难的，我们利用了划分的思想，对两台机器的排序问题，我们提供了一个有效的近似算法一全多项式逼近算法，并把这个结果推广到机器数目固定的多台机器的平行机问题上，关键词：排序；可控加工时问；准时排序；共同交货期；资源约束；恶化工件！至上连盘堂亟堂焦迨塞！。，。、盯工，面出，卸出，出旷，嬲。函，：丘盯（），跗贰，舡，矗“，一一一！生土渔太堂亟堂焦迨塞！出：。嘲，。（）：村舭盯，工礼彻，：；。；缸；原创性声明本人声明：所呈交的论文是本人在导师的指导下进行的研究工作除了文中特别加以标注和致谢的地方外，论文中不包含其他人已发表或撰写过的研究成
4、果，参与同一工作的其他同志对本研究所做的任何贡献均已在论文中做了明确的说明并表示了谢意签名：例乏不日期：加刃年月莎日本论文使用授权说明本人完全了解上海大学有关保留、使用学位论文的规定，即：学校有权保留论文及送交论文复印件；允许论文被查阅和借阅；学校可以公布论文的全部或部分内容保密的论文在解密后应遵守此规定签名玩引墨荦导师籍名拣印蔟日觏“年石其年上海大学硕士学位论文第一章绪论排序问题（）是一类重要的组合最优化问题，也是运筹学研究的一个非常活跃的分支排序问题最早起源于机器制造业，后来被广泛地应用于计算机系统、运输调度、生产管理等领域从普通的生产部门的计划安排、人员调度，学校课程表的制定，到宇宙飞船的复杂庞大的飞行计划，都要用到排序的理论和算法排序问题排序问题是一类利用一些处理机、机器（）或资源（）最优地完成一批给定的任务或作业的组合最优化问题在执行这些任务或作业时要满足某些限制条件，如任务或作业的到达时间、完工的限定时间、任务的加工顺序、资源对加工时间的长短、处理机的影响等最优地完成指的是使目标函数达到最小，而目标函数通常是对加工时间的长短、处理器的利用率的描述对于排序问题，我们一般采用下面的方式来描述：给定含有个任务的任务集以如，厶台处理机的集合，）和种资源的资源集，。）排序问题指的是在一定条件下，为了完成各项任务，把尸中的处理机和（如果有）中的资源分配给，
