Dominance rules for single machine schedule with sequence dependent setup and due date  

作　　者：Xiaochuan LUO Xiao LIU Chengen WANG Zhen LIU 

机构地区：[1]Key Laboratory of Process Industry Automation, Ministry of Education, Shenyang Liaoning 110004, China [2]LOSI, Universite de Technologie de Troyes, Troyes Cedex 10010, France [3]School of Business Administration, Northeast University, Shenyang Liaoning 110004, China

出　　处：《控制理论与应用（英文版）》2005年第4期364-370,共7页

基　　金：ThisworkwassupportedbyEGIDEFoundationofFrance;NationalNaturalScienceFoundationofChina(No.79931000).

摘　　要：Some dominance rules are proposed for the problems of scheduling N jobs on a single machine with due dates, sequence dependent setup times and no preemption. Two algorithms based on Ragatz＇ s branch and bound scheme are developed including the dominance rules where the objective is to minimize the maximum tardiness or the total tardiness. Computational experiments demonstrate the effectiveness of the dominance rules.Some dominance rules are proposed for the problems of scheduling N jobs on a single machine with due dates, sequence dependent setup times and no preemption. Two algorithms based on Ragatz＇ s branch and bound scheme are developed including the dominance rules where the objective is to minimize the maximum tardiness or the total tardiness. Computational experiments demonstrate the effectiveness of the dominance rules.

关 键 词：Dominance role Sequence dependent setup Due date Single machine schedule Branch and bound 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]