摘要
设有n个工件J_1,J_2,…,J_n要在一台机器上加工。已知工件J_i的工时(加工时间)是Pi,工期(预定交付期限)是d_i,权(工件误工时,即在工期之后完工所造成的损失)是w_i.记s=(s(1),…,s(n))为1,2,…,n的一个排列(置换),并记S为1,2,…,n所有排列的全体。如何在S中寻找一个排列s,使在按照次序J_(s(1)),J_(s(2))…,J_(s(n))
A branch and bound algorithm is presented for the problem of sequencing n jobs on a single-machine to minimize the weighted number of tardy jobs,which is NP-complete. An optimal sequence in which jobs completed on time are in EDD order is found.We propose and consider the precedence relationship between jobs so that we may reduce branches and pick up the speed of searching.Both Moore-Hodgson's algorithm for non-weighted jobs and Lawler's algorithm for agreeable jobs are special cases of our algorithm.
出处
《应用数学学报》
CSCD
北大核心
1992年第2期194-199,共6页
Acta Mathematicae Applicatae Sinica
基金
国家自然科学基金
