Sequencing unreliable jobs on parallel machines |
| |
Authors: | Alessandro Agnetis Paolo Detti Marco Pranzo Manbir S. Sodhi |
| |
Affiliation: | (1) Dipartimento di Ingegneria dell’Informazione, Università di Siena, Via Roma 56, 53100 Siena, Italy;(2) Department of Industrial Engineering, University of Rhode Island, Gilbreth Hall, Kingston, RI 02881, USA |
| |
Abstract: | 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 p i , and a reward r i 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. |
| |
Keywords: | Indexable problems Polymatroids NP-hardness Approximation algorithms Unsupervised manufacturing systems |
本文献已被 SpringerLink 等数据库收录! |
|