一类资源费用可变的平行机排序问题

A Class of Parallel Machine Scheduling Problem with Varible Time Slot Costs

研究了资源费用可变的排序问题起源于服务系统和某些特定的生产系统,在这些服务系统中均存在着随着资源使用时段的不同而产生不同的费用。在资源费用可变的排序问题中,工件具有整数加工时间,工件在加工过程中允许中断。假定把机器的时间窗口划分为T个单位时间段,在某个时间段使用机器加工工件就要付出相应的费用,要求在给定的时间窗口内加工完所有的工件。问题的目标函数是经典排序的目标函数与所使用的总资源费用之和。对于目标函数为完工时间和与所使用的总资源费用之和的排序问题,给出了2个近似算法。

The scheduling problem with variable time slot costs studied is originated from service system and certain production systems,in which the resource usage costs varies over time period.In the scheduling problem with variable time slot costs,an integer processing time is given for each job the jobs and preemption is allowed.Suppose that the planning horizon consists of T time slots with unit length,the corresponding cost must be paid if some time periods is taken to process jobs,and all the jobs must be processed in the given time horizon.The objective function is one traditional performance measure plus the total time slot costs.For the scheduling problem with the total completion time plus the total time slot costs,two approximation algorithms was presented.