运筹学指派问题

前言：想要写出一篇令人眼前一亮的文章吗？我们特意为您整理了5篇运筹学指派问题范文，相信会为您的写作带来帮助，发现更多的写作思路和灵感。

运筹学指派问题范文第1篇

关键词：运筹学；空中交通管理；应用

0. 引言

运筹学是一门应用性的实用科学，是用多种数学工具及逻辑判断方法来对系统中的人、财、物的组织管理及筹划调度等问题进行研究的一种管理学科，它能有效的对管理系统中的各种资源进行科学的规划与安排，并为相关决策者提供有价值的参考依据，有力促进效益最佳化的实现[1]。对于空中交通管理而言，能够运用到空中交通管理中的运筹学知识有很多，包括线性规划、整数规划、非线性规划、动态规划、排队论、网络分析以及对策论等等，而在这其中，运筹学内容中的线性规划以及整数规划中的等很多课程内容的设计都与空中交通实践过程不谋而合，能有力的起到提升空中交通管理安全性及管理效率的作用，因而对其在在空中交通管理中的应用做出仔细探究则显得尤为迫切与重要，现分析如下：

1. 在空中交通管理中线性规划的应用

1.1机场空侧容量评估优化中线性规划的应用

完善的机场空侧的容量评估体系能对机场航班的有效安排起到重要促进作用。一般情况下机场空侧容量评估体系主要由滑行道系统、停机坪系统以及跑道体统等三部分内容构成，而对这三方面不同内容的评估目的也有所差异，即依次为改良滑行道的路径、对停机位指派进行优化以及进港先服务、离港优先隔。将机场空侧容量评估的模型转化为多目标线性规划后，其目标函数则为经济成本函数与延误时间函数，约束条件既通过进港以及离港定位点的设定，来转化成节点的流量控制[2]。

1.2地面等待问题中线性规划的应用

统筹学中线性规划在地面等待问题的应用中一般情况下需要通过以下三个步骤才能进行有效解决。首先就是对影响地面等待的各个因素进行科学、仔细的分析，并确定出决策中的变量因素。其次就是将问题的解决的目的加以明确和定位，同时紧密结合决策变量来对目标函数进行确定。最后就是以机场的运行限制为重要依据，来决定约束的条件。通过以上三个步骤我们便可以将地面等待问题有效转换成线性规划问题，而在其中目标函数则是综合飞机延误时间的最小化，约束条件则包括机场在容量方面的约束、航班的到达约束、单位时间内机场的最大起驾次以及飞机起飞时间与次数方面连续性的约束。

2. 在空中交通管理中整数规划的应用

2.1整数规划在机位分配中的应用

整数规划除了在限制方面不同于线性规划外，其在原理、操作流程以及模型上都与线性规划在空中交通管理中的应用大体相似。在整数模型建立之后，运用单纯性的方法以及计算机的计算软件来进行求解，以促进机位分配最优化的实现，同时，在建立机位分配模型时，所选取的目标函数即为旅客转机路程最优、机位空闲时间均衡、航班等待延误时间最小等，其中可以将机位空闲时间均衡与航班等待延误时间进行整体的规划，使得机位分配模型将旅客与地面服务人员异动距离的最小化作为目标。其中决策参数即为机位作业时间以及机位最小间隔时间[3]。

2.2整数规划在机位分配中的流程设置

将实时调配的流程设计应用于机场机位的分配中，能够有效的提升机位分配的有效性。同时，在进行停机位的指派时要将机位号、机型以及所属公司等飞机的属性匹配问题进行充分考虑。而其主要流程一般由以下七个步骤组成：第一步 ，对航班预期到达的时间进行仔细的确认；第二步，对航班所需要调整的时间段进行科学的设定；第三步，调整进港航班集合；第四步，将集合中的航班在机位预指派中进行取消；第五步，对和航班需要调整时间段有交集的极为空闲时间进行及时的更新；第六步，运用遗传算法对集中航班的机位进行合理的调配；第七步，以机位调配方案为重要依据，对机位空闲时间进行更新，实现调整方案的输出。另外，在对机位指派问题中的求解过程中可以采取以下几种方法：贪心算法、禁忌搜索算法、模拟退火算法、图着色算法、蚁群算法（ASP）、遗传算法以及Memet-ic 算法，同时，还可以对其中若干个算法进行组合来进行求解[4]。

