A rank-based approach to the sequential selection and assignment problem

Young H. Chun

doi:10.1016/j.ejor.2005.03.040

2006-10-01

PRE

Young H. Chun *

Robert T. Sumichrast

DOI：10.1016/j.ejor.2005.03.040

原文链接

原文求助

摘要

En 中文

In the classical sequential assignment problem, machines are to be allocated sequentially to jobs so as to maximize the expected total return, where the return from an allocation of job j to machine k is the product of the value x(j) of the job and the weight p(k) of the machine. The set of m machines and their weights are given ahead of time, but n jobs arrive in sequential order and their values are usually treated as independent, identically distributed random variables from a known univariate probability distribution with known parameter values. In the paper, we consider a rank-based version of the sequential selection and assignment problem that minimizes the sum of weighted ranks of jobs and machines. The so-called secretary problem is shown to be a special case of our sequential assignment problem (i.e., m = 1). Due to its distribution-free property, our rank-based assignment strategy can be successfully applied to various managerial decision problems such as machine scheduling, job interview, kidney allocations for transplant, and emergency evacuation plan of patients in a mass-casualty situation. (c) 2005 Elsevier B.V. All rights reserved.

Keyword:

job scheduling

optimal stopping rule

secretary problem

sequential decision