极小化加权完工时间和的无界批量机器并行调度问题

摘要

考虑无界批量机器并行调度中极小化加权完工时间和问题.设有n个工件和m台批加工同型机.每个工件具有一个正权因子、一个释放时间和一个加工时间.每台机器可以同时加工B≥n个工件.一个批次的加工时间是该批次所包含的所有工件的加工时间的最大者.在同一批次中加工的工件有相同的完工时间,即它们的共同开始时间加上该批次的加工时间.给出了一个多项式时间近似方案(PTAS).%This paper considers the problem of scheduling n jobs on m parallel unbounded batch machines to minimize the total weighted completion time. Each job is characterized by a positive weight, a release time and a processing time. Each unbounded batch machine can process up to B (B≥n) jobs as a batch simultaneo usly. The processing time of a batch is the longest processing time among jobs in the batch. Jobs processed in the same batch have the same completion time, I.e., their common starting time plus the processing time of the batch. A polynomial time approximation scheme (PTAS) for this problem is presented.