产品中有多个工件时加权情况下的排序问题

The Weighted Scheduling Problem in a Production Having Several Common Components

本文考虑的是工件在单台机器上加工随后组装成产品的下述排序问题：ｎ个产品各由一特殊工件和ｍ个共同工件组成，这ｍ个共同工件分属ｍ个不同的共同工件类，所有的工件在同一台机器上加工．机器在加工一组第ｉ类共同工件前需调整时间ｓｉ＞０（ｉ＝１，２，…，ｍ），一组共同工件中任一工件的完工时间为其所在组中的全部工件完工时的时间，产品的完工时间为其特殊工件和所有共同工件均完工时的时间．目标是适当排列工件加工序使ｎ个产品的加权完工时间和达最小．对该排序问题，在一定条件下，文中给出了一多项式算法．

This paper deals with the following scheduling problem of manufacturing components at a single facility for subsequent assembly into end products: n pro ducts composed of a unique component and m common components, respectively. The m common components belong to m different common component class. All the components are manufactured at a single facility. Before manufacturing a group of i th common components class there is set up time s i >0(i=1,2,…,m) for the machine. The complete time of every component in a group of common components is the time at which all the component in this group are completed. Products' complete time is the time at which its unique component and all its common components are completed. The objective is to schedule the components to minimize the total weighted complete time of n products. We give a polynomial algorithm to our problem.