Premium
Heuristic Estimation of the Efficient Frontier for a Bi‐Criteria Scheduling Problem
Author(s) -
De Prabuddha,
Ghosh Jay B.,
Wells Charles E.
Publication year - 1992
Publication title -
decision sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.238
H-Index - 108
eISSN - 1540-5915
pISSN - 0011-7315
DOI - 10.1111/j.1540-5915.1992.tb00407.x
Subject(s) - computer science , mathematical optimization , frontier , efficient frontier , heuristic , scheduling (production processes) , variance (accounting) , single machine scheduling , job shop scheduling , mathematics , portfolio , schedule , accounting , archaeology , financial economics , economics , history , operating system , business
We examine a single‐machine scheduling problem where the objective is to minimize the mean and the variance of the job completion times simultaneously. We seek to identify the efficient frontier which is obtained by parametrically solving a weighted combination of the two criteria. The identification of the true efficient frontier for this problem is notoriously difficult. To estimate the frontier, we propose a heuristic procedure which is quite general and can be applied to other bi‐criteria problems as well. It involves repeated applications of a relatively new technique called beam search in an adaptive manner. To evaluate the proposed procedure, we introduce two measures of performance and conduct a computational study. The results of the study indicate that the procedure is highly effective.