3. 结语

总而言之，运筹学作为一门利用数学方法来解决生产、管理问题的重要学科，对于空中交通管理效率的提升而言，有着十分重要的战略指导意义。为此，相关管理人员应当加大对运筹学的学习与研究力度，并将运筹学有效应用于空中交通管理中，唯有如此，才能进一步促进公众交通管理在安全性与效益性方面的有效增长。

参考文献

[1]石文先，朱新平. 智慧空中交通管理系统及其应用[J]. 南京航空航天大学学报（社会科学版），2013（03）

[2]万健，李楠，李琦. 空中交通管理系统安全评价研究[J]. 北京航空航天大学学报（社会科学版），2013（01）

运筹学指派问题范文第2篇

【关键词】运筹学；交通运输管理；实际

随着科技和社会的不断发展，运筹学作为一门以解决实际问题为主的学科，已经渗入到了很多领域上，尤其是在农业、工业和社会生活中被人们广泛的应用。在进行运筹学的教学中，虽然它属于软科学的中的一种，只是通过理论知识进行研究，但是由于它存在比较强的逻辑思维，在人们学习形成了很大的阻碍。运筹学是系统工程学和现代管理学中的一种基础理论和不可缺少的方法和手段，目前运筹学已被应用到各个管理行业中，对我国现代化的社会建设有着十分重要的作用。

1.运筹学概论

运筹学又被称之为作业研究，是指以应用数学和形式科学的跨领域研究，利用像是统计学、数学模型和算法等方法，去寻找复杂问题中的最佳或近似最佳的解答。它经常用于解答生活中的各种复杂的问题，帮助人们在生活中找到一个属于自己的答案。对于运筹学知识的研究我们主要采用的实分析、矩阵论等方法进行研究，以便挖掘更多的知识。

我们在运用运筹学在处理各种不同的问题时，一般都是采用确定目标、制定方案、建立模型、制定解法这四个方面入手，运用科学的理论来分析问题的实质，这样的处理方案，把复杂的问题瞬间简单化，从而方便人们的解决。所以正是由于，在解决问题是有着系统、全面的分析方法，我们才在各个方面，广泛的运用运筹学。而且在学习中，也有着许多专业和运筹学密不可分，例如应用数学、工业工程、计算机技术等都和运筹学有着密切的联系。

在我国古代，运筹学就开始运用在人们的社会中，但是当时却少一种比较系统全面的分析，人们只能把运筹学通过一种思想传递的方式，在社会中进行运用和传播。当时人们对于运筹学的理解还比较片面，而且涉及范围也比较狭窄，主要就是运用在战争中而对于运筹学的真正发展，那还是在20世纪40年代，那时候运筹学的思想主要是英国和美国提出并用于社会的发展当中，而真正引入我国的时候，是20世纪50年代末。对当时来说这些先进的思想是我国社会主义发展所需要的，因此在通过科学家们的努力下，现在已经建立了一个系统全面的运筹体系，对社会的发展和经济的建设有着重要的意义。

2.运筹学的特点

对运筹学特点的分析，是运筹学发展、前进和开展新思想的唯一方法。目前我们归纳的特点有以下几点：

2.1主要使用数学方法

运筹学在教学和与数学有着密切的联系，在人们对运筹学进行学习时我们不仅要求人们要有比较强的逻辑思维，还要有着一定的数学基础。在对运筹学进行定义的时候，我们就把数学方案作为协助运筹学发展的一件工具。而且这门应用科学在实际操作中也需要，许多数学提供的信息和技巧，才能使其发挥出最大的效率。

2.2以优化思想为核心

运筹学主要就是以最简单的方法对实际科学，做出最优化的判断，以最优化的方法，来解决人们生活中的问题，这样往往会使得人们在社会中得到最大的收益。由于运筹学以这样的思想为核心，因此这就让运筹学形成了一门独特而又严谨的科学。

