Heuristic Estimation of the Efficient Frontier for a Bi‐Criteria Scheduling Problem
研究单机调度中同时最小化完工时间均值和方差的问题，提出一种基于自适应束搜索的启发式方法来估计有效前沿，并通过计算实验验证其有效性。
ABSTRACT 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.