具有服务等级的三台平行机在线排序问题
摘要：本文研究具有服务等级的三台平行机在线排序问题。我们所说的服务等级是机器和工件都被标注了服务等级,只有当工件的服务等级不低于机器的服务等级时,这个工件才能在该台机器上加工。目标为最小化最大工件完工时间。具有服务等级的平行机排序问题的实际背景是服务业中推行的等级差异服务。本文首先介绍了排序问题产生的背景和一些基本概念，然后介绍了具有服务等级的平行机排序问题已有的相关结果，最后提出了本文主要研究的两类问题以及做出的解答。
目录
摘要1
关键词1
Abstract1
Key words1
引言1
1排序问题介绍1
1.1研究背景1
1.2基本概念 2
1.2.1 机器状况、工件特征、最优准则 2
1.2.2 在线排序、在线算法、竞争比2
1.2.3 问题描述2
1.3已有成果3
1.4本文研究结果3
2主要研究内容4
2.1 问题4
2.1.1 机器的服务等级为1，机器和的服务等级为24
2.1.2 机器和的服务等级为1，机器的服务等级为25
2.2 问题 7
3 结论9
致谢10
参考文献11
具有服务等级的三台平行机在线排序问题
引言
引言
排序问题是组合优化问题中非常重要的一环，是运筹学研究的一个非常活跃的分支。排序问题产生于机器制造业并且广泛地存在于社会生活的各个方面，例如日常生活中市民乘坐公共交通工具（公交、地铁等）上下班、到医院就医、假期外出旅游购票等，如何能够节省时间高效有序的问题；再比如更具体一点儿的，每年春运期间，无数异地工作的劳动者都涌向火车站，铁路部门如何疏导客流的问题等。这些都是排序问题。
1排序问题介绍
1.1研究背景
因为排序问题的广泛存在性，许多专家学者对其进行研讨，而且取得了较大收获。20世界50年代Johson[1]刊登了第一篇排序文章，至今，全球相关论文以及专著已经超过了3000多。现在，排序论知识系统日渐完备，它现在
*好棒文|www.hbsrm.com +Q: %3^5`1^9`1^6^0`7^2#
已经成为各个领域不可或缺的一员。
在大多数服务行业，像铁路运输业、医药业等，我们一般需要根据不同的顾客提供不同的服务。这些现实中出现的问题可以按照接下来的的途径变成本文所说的排序问题，以医院就医的为例：我们把医院里每一个窗口看作是一台台机器，把来医院就医的各种医患看成工件，像军属通道以及紧急窗口这种提供高级服务的看成是标记高等级的机器，服务越高级标记也越高；军属医患和急病病患这种级别优先的医者标记为高级别的工件，所需要的服务越高级的医者标记的等级越高，在这里，仅仅当工件所标注级别大于等于机器被标注级别情况下,这个工件才能置于该台机器加工。
1.2 基本概念
1.2.1 机器状况、工件特征、最优准则
学术界通常通过“三参数表示法”[9]去描述某个实际情况下的排序问题。的含义是机器状况，指代的意思是工件特征，表征的是最优准则。
机器状况里面有很多细分的部分，比如机器类型、数量和环境等与机器有关的各种信息。常见的机器类型有：单机（single machine）、同型平行机(identical parallel machine)、同类平行机(uniform parallel machine)、无关平行机(unrelated parallel machine)、流水作业(flow shop)、有序作业(job shop)、自由作业(open shop)等等[15]。我们这篇文章中的排序问题仅仅用到同型平行机，同型平行机即每一台机器单位时间内完成的工件加工数量也就是机器的加工速度是相同的。
工件特征里面涵盖了工件信息是不是提前可以知道，即我们说的离线和在线；工件被置于机器加工是不是允许中途停止；工件是否需要准备时间；工件之间是否有优先加工关系等等。
我们用最优准则来评判一个排序的好坏，换种说法就是我们决定用怎样的目标函数。最优准则里面包括了两种，一种是极大化，另一种是极小化。针对极小化，我们期望努力得到合理的排序，让这个排序的最大完工时间比每个符合条件的其他排序小；相对应的极大化类似。
1.2.2在线排序、在线算法、竞争比
离线排序是指一个具体例子的相关情况，不管是工件数量，还是工件来的时间以及加工所需要的时间等我们在安排之前了解了。与之相对应的，在线排序是指决定的人要在工件信息不知道的情况下做出抉择。在在线排序里面，工件的相关信息一个个传递出来，作安排的人在安排这个工件的时候对它之后将要来的工件相关情况一点都不知道，就连后面会不会还有工件来都不知道。
在线排序分为两种：一种为列表在线排序，也就是工件被排为表依次显现；另一种是时间在线排序，也就是工件伴着时间被放在机器上加工任意某个时刻仅仅了解已经准备好的工件的相关情况。本文研究中，我们讨论列表在线排序情形。
在线算法是我们解决在线排序问题的主要手段并用竞争比来判定算法的好坏。
在极小化在线排序问题里，对于每一种特定情况求其，就是的上确界，为该在线排序算法获得的目标函数值，为对应的离线排序的最好结果。若没有其他在线排序算法的比该在线排序算法的小，这时在线排序算法的还叫做在线排序算法竞争比的下界。对于极大化在线排序问题，和上面道理一样的，可以定义竞争比的上界，此处不再赘述。
下界能够反映问题的难易，它和算法如何设计的没有关系，只和原问题自己有关系。现在，寻找下界的方法有不少，但是我们最常用的途径是对手法。对手法的基础方式就是想尽办法提供一连串的打破好实例的坏实例，从而让每一个在线算法都不可以一起解决好它们。
1.2.3 问题描述
这里我们给出和，其中对应的服务等级是，对应的服务等级是，，只有当时，才能在上加工。
这里问题的目标函数我们取的是。
若每一个工件所对应的服务等级都大于或等于机器所对应的服务等级，也就是说每一个工件都能在所有机器上加工，那么我们就把具有服务等级的排序问题变化为了经典的平行机排序问题。所以，本文研究的问题有理论方面的价值和比较不错的实际应用前景。
目录
摘要1
关键词1
Abstract1
Key words1
引言1
1排序问题介绍1
1.1研究背景1
1.2基本概念 2
1.2.1 机器状况、工件特征、最优准则 2
1.2.2 在线排序、在线算法、竞争比2
1.2.3 问题描述2
1.3已有成果3
1.4本文研究结果3
2主要研究内容4
2.1 问题4
2.1.1 机器的服务等级为1，机器和的服务等级为24
2.1.2 机器和的服务等级为1，机器的服务等级为25
2.2 问题 7
3 结论9
致谢10
参考文献11
具有服务等级的三台平行机在线排序问题
引言
引言
排序问题是组合优化问题中非常重要的一环，是运筹学研究的一个非常活跃的分支。排序问题产生于机器制造业并且广泛地存在于社会生活的各个方面，例如日常生活中市民乘坐公共交通工具（公交、地铁等）上下班、到医院就医、假期外出旅游购票等，如何能够节省时间高效有序的问题；再比如更具体一点儿的，每年春运期间，无数异地工作的劳动者都涌向火车站，铁路部门如何疏导客流的问题等。这些都是排序问题。
1排序问题介绍
1.1研究背景
因为排序问题的广泛存在性，许多专家学者对其进行研讨，而且取得了较大收获。20世界50年代Johson[1]刊登了第一篇排序文章，至今，全球相关论文以及专著已经超过了3000多。现在，排序论知识系统日渐完备，它现在
*好棒文|www.hbsrm.com +Q: %3^5`1^9`1^6^0`7^2#
已经成为各个领域不可或缺的一员。
在大多数服务行业，像铁路运输业、医药业等，我们一般需要根据不同的顾客提供不同的服务。这些现实中出现的问题可以按照接下来的的途径变成本文所说的排序问题，以医院就医的为例：我们把医院里每一个窗口看作是一台台机器，把来医院就医的各种医患看成工件，像军属通道以及紧急窗口这种提供高级服务的看成是标记高等级的机器，服务越高级标记也越高；军属医患和急病病患这种级别优先的医者标记为高级别的工件，所需要的服务越高级的医者标记的等级越高，在这里，仅仅当工件所标注级别大于等于机器被标注级别情况下,这个工件才能置于该台机器加工。
1.2 基本概念
1.2.1 机器状况、工件特征、最优准则
学术界通常通过“三参数表示法”[9]去描述某个实际情况下的排序问题。的含义是机器状况，指代的意思是工件特征，表征的是最优准则。
机器状况里面有很多细分的部分，比如机器类型、数量和环境等与机器有关的各种信息。常见的机器类型有：单机（single machine）、同型平行机(identical parallel machine)、同类平行机(uniform parallel machine)、无关平行机(unrelated parallel machine)、流水作业(flow shop)、有序作业(job shop)、自由作业(open shop)等等[15]。我们这篇文章中的排序问题仅仅用到同型平行机，同型平行机即每一台机器单位时间内完成的工件加工数量也就是机器的加工速度是相同的。
工件特征里面涵盖了工件信息是不是提前可以知道，即我们说的离线和在线；工件被置于机器加工是不是允许中途停止；工件是否需要准备时间；工件之间是否有优先加工关系等等。
我们用最优准则来评判一个排序的好坏，换种说法就是我们决定用怎样的目标函数。最优准则里面包括了两种，一种是极大化，另一种是极小化。针对极小化，我们期望努力得到合理的排序，让这个排序的最大完工时间比每个符合条件的其他排序小；相对应的极大化类似。
1.2.2在线排序、在线算法、竞争比
离线排序是指一个具体例子的相关情况，不管是工件数量，还是工件来的时间以及加工所需要的时间等我们在安排之前了解了。与之相对应的，在线排序是指决定的人要在工件信息不知道的情况下做出抉择。在在线排序里面，工件的相关信息一个个传递出来，作安排的人在安排这个工件的时候对它之后将要来的工件相关情况一点都不知道，就连后面会不会还有工件来都不知道。
在线排序分为两种：一种为列表在线排序，也就是工件被排为表依次显现；另一种是时间在线排序，也就是工件伴着时间被放在机器上加工任意某个时刻仅仅了解已经准备好的工件的相关情况。本文研究中，我们讨论列表在线排序情形。
在线算法是我们解决在线排序问题的主要手段并用竞争比来判定算法的好坏。
在极小化在线排序问题里，对于每一种特定情况求其，就是的上确界，为该在线排序算法获得的目标函数值，为对应的离线排序的最好结果。若没有其他在线排序算法的比该在线排序算法的小，这时在线排序算法的还叫做在线排序算法竞争比的下界。对于极大化在线排序问题，和上面道理一样的，可以定义竞争比的上界，此处不再赘述。
下界能够反映问题的难易，它和算法如何设计的没有关系，只和原问题自己有关系。现在，寻找下界的方法有不少，但是我们最常用的途径是对手法。对手法的基础方式就是想尽办法提供一连串的打破好实例的坏实例，从而让每一个在线算法都不可以一起解决好它们。
1.2.3 问题描述
这里我们给出和，其中对应的服务等级是，对应的服务等级是，，只有当时，才能在上加工。
这里问题的目标函数我们取的是。
若每一个工件所对应的服务等级都大于或等于机器所对应的服务等级，也就是说每一个工件都能在所有机器上加工，那么我们就把具有服务等级的排序问题变化为了经典的平行机排序问题。所以，本文研究的问题有理论方面的价值和比较不错的实际应用前景。
版权保护: 本文由 hbsrm.com编辑，转载请保留链接: www.hbsrm.com/jsj/xxaq/977.html
