与位置相关并带有拒绝的不同类型机排序问题

摘 要：排序问题是一类具有广泛实际背景的组合最优化问题，应用于众多领域。随着现代工业的发展，排序模型被不断突破。在一些排序模型中，如果所有工件都不被拒绝，当一个工件的加工时间或加工费用太大时，将导致完工时间变大或费用太大，因此需要考虑该工件是否被加工。若工件被拒绝则有一个惩罚费用。该文研究带有拒绝的不同类型机排序问题，工件的实际加工时间是与工件位置的一般函数，目标函数是极小化接受工件的排序指标与拒绝工件总惩罚之和。

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

中图分类号：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.

[6]Kuo W H， Yang D L. Parallel-machine scheduling with time dependent processing times[J]. Theor Comput Sci，2008，393（1）：204-210.

[7]Kuo W H， Hsu C J， Yang D L. A note on unrelated parallel machine scheduling with time-dependent processing times[J].J Oper Res Soc， 2008，60（3）：431-434.