2.3多学科交叉

运筹学思想广泛解决不同学科领域的问题。解决实际中提出的决策问题，为决策者选择理想方案提供科学依据，同时它综合运用心理学、经济学、化学、物理学、计算机科学和工程技术等学科的理论及方法。既提供量化因素，也进行定性分析，最终能向决策者提供建设性意见，并收到实效。

2.4 应用性

我国在1956年曾用过“运用学”的名词，到1957年正式定名为运筹学。不管是最初仅应用在军事上，还是到最后应用到社会经济等各个领域，运筹学都是扮演着“工具”的角色。运筹学既对各种经营进行创造性的科学研究，又涉及到组织的实际管理问题，它具有很强的实践性。运筹学从来自于企业和生活的实际案例出发，了解事实，理清问题结构，对问题进行量化，建立数学模型，运用运筹学软件求解，最终服务于实际生活。

2.5多分支性

运筹学经过半个多世纪的发展，已经成为具有坚实的理论基础，完善的结构体系，严谨的科学方法的学科。并已有众多分支学科，包括数学规划、图论与网络、排队论、存贮沦、决策论、对策论、设备维修更新理论、搜索论、可靠性理论等。而且每一个分支在实际生活中已经渗透多个领域，得到广泛使用。

3.运筹学在交通运输中的理论体现及应用

3.1教学规划论

数学规划论可以处理成千上万个约束条件和变量的大规模线性规划问题。研究内容与生产活动中有限资源的分配有关，在组织生产的经营管理活动中，具有极为重要的地位和作用。包括线性规划、整数规划、动态规划、应用规划、目标规划等。从解决技术问题的最优化，到工业、农业、商业、交通运输业以及决策分析部门都可以发挥作用。具有适应性强，应用面广，计算技术比较简便的特点。具体地讲，线性规划可解决交通运输系统中物资调运、配送和人员分派等问题。我国曾经利用线性规划理论进行水泥、粮食和钢材的合理调运，取得了较好的经济效益；动态规划可用来解决诸如最优运输路径、资源分配、运输凋度、库存控制、设备更新等同题；应用规划论典型的例子就是“运输问题”，即将数量和单位运价都是给定的某种物资从供应站运送到消费站，在满足供销平衡的同时。定出流量与流向，达到总运输成本最小。应用规划论还可以解决运输系统中合理选址、车辆调度、货物配装、物流资源（人员或设备）指派、投资分配等问题。

3.2图论

图论是一个古老的但又十分活跃的分支，在物流中的应用非常显著。其中最明显的应用体现在运输问题，比如城市间的物资调运、车辆调度时运输路线的选择等。运用了图论中的最小生成树、最短路、最大流、最小费用等知识，可求得运输所需时间最少、路线最短、费用最省的路线等一系列实际问题。另外，运用图论的知识绘制铁路运输系统线路图、公路网的设计和分析、市内公共汽车路线的选择和行车时刻表的安排、出租汽车的词度和停车场的设立等，可辅助决策者进行最优的安排。

3.3排队论

排队论主要研究各种系统的排队队长、等待时间和服务等参数，解决系统服务设施和服务水平之问的平衡问题。以较低的投入求得更好的服务。现实生活中排队现象普遍存在，如运输站车辆进出站的排队，商店顾客排队付款、客服中心顾客电话排队等待服务等。交通领域中也有多见。在高速公路收费站服务台的设计与管理中运用排队论进行定量分析，运用排队论知识对其进行优化和设计，并建立速公路收费站服务台与工作人员的配备模型，对避免盲目确定收费亭建设规模大小，提高收费站服务台的服务和管理水平，降低运营成本等方面发挥重要作用。

3.4对策论

对策论是一种定量分析方法，可以帮助我们寻找最佳的竞争策略。以便战胜对手或者减少损失。在市场经济条件下，交通行业也充满了竞争。例如在一个城市内有两个配送中心经营相同的业务，为了争夺市场份额，双方都有多个策略可供选择，可以运用对策论进行分析，寻求最佳策略。又如，某一地区，汽车运输公司要与铁路系统争夺客源，有多种策略可供选择，也可用对策论研究竞争方案，最终获得利益的最大化。对策论可以在竞争性定价、新服务的推出、销售计划的制定、加强广告与宣传、新设备的引入等方面发挥作用。

