工件可拒绝的分批配送问题研究

考虑工件可拒绝的分批配送问题:一个制造商为一个客户加工n个工件,每个工件既可以被接受加工,也可以被拒绝加工(但要支付拒绝费用),工件加工完之后要安排车辆运送给客户,完工时间为工件送达客户的时间.目标函数为被接受工件的总完工时间、总配送费用和被拒绝工件的总拒绝费用三者之和,文中对处理机为单机的情形给出了多项式时间算法,且证明了两台平行机的情形下该问题是NP-完备的,并给出了伪多项式时间算法.

A Research on Batch Delivery With Job Rejection

Two scheduling problems with batch delivery and job rejection are considened as follows.For the first one,there are njobs to be processed on a single machine.Each job is either be rejected,while a rejection penalty has to be paid,or be accepted and processed on the machine.After processed,the jobs should be delivered by vehicles to the customer.The completion time of a job is the time when it arrives at the customer area.The objective is to minimize the sum of the total completion time and delivery cost of the accepted jobs,and the total rejection penalty of the rejected jobs.A dynamic programming algorithm for this problem is provided,which runs in polynomial time.For the second one,which differs from the first one that jobs are processed by two parallel machines.The second problem is NP-complete,and a pseudo-polynomial time algorithm is given.