1,721,014 research outputs found
Algorithms for multiprocessor scheduling with two job lengths and allocation restrictions
No full textA variant of the High Multiplicity Multiprocessor Scheduling Problem with C job lengths is considered, in which jobs can be processed only by machines not greater than a given index. When C = 2, polynomial algorithms are proposed, for the feasibility version of the problem and for maximizing the number of scheduled jobs
A polynomial algorithm for the multiple knapsack problem with divisible item sizes
No full textA polynomial algorithm for the multiple bounded knapsack problem with divisible item
sizes is presented. The complexity of the algorithm is O(n2 + nm), where n and m are
the number of different item sizes and knapsacks, respectively. It is also shown that the
algorithm complexity reduces to O(n logn +nm) when a single copy exists of each item
A new upper bound for the multiple knapsack problem
No full textIn this paper, a new upper bound for the Multiple Knapsack Problem (MKP) is proposed, based on the idea of relaxing MKP to a Bounded Sequential Multiple Knapsack Problem, i.e., a multiple knapsack problem in which item sizes are divisible. Such a relaxation, called sequential relaxation, is obtained by suitably replacing the items of a MKP instance with items with divisible sizes. Experimental results on benchmark instances show that the upper bound is effective, in terms of quality, when the ratio between the number of items and the number of knapsacks is small
Comparing Lagrangian-based distributed algorithms for parallel machine scheduling problems
No full textIn this paper Lagrangian-based distributed algorithms for scheduling jobs on unrelated parallel machines are presented. In these algorithms, the scheduling process is the result of a cooperation process among several Decision Makers (DMs). DMs have a local knowledge of the system, and the possibility to decide which type of information to exchange each other. Our focus is to investigate the performance of different algorithms based on different knowledge degrees of the parallel machine system. The implementation issues and the effectiveness of the algorithms are analysed via simulation, in which problem instances with job dynamic arrivals are also considered. Copyright © 2009, Inderscience Publishers
Parallel machine scheduling problems with partial information: Distributed decision models and algorithms
No full textIn this paper Lagrangian-based distributed algorithms for
scheduling jobs on unrelated parallel machines are presented. In the
algorithms, the scheduling process is the result of a cooperation process
among several decision makers (DMs). DMs have a local knowledge of
the system, and the possibility to decide which type of information to
exchange each other. Our focus is to investigate the performance of
different algorithms based on different knowledge degrees of the parallel
machine system. The implementation issues and the effectiveness of
the algorithms are analysed via simulation. Extensive experimental results
are reported, allowing to evaluate the trade–off between knowledge
degree and system performance
Message passing resource allocation for the uplink of multicarrier systems
No full textWe propose a novel distributed resource allocation scheme for the up-link of a cellular multi-carrier system based on the message passing (MP) algorithm. In the proposed approach each transmitter iteratively sends and receives information messages to/from the base station with the goal of achieving an optimal resource allocation strategy. The exchanged messages are the solution of small distributed allocation problems. To reduce the computational load, the MP problems at the terminals follow a dynamic programming formulation. The advantage of the proposed scheme is that it distributes the computational effort among all the transmitters in the cell and it does not require the presence of a central controller that takes all the decisions. Numerical results show that the proposed approach is an excellent solution to the resource allocation problem for cellular multi-carrier systems
Optimal power control in OFDMA cellular networks
No full textThis article addresses the problem of allocating users to radio resources in the downlink of an OFDMA cellular system. We consider a classical multicellular environment with a realistic interference model and a margin adaptive approach, i.e., we aim at minimizing total transmission power while maintaining a certain given rate for each user. We discuss computational complexity issues of the resulting model and present a heuristic approach that finds optima under suitable conditions or reasonably good solutions in the general case. Computational experiments show the effectiveness of the proposed heuristic in a comparison with both a commercial state-of-the-art optimization solver and other approaches from the literature. Copyright © 2011 Wiley Periodicals, Inc
A lower bound on the Hamiltonian path completion number of a line graph
No full textGiven a line graph L(G) of a graph G = (V, E), the problem of finding the minimum number of edges to add to L(G) to have a Hamiltonian path on L(G) is considered. This problem, related to different applications, is known to be NP-hard. This paper presents an O(vertical bar V vertical bar + vertical bar E vertical bar) algorithm to determine a lower bound for the Hamiltonian path completion number of a line graph. The algorithm is based on finding a collection of edge-disjoint trails dominating all the edges of the root graph G. The algorithm is tested by an extensive experimental study showing good performance suggesting its use as a building block of exact as well as heuristic solution approaches for the problem
Robust job-sequencing with an uncertain flexible maintenance activity
Full text linkIn this study, the problem of scheduling a set of jobs and one uncertain maintenance activity on a single machine, with the objective of minimizing the makespan is addressed. The maintenance activity has a given duration and must be executed within a given time window. Furthermore, duration and time window of the maintenance are uncertain, and can take different values which can be described by different scenarios. The problem is to determine a job sequence which performs well, in terms of makespan, independently on the possible variation of the data concerning the maintenance. A robust scheduling approach is used for the problem, in which four different measures of robustness are considered, namely, maximum absolute regret, maximum relative regret, worst-case scenario, and ordered weighted averaging. Complexity and approximation results are presented. In particular, we show that, for all the four robustness criteria, the problem is strongly NP-hard. A number of special cases are explored, and an exact pseudopolynomial algorithm based on dynamic programming is devised when the number of scenarios is fixed. Two Mixed Integer Programming (MIP) models are also presented for the general problem. Several computational experiments have been conducted to evaluate the efficiency and effectiveness of the MIP models and of the dynamic programming approach
- …