运筹学指派问题范文第3篇

关键字：运筹学；企业管理

运筹学问题和运筹思想可以追溯到古代，它和人类实践活动的各种决策并存。现在普遍认为，运筹学是近代应用数学的一个分支，主要是将生产、管理等事件中出现的一些带有普遍性的运筹问题加以提炼，然后利用数学方法进行解决。界定运筹学作为在科学界的一门独立学科的出现，应当说是在1951年，即P.M.Morse和G.E.Kimball的专著“运筹学方法”出版的那一年。运筹学的思想贯穿了企业管理的始终，运筹学对各种决策方案进行科学评估，为管理决策服务，使得企业管理者更有效合理地利用有限资源。优胜劣汰，适者生存，这是自然界的生存法则，也是企业的生存法则。只有那些能够成功地应付环境挑战的企业，才是得以继续生存和发展的企业。作为企业的管理者，把握并运用好运筹学的理念定会取得“运筹帷幄之中，决胜千里之外”之功效。

一、企业发展原则与战略管理

企业战略管理是企业在宏观层次通过分析、预测、规划、控制等手段，充分利用本企业的人、财、物等资源，以达到优化管理，提高经济效益的目的。随着我国经济市场化的日益加深，市场竞争日趋激烈，我国企业面临着更多的环境因素的影响与冲击。企业要求得生存与发展，必须运筹帷幄，长远谋划，根据自身的资源来制定最优的经营战略，以战略统揽全局。企业战略过程包括，明确企业战略目标，制定战略规划，作出和执行战略决策，并最后对战略作出评价。企业战略管理作为企业管理形态的一种创新，应是以市场为导向的管理、是有关企业发展方向的管理、是面向未来的管理、是寻求内资源与外资源相协调的管理、是寻找企业的长期发展为目的。也就是将企业看作一个系统，来寻求系统内外的资源合理分配与优化，这正体现了运筹学的思想。我国企业战略管理的内容应根据自己的国情，制定对应的战略。主要侧重规定企业使命、分析战略环境、制定战略目标。中国现在绝大部分商品已由卖方市场转为买方市场，知识经济正向我们走来，全球经济一体化的程度在加深，我国企业不仅直接参与国内市场，还将更直接面临与世界跨国公司之间的角逐，企业间竞争的档次和水平日益提高，因而企业将面临更加复杂的竞争环境。只有确定了宏伟的奋斗目标，才能使企业凝集全部的力量，众志成城，向一个共同方向努力，争取实现有限资源的最有效的利用。显然，运筹学理念的作用举足轻重。

二、企业生产计划与市场营销

1、生产计划。使用运筹学方法从总体上确定适应需求的生产、贮存和劳动力安排等计划，以谋求最大的利润或最小的成本，运筹学主要用线性规划、整数规划以及模拟方法来解决此类问题。线性规划问题的数学模型是指求一组满足一个线性方程组（或线性不等式组，或线性方程与线性不等式混合组）的非负变量，使这组变量的一个线性函数达到最大值或最小值的数学表达式.

建立数学模型的一般步骤：

（1）确定决策变量（有非负约束）；对于一个企业来说，一般是直生产某产品的计划数量。

（2）写出目标函数（求最大值或最小值）确定一个目标函数；

（3）写出约束条件（由等式或不等式组成）.约束条件包括指标约束需求约束、资源约束等；

（4）最后根据目标函数为作出最合适的企业生产计划决策。

2、市场营销。一个市场研究专家试图用数据证明消费者的洞察多么有意义，而一个战略管理咨询专家则强调成功营销案例中隐藏的思路更有价值。我认为市场营销管理的任务主要是探查决策环境，进行数据和信息的搜集、加工、分析，确定影响决策的因素或条件。因此，在确定目标阶段实际上包含了问题识别和问题诊断两个内容。在设计方案阶段要理解问题，建立模型，进行模拟，并获得结论，提供各种可供选择的方案（方案主要通过对产品、价格、销售渠道、促销等基本环境的控制来影响消费需求的水平、时机和构成）。评价方案阶段要根据确定的决策准则，从可行方案中选择出最优或满意的方案。这些都都可以使用运筹学的理念来为管理者提供辅助决策。三、企业库存管理与运输问题

