本文考虑了下述由多类工件组成的订单的单机排序问题:每一个客户提供一个由若干工件组成的订单,总共n个工件又分成k个类.当机器从加工某类中的工件转向加工不同于它的第i类工件时,需一调整时间s<,i>,每一订单有一给定的应交工时间.订单的完工时间定义为该订单所含全部工件完工时的时间.我们希望适当排列这n个工件,使得同订单有关的某目标函数达最优值.我们将此类问题称之为订单问题,记为1|s<,f>,order|g,其中s<,f>指机器加工不同类工件前存在调整时间,order表示订单问题,g是目标函数.由于在生产现实中平等对待所有客户的问题十分重要,因此我们考虑的目标函数是使订单的迟后范围最小,即[L<,max>(DC<,i>)-L<,min>(DC<,i>)]的极小化.相应这一排序问题,在第二、三、四章中依不同的背景,我们给出了三种模式.第二章涉及的模式是同类工件一起连续加工,工件的完工时间为其所属类中全部工件完工时的时间,文中用GT,Ba来表示.我们证明了当目标函数是maxL<,min>(OC<,i>)时,该问题是NP-hard的.在此基础上证明了问题1|s<,f>,order,GT,Ba|L<,max>(DC<,i>)-L<,min>(OC<,i>)是NP-hard的,给出了一分枝定界方法并用实例加以说明.第三章中涉及的模式是同类工件一起连续加工,工件的完工时间为其本身,文中用GT,Ja来表示此种模式.在这种模式下,我们仍然可以证明1|s<,f>,order,GT,Ja| maxL<,min>(OC<,i>)是NP-hard的.然后我们证明了问题1| s<,f>,order,GT,Ja|L<,max>(OC<,i>)-L<,min>(OC<,i>)也是NP-hard的.在本章最后提出了一分枝定界方法,并用实例加以说明.第四章中涉及的模式是同类工件不必一起连续加工,工件的完工时间为其本身,文中用Ja来表示.可以发现1|s<,f>,order,Ja|<,max>L<,min>(OC<,i>)是NP-hard的,类似地,1|s<,f>,order,Ja|L<,max>(OC<,i>)-L<,min>(OC<,i>)也是NP-hard的.对于该问题仍然用分枝定界法来解决.