订单带多工类工件时的极小迟后范围问题  

Minimizing the Range of Order Lateness with Multiple Job Classes

作　　者：刘静[1] 孙世杰[2] 陈跃[2] 

机构地区：[1]嘉兴学院数学系,浙江嘉兴314001 [2]上海大学数学系,上海200444

出　　处：《运筹学学报》2006年第3期91-98,共8页Operations Research Transactions

基　　金：浙江嘉兴学院重点课题项目资助(70106005).

摘　　要：本文考虑下述由多工类工件组成的订单的单机排序问题：每一个客户提供一个由若干工件组成的订单,总共n个工件又分成k个类．当机器从加工某类中的工件转向加工不同于它的第i类工件时,需一调整时间si．每一订单有一给定的应交工时间,订单的完工时间定义为该定单所含全部工件完工时的时间．我们希望适当排列这n个工件,使得订单的迟后范围最小．相应这一排序问题,文中依不同的背景给出了以下二种模式：同类工件一起连续加工,工件的完工时间为其所属类中全部工件完工时的时间,用GT,Ba来表示；同类工件一起连续加工,工件的完工时间为其本身的完工时间,用GT,Ja来表示．对于这两种模式的排序同题,我们均证明了其NP-hard性并给出了对应的分枝定界算法．This paper considers a single machine scheduling problem with m customer orders and multiple job classes.Each customer places an order contains several jobs. The jobs in total can be grouped into different classes. When the nlachine changes its processing from the job in a class to a job in a different class, say class i, a non-productive time si is required for setup. There exists a due date for each order. The finish time of an order is the finish time of all its jobs. We wish to schedule these n jobs such that the lateness range of orders is minimized. Corresponding to this scheduling problem, following two different models are considered in this paper： the jobs in the same class must be processed continuously, and the job＇s completion time is the completion time of the batch to which this job is assigned, we denote it by GT, Ba： the jobs in the same class must be processed continuously, and a job is considered completed at the time when it is completed itself, we denote it by GT, Ja. We proved that the scheduling problems corresponding to these two models are NP-hard and construct the branch and bound algorithms for them, respectively.

关 键 词：运筹学 排序 订单问题 迟后范围 NP-HARD 分枝定界算法 

分 类 号：O223[理学—运筹学与控制论]