1、库存管理。如果说生产计划是从信息流的角度指挥、控制生产系统的运行，那么库存的管理则是从物质流的角度来指挥和控制。库存管理的目标是如何最有效的利用企业的物质资源的问题。

由于库存的物质属性，因此对生产系统的日常运行具有更直接的作用，库存是指处于存储状态的物品或商品。库存具有整合需求和供给，维持各项活动顺畅进行的功能。而库存的存在又意味着占用资金、面积、资源，这种矛盾的处境导致了库存管理的必要性与难度。现在流行的库存管理系统的库存管理软件，一般含货品进货、出货管理系统，仓库管理系统，报表系统等子模块等，运用的原理还是运筹学模型。

2、运输问题。在企业管理中经常出现运输范畴内的问题，例如，工厂的原材料从仓库运往各个生产车间，各个生产车间的产成品又分别运到成品仓库。这种运输活动一般都有若干个发货地点（产地）、又有若干个收货地点（销地）；各产地有一定的可供货量（产量）；各销地各有一定的需求量（销量）；运输问题的实质就是如何组织调运，才能满足各地地需求，又使总的运输费用（公里数、时间等）达到最小。运输模型是线性规划的一种特殊模型。这模型不仅实用于实际物料的运输问题，还实用于其它方面：新建厂址的选择、短缺资源的分配问题、生产调度问题等。

四、企业人事管理与财务管理

1、人事管理。随着知识经济的到来，现代企业的竞争已经变成人才的竞争。知识经济条件下，经济发展中的知识含量高，对过去一直贯穿和渗透于农业和工业经济中的知识的作用就凸显得日益突出，知识经济时代的到来，是知识成为社会的主要财富，知识和信息逐步成为与人力、资金并列的企业第三大“战略资源”。因此，人力资源的竞争已成为企业间竞争的焦点。所以企业应根据自身的特点和发展状况，应该建立战略导向型的人力资源管理，根据客户总部与下属公司不同的架构，建立对应的人力资源管理模式，最大程度地通过战略纽带将“分割”的人力资源管理职能整合起来，带动企业文化、企业管理等的全面提升，以内部管理的完善获取市场竞争中的优势。这显然蕴涵的是运筹学的理念。还可以用指派问题对人员合理分配；用层次分析方法可以确定一个人才评价体系等。

2、财务管理。运筹学的理念在财务与会计中显得更为突出也就是说它解决企业如何最有效的利用资金资源的问题。其涉及到投资决策分析、成本核算分析、证券管理等。在投资决策分析中，企业如何利用剩余资金，如何投资往往有多种方案。而运筹学的作用就是要要对这些不同的投资方案进行决策，以确定最优的方案，使得企业的收益最大。通常是利用线性规划模型、决策论来进行判断。

参考文献：

[1]曹敬东，“管理科学之运筹学在企业中的应用初探”，科技资讯，2007（2).

运筹学指派问题范文第4篇

【关键词】整数规划 选课模型 最优解

1．整数规划原理。在整数规划中，为了满足整数的要求，初看起来似乎只要把已得的非整数解舍入化整就可以了。实际上化整后的数不见得是可行解和最优解，所以应该有特殊的方法来求解整数规划。在整数规划中，如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。整数规划的一种特殊情形是0－1规划，它的变数仅限于0或1。0－1规划在整数规划中占有重要地位，可以解决许多实际问题，例如指派问题、选地问题、送货问题等等。

0－1整数规划的一般模型是：

2．课程优选模型的建立。

2．1 问题的提出。现在，多数高校采取的都是学分制，大学课程是按学分值进行设置的，大学生学费主要依据按学分多少收取。学生可以根据自己的兴趣爱好选择自己所喜欢的课程，但是不合理的选课将造成学校资源的浪费，同时也将增加学生的选课费用。因此，合理选择所学课程是大学生学习过程中的一个重要组成部分。能否合理优选自己的课程，不但是我们顺利完成学业的关键，还可以为我们自己节约大笔费用，节约学校的教学资源，达到经济合理学好知识的目的。

