The problem of scheduling G groups of jobs on m parallel machines is considered. Each group consists of several identical jobs. We have to find splittings of groups into batches (i.e. sets of jobs to be processed cont...
详细信息
The problem of scheduling G groups of jobs on m parallel machines is considered. Each group consists of several identical jobs. We have to find splittings of groups into batches (i.e. sets of jobs to be processed contiguously) and to schedule the batches on the machines. It is possible for different batches of the same group to be processed concurrently on different machines. However, at any time, a batch can be processed on at most one machine. A sequence-independent machine set-up time is required immediately before a batch of a group is processed. A deadline is associated with each group. The objective is to find a schedule which is feasible with respect to deadlines. The problem is shown to be NP-hard even for the case of two identical machines, unit processing times, unit set-up times and a common deadline. It is strongly NP-hard if machines are uniform, the number of jobs in each group is equal and processing times, set-up times and deadlines are unit. Special cases which are polynomially solvable are discussed. For the general problem, a family {DPepsilon} of approximation algorithms is constructed. A new dynamic rounding technique is used to develop DPepsilon. For any epsilon>0, DPepsilon delivers a schedule in which the completion time of each group is at most (1 + epsilon) times the value of its deadline if there exists a schedule which is feasible with respect to the deadlines. The time complexity of DPepsilon is O(G(2m+1/)epsilon(2m)).
A NP-hard problem (P) of mixed-discrete linear programming is considered which consists in the minimization of a linear objective function subject to a special nonconnected subset of an unbounded polymatroid. For this...
详细信息
Finding a path that satisfies multiple Quality-of-Service (QoS) requirements is vital to the deployment of current emerged services. However, existing QoS routing algorithms are not very efficient and effective at fin...
详细信息
ISBN:
(纸本)9781424456383
Finding a path that satisfies multiple Quality-of-Service (QoS) requirements is vital to the deployment of current emerged services. However, existing QoS routing algorithms are not very efficient and effective at finding such path. Moreover, few works focus on two or more QoS constraints. In this paper, we propose an effective fully polynomial approximation scheme (FPAS) for multiconstrainted path optimal problem based on the technique of auxiliary graph construction. By employing the nonlinear definition of the path constraint and limited iteration of the FPAS itself, our FPAS can not only achieve the complexity reduction but generate a preferable path as well. We further analyze the Markov properties of the entire network and obtain some key parameters to reflect the routing characteristic. We experiment with different scale of random networks and compare our FPAS against previous well known studies. Our results show that FPAS can find path with lower complexity and better quality.
In this paper, a parallel machine scheduling problem was considered , where the processing time of a job is a simple linear function of its starting time. The objective is to minimize makespan. A fullypolynomial time...
详细信息
In this paper, a parallel machine scheduling problem was considered , where the processing time of a job is a simple linear function of its starting time. The objective is to minimize makespan. A fullypolynomial time approximationscheme for the problem of scheduling n deteriorating jobs on two identical machines was worked out. Furthermore, the result was generalized to the case of a fixed number of machines.
暂无评论