Sequencing unreliable jobs on parallel machines
Sequencing unreliable jobs on parallel machines
复制标题
在并行机器上对不可靠的作业进行排序
DOI：
10.1007/s10951-008-0076-6
复制
发表时间：
2009
影响因子：
2
通讯作者：
M. Sodhi
中科院分区：
文献类型：
--
作者：
A. Agnetis;P. Detti;M. Pranzo;M. Sodhi
本文解决了由无监督自动化制造中的应用引发的分配和排序问题。在有限的无人监督的持续时间或轮班期间，m 个机器或单元之一要处理 n 个独立的作业。每项工作都有一定的成功概率 pi 以及工作成功执行后获得的奖励 ri 。当作业在处理过程中失败时，处理单元将被阻塞，并且随后调度到该机器上的作业将被阻塞，直到无监督期结束。问题是对机器上的作业进行分配和排序，以使预期的总回报最大化。本文提出了该问题的以下结果和一些扩展：(i) 单机情况的多面体表征，(ii) 即使有两台机器，问题也是 NP 困难的证明，(iii) 循环启发式的近似结果，(iv) 有效上限。大量的计算结果显示了启发式方法的有效性以及对大量实例样本的限制。
This paper addresses an allocation and sequencing problem motivated by an application in unsupervised automated manufacturing. There are n independent jobs to be processed by one of m machines or units during a finite unsupervised duration or shift. Each job is characterized by a certain success probability pi, and a reward ri which is obtained if the job is successfully carried out. When a job fails during processing, the processing unit is blocked, and the jobs subsequently scheduled on that machine are blocked until the end of the unsupervised period. The problem is to assign and sequence the jobs on the machines so that the expected total reward is maximized. This paper presents the following results for this problem and some extensions: (i) a polyhedral characterization for the single machine case, (ii) the proof that the problem is NP-hard even with 2 machines, (iii) approximation results for a round-robin heuristic, (iv) an effective upper bound. Extensive computational results show the effectiveness of the heuristic and the bound on a large sample of instances.