目前，高校所学课程类型主要有三种：必修课程、限选课程和选修课程。必修课程是必选学科，而限选课程和任选课程则可以根据个人的爱好自己决定。学生可以根据自己的实际情况和学校关于学分选择的规定，采用适合的方法，合理优选出自己的选课计划。我们可以借助0－1整数规划原理建立课程优选模型来解决此问题。下面结合某高校学生的选课实例对课程优选模型予以阐述。

2．2 模型的建立。

某高校学生要求经济合理地选择大三下学期课程。该学期可选课程中包括必修课程共7门，总共17个学分（此7门必修课程未在文中列出）；限选课程共有14门，任选课程有15门。限选课程和任选课程的学分设置情况以及部分课程之间的关系见表1。另外，学校关于选课的相关规定如下：

①所选课程的总学分不能少于26学分；

②任选课的至少选1门；

③限选课的至少选2门；

④必选课的学分为120元/学分，限选课程为108元/学分，任选课程为98元/学分。

我们针对上述情况建立0－1整数规划模型。具体如下：

①选取所选学分总费用最小值作为本问题的目标函数z；

②用xi表示是否选择课程，其中，xi=1表示该课程被选择，xi=0表示该课程未选择；

③若选课程i时必须同时选课程j，则可以用xi-xj=0表示；

④若选课程i前先选课程j，则用 ， 表示；

⑤若两门课程不能同时选，则用 表示。

于是，建立如下的数学规划模型：

2．3 求解模型。用VB编程来求解上述问题，运行结果为：x3=x4=x23=x25=1，其他xi=0。即选修4门课程，课程标号分别是3，4，23，25；本学期的最低学费为2962元。

一般来说，得到一个整数规划问题的最优解是很困难的，所以该整数规划模型的解也不唯一。我们通过对变量的约束进行隐式枚举的方法给出其他一些选课方案，见表2。

由于必修，限选和任选课程学分的费用不一样。所以由表2可以得出，要使费用最低，则在满足模型的情况下，尽量选择费用最低的任选课程，并所选的学分不超过总选修的9个学分。在本文中所给出的所有最优的选课方案中，学费最低的为选修4个学分的限选，5个学分的任选，其总的最低学费为2962元。

3．结束语。本文利用0－1整数规划原理建立模型解决了高校学生课程优选问题。实际上，整数规划原理已广泛应用于我们的生产生活当中，它不仅在工业和工程设计和科学研究方面有许多应用，而且在计算机设计、系统可靠性、编码和经济分析等方面也有新的应用。

参考文献

1 焦永兰主编.《管理运筹学》[M].北京:中国铁道出版社, 2007

2 郭耀煌主编.《运筹学原理与方法》[M].成都:西南交通大学出版社,1994

运筹学指派问题范文第5篇

关键词：不同类型机排序 与位置相关 拒绝 排序

中图分类号：O2 文献标识码：A 文章编号：1674-098X（2015）07（b）-0214-02

排序问题也称调度问题或时间表理论，是运筹学的一个分支，有特别广阔的实际背景和应用前景。铁路上的火车调度，公共服务问题，宇宙飞船的飞行计划，学校课程表的制定等等，都要用到排序理论。在工业生产过程中，工件的加工时间往往依赖于工件的实际加工位置。Mosheiov[1]提出工件的实际加工时间是与工件原有加工时间和位置相关的函数，其中，给出了总时间表长，总完工时间的多项式时间算法。Gordon[2]提出工件的实际加工时间是与工件原有加工时间和位置指数相关的函数，其中，并给出了总时间表长，总完工时间的多项式时间算法。Wang等[3]研究了加工时间与开始加工时间相关的，三台机器同顺序流水作业的排序问题，目标函数为最大完工时间。Gerstl等[4]研究了工件的加工时间与位置相关的、带有拒绝的平行机排序问题，目标函数为总完工时间。研究表明当机器的数量固定时，此问题可以转化成指派问题。Wang等[5]研究了带有指数学习效应和一般函数退化效应的单机排序问题，其中工件的加工时间是由工件的开始加工时间和工件的位置决定的，目标函数分别为最大完工时间和总完工时间，证明了它们是多项式时间可解的。Kuo等[6]证明了问题是多项式时间可解的，算法复杂性为。Kuo等[7]证明了在给定每台机器加工的工件数前提下，问题是多项式时间可解的。

1 问题描述

假设有个工件，需要在台变速处理机上被加工。在工件存在拒绝的情况下，即工件可能不被加工，但由此可能产生已定的代价。其中接受工件的个数为，拒接工件个数为，。接受工件在台变速处理机上加工，每台处理机的容量是一定的，分别为，且。如果工件被拒绝，则有一个惩罚费用。

工件的实际加工时间与工件的基本加工时间和其在处理机上的位置相关，即。工件的总完工时间为。该文研究带有拒绝情况下，加工时间与位置相关的不同类型机排序问题，运用三参数表示法，表示为：

2 主要性质

假设1.在工件的加工过程中，机器无空闲。即工件在第台处理机第个位置加工，第位置不能为空，若为空，工件必须放置在第个位置。

引理1.工件在每台工件上的完工时间分别为：

定理1.问题存在时间复杂性为的最优算法。

证明：工件的总完工时间为：

则带有拒绝的目标函数可化简为：

（1）

由上式可知，这个问题可以转化成指派问题。矩阵的行表示被加工工件，矩阵的列表示工件可能被加工的位置。矩阵包含两块（接受矩阵和拒绝矩阵），分别表示有个加工工件和个拒绝工件。对于一个给定向量，机器有列个位置分配。由于不知道工件被拒绝的数量，第二块包含列，第二块的维数为。因此，指派矩阵的总维数为。

下面，先定义矩阵的费用值。第一块包含工件的加工时间与它们在相应机器上位置权的乘积。通过等式（1），在机器上位置的位置权：

第二块对角线上的值为，其余均为无穷。为了方便起见，定义第二块（也就是拒绝工件）作为第台机器。这台机器包含个可能排列的位置，这意味着这块包含列，位置从到。定义的值：

它表示把工件指派在机器上位置的费用。另外，令为变量，如果工件排在机器上位置时，；否则。因此，上面讨论的排序问题可以归结为下面的指派问题：

对于一个给定的向量，当时，可能取值为。如果已知前台机器的工件数且，那么最后一台机器加工的工件数也唯一确定。得出分配向量的数量上界为。该过程需要重复执行所有可能的次，（）。因此，该问题要运行的总次数为。已知指派问题的算法复杂性为，因此问题存在时间复杂性为的多项式时间算法。

3 结论

该文研究带有拒绝的不同类型机排序问题，工件的实际加工时间是与工件位置的一般函数，目标函数是极小化接受工件的排序指标与拒绝工件总惩罚之和。通过将问题转化为指派问题，证明了问题是多项式可解的。对于其他目标函数，如最大完工时间，总误工工件数和最大延误时间等，也可进行研究，我们将继续努力。

参考文献

[1]Mosheiov G. A note on scheduling deteriorating jobs[J].Mathematical and ComputeModelling，2005， 41（8）：883-886.

[2]Gordon V S， Potts C N， Strusevich V A， et al. Single machine scheduling models with deterioration and learning： handling precedence constraints via priority generation[J].Journal of Scheduling，2008， 11（5）：357-370.

[3]WANG Jibo， WANG Mingzheng. Minimizing makespan in three-machine flow shops with deteriorating jobs[J].Comput Oper Res，2013， 40（2）：547-557.

[4]Gerstl E， Mosheiov G. Scheduling on parallel identical machines with job-rejection and position-dependent processing times[J].Inf Process Lett， 2012，112（19）：743-747.

[5]WANG Jibo， Hsu C J， Yang D L. Single-machine scheduling with effects of exponential learning and general deterioration[J].Appl Math Modell，2013，37（4）：2293-2299.