An important cost issue in multimedia servers is disk load balancing, such that the available hard disks are used as efficiently as possible. Data redundant storage strategies enable a good load balance. We describe two retrieval approaches for these redundant storage strategies: (1) block-based load balancing and (2) time-based load balancing. For each approach we present a model, analyze the complexity of the corresponding retrieval problem, and describe an algorithm.
We consider a bus with finite capacity to which several nodes are connected. Between each node and the bus there is a buffer of finite size. Furthermore, there is a set of data streams, with each stream running from one node to another node. Each stream is to be given a fixed part of the bus and a fixed part of the relevant buffers to use. The problem is to determine for each stream the size of those fixed parts of the bus and buffers and a transmission scheme, such that supply and consumption schedules of each stream are met and buffers neither underflow nor overflow.
We model the above problem and formulate it as an LP-problem. To this LP-formulation we apply a Dantzig-Wolfe decomposition, which leads to a master problem and a sub-problem per stream. The master problem divides the bus and buffer sizes between the different streams. The sub-problem per stream minimizes the bus and buffer usage of a stream provided that a transmission scheme exists. The objective coefficients in a sub-problem result from the master problem. Although each sub-problem is an LP-problem, we use specific algorithms to solve them more efficiently than standard LP-solving methods do.
In this talk I consider two generalizations of the classical job shop scheduling problem. In our basic model there are release times, positive end-start time la gs, and a general precedence graph. As objective we consider the total weighted tardiness.
We use a tabu search algorithm to search for the order in which the operations are processed on each machine. Given an execution order of the operat ions on each machine, we determine optimal starting times by solving a maximum c ost flow problem. The starting times could also be determined by solving a singl e source longest path tree in an acyclic graph. We show that it only costs a sma ll amount of extra computation time to determine the solution to the maximum cos t flow problem. This solution is used to determine the neighborhood for our tabu search algorithm. All sequences in our neighborhood are obtained by swapping certain pairs of adjacent operations. We show that only swaps that possess a certain property can improve the current solution; if no such swap is available in the neighborhood, then the current solution is optimal.
In the second part of the talk we will extend the problem with nonrenewable reso urce constraints. A resource is called nonrenewable if it is actually being cons umed by the operations using it. The nonrenewable-resources that are consumed by an operation must be produced by other operations or delivered by external supp liers before the start of the consuming operation. We will present a tabu search approach for this problem.
E-commerce has called for a greater flexibility in logistics, especially in the delivery of ordered goods. The lack of adequate flexibility in logistics is a major obstacle; logistics service providers can not cope sufficiently with demands for services that fit within the e-commerce paradigm. Up to now, logistics systems were mainly based on fixed chains of processes of which only capacity could vary within limits. Logistics services were realized by choosing from predefined chains and predefined time windows. This is the main reason logistics service providers are not prepared for demands from e-commerce: individualized treatment; full customer control; virtual, decentralized and dynamic environment.
Customer controlled logistics aims at: personalized control; dynamic planning of services; dynamic scheduling of logistics activities; flexible reaction upon unpredictable changes. It is based on a new model for logistics control: Service Controlled Agile Logistics. SCAL treats requested services as individual entities. The realization is controlled by a dedicated agent travelling over Internet in search for resources able to fulfil (parts of) the service requirements. This agent negotiates with relevant resources and plans the necessary activities. When the requested service is actually carried out, it is the same planning agent that escorts the it. Replanning is established whenever activities deviate from what is planned, or when changing circumstances urge to do so. Thus, all available resources are used in the best possible way.
In the SCAL model, the demanders side of service requesting clients is perfectly balanced with the providers side of resource exploiting logistics operators. This mirrors precisely the interdependency of both more or less independent worlds. The feasibility of this approach has been examined in a number of simulations. The presentation zooms in on the background of the SCAL approach and examines the characteristics of the planning agent in some more detail.
Negotiations are considered to play an important role in the interaction process between self-interested agents. We will present an environment in which artificial agents perform one-on-one negotiations over multiple issues simultaneously. The negotiation strategies used by the agents are continuously adjusted to their opponent's behaviour using an evolutionary algorithm (EA). Such a system is a first step to computing efficient negotiation strategies. Another important part of the research involves studying the emergent properties of the EA and comparing the results to game-theoretic predictions. Game theory has been extensively used to study such bargaining problems. Additionally, an extension is presented in which the bargaining agents take into account the fairness of an offer. Fairness is a social factor which appears to have a large impact on the negotiation outcomes. The main subject is preceded by an introduction on game-theoric bargaining and evolutionary algorithms.
This talk will give an overview of my current and planned research. The first part will look at the two-additive-metrics problem. This problem can be described by imagining a traveller that wants to get from A to B in a graph, and wants to minimize both time and expenses. Each edge in the graph is labeled with not only a length, but also a cost. The total cost then is the sum of costs over all edges that lie on the chosen path. Likewise, the total time is the sum of lengths over all edges traversed. This problem is NP-complete. However, a perfect solution can be calculated in polytime if a certain convexity assumption is made.
For non-convex instances of this problem, a multi-agent system can be used that approximates the solution by using bounded communication. Alternatively, a multi-objective evolutionary algorithm (MOEA) could be useful for finding approximate solutions to this problem.
The second part of the talk will be about the possibility of applying MOEAs to dynamic problems, such as on-line scheduling. In dynamic problems, the engineered system constantly needs to adapt to a changing environment. Sometimes, the number of changes that can happen in the environment is limited, and it is feasible to evaluate how the system would perform under each of these prediction models.
We are currently investigating how these prediction models can be treated as objectives in a MOEA.
In this talk we present an overview of transport and distribution problems we are solving in practice. These problems can be divided into three areas:
Each of these questions require their own algorithmic technique. Techniques we apply, and which are proven to be very successful include linear programming, Lagrange relaxation and heuristics (tabu and local search). In the talk we give an outline of these algorithms. We have applied these techniques in projects in the petrochemical, retail and diairy products industry and for logistic service providers.
Current hard disks offer enough performance to simultaneously record and playback several TV programmes with a single disk. In addition, multiple hard disks can be combined to build video servers that can offer video-on-demand functionality to several hundreds of users.
These multimedia applications require disk scheduling and disk allocation algorithms that are quite different from the' traditional' computer applications, where disks are optimized for average performance instead of real-time guarantees. We give an overview of a number of disk scheduling and disk allocation algorithms both for single-disk applications and multiple-disk applications.
Multimedia broadcasting is one of the promising future Internet applications. A key enabling technology is multicast, which is an efficient way of forwarding data along a tree to a large group of receivers in the network.
The deployment of Internet multicast is impeded by a lack of mechanisms for the recovery of lost packets. Retransmitting packets based on (negative) acknowledgements easily leads to implosions of feedback and explosions of retransmissions. Problems are aggravated by the real-time nature of the transfer.
We describe a technique to solve the feedback implosion problem, when packets are restored using erasure codes. In this scenario different receivers can recover from different losses in a block of packets using the same, appropriately encoded packets. The only feedback to the sender needed is the maximum number of lost packets in the group. In our protocol this information is acquired via a sequence of polls. The number of feedback messages satisfies a probabilistic bound which is independent from the loss distribution.
The size of the World Wide Web is increasing at formidable speed every year. This means that there's constantly more and more valuable information on the web, but also means that it is becoming progressively harder to find the right information. World Wide Web search engines are the primary tools that try to address this formidable task, and have to face a number of big problems in order to achieve some efficiency. In this talk we will outline the situation in the World Wide Web search arena, and provide insight on the algorithms developed to search the web. Problems, theoretical solutions, comparison with applied technology in existing search engines, market and advertisement impact, and view into the upcoming future revolution (XML) will be the main topics of the presentation.
The problem of using P processes to write a given value to all positions of a shared array of size N is called the Write-All problem. We present and analyze an algorithm with work load O(N.P^log(x+1/x)), where x = N^(1/log(P)). Our algorithm is a generalization of the naive two-processor algorithm where the two processes each start at one side of the array and walk towards each other until they collide. It improves upon existing algorithms in several ways.
The Write-All problem has interesting counterparts on the World Wide Web.
We study the problem of ordering a collection of n numbers such that the maximum sum of k successive numbers is minimized. The problem occurs in the design of video servers and in-home hard disk recorders.
We present an optimal algorithm for k=2 and a heuristic for k>2. The main focus of the presentation is on proving performance ratios for the heuristic for fixed k and arbitrary n. However, we also present performance ratios for fixed k and fixed n. The performance ratios are tight up to k=6 and we give a lower bound and a upper bound on a tight performance ratio for k>6.
We study some simple buffer management mechanisms for differentiated Services in the internet and analyse their per node behaviour. The differentiated Services architecture provides router mechanisms for aggregate traffic and edge mechanisms for individual flows, that can be used to build services with varying packet loss and packet delays. We provide an analysis for serving two classes of traffic assuming varying arrival processes and different buffer management mechanisms and study the relative merits and demerits of such scheduling mechanisms. Such a study is motivated by the fact that internet in future is also going to transport video and audio services and modifying the existing router mechanisms is necessary to gear up for transport of different classes of traffic. This study is in conformance with the assured forwarding (AF) per hop behaviour (PHB) group of the differentiated services in the internet. We compare the loss and delay behaviours that can be provided using services based on combinations of different buffer management and router mechanisms. The study shows that a very good usage of the buffer space can be obtained by combining threshold and push-out mechanisms, compared to only threshold or only push-out mechanism.
In a multimedia context, providing quality-of-service guarantees to a heterogeneous group of users often involves dynamic sharing of scarce system resources, such as CPU time, disk access time, transmission time, et cetera. The dynamic aspect derives from variability in, e.g., the instantaneous load or bit rate.
The class of weighted fair queuing algorithms provide solutions to the problem of dynamic resource sharing in a fair way. In this talk, I concentrate on one such algorithm and derive properties, drawing upon and extending classical results in the area of periodic scheduling.
The newspaper industry is an example of an industrial branch in which time plays a crucial role. In order to be able to bring the latest news, the printing of the newspapers should start as late as possible. On the other hand, the newspapers have to be delivered to the subscribers in time. The time that is available for printing and distributing the newspapers is therefore limited. As a result of this, the processes of production and distribution are tightly coupled.
We modelled both processes for a regional Dutch newspaper that prints two daily papers in a number of different editions. The goal was to minimize the distribution costs for given time bounds for production and distribution. We developed two algorithms for planning these processes. One algorithm creates the production plan and the distribution plan one after another, the other one creates both plans simultaneously. Both algorithms are tested in a number of situations.
We consider the problem of scheduling the transmissions of data services over digital media such as satellites. In this problem we are given a number of services, such as data files and video fragments, that have to be transmitted to the users at home. Possibly, the services have to be transmitted several times, in which case we talk about different activations.
For each of these activations we have to make reservations to allow their transmission, indicating when they may start, when they stop, and what bit rate is used during their transmission. The latter may vary, within certain bounds, since for a data file, for instance, it does not matter what the actual bit rate is, as long as the entire file is transmitted before a certain deadline. In scheduling terminology, this means that the tasks that are scheduled are `flexible' in their duration and resource needs.
Next to the above time/bit-rate profiles, we have to determine upon the resources used for each of the transmitted services. In our model, resources are multiply capacitated, meaning that they can be used for multiple services simultaneously, as long as the total number they can handle is not exceeded as well as the total bit rate they can handle. Next to this, services generally occupy several resources of the transmission system simultaneously when activated. This resource assignment part resembles that of resource constrained scheduling problems.
In the presentation, we will first present a model of the above scheduling problem, and analyze its computational complexity. Next, we present a two-level approach that is currently being developed. At the first level we use a local search technique to determine a relative ordering of the activations and to determine the resources on which they are scheduled. Given this, we determine at the second level the absolute values of the time points and of the bit rates, for which we use linear programming and column generation.
Nowadays, supply chain design and planning is a hot issue. Many large companies spend a lot of effort in modeling general supply chains. However, generic solution methods for solving instances of these problems cannot be expected to exist.
I will discuss a specific practical supply chain design and planning problem. The model I present is be used by our customer among other things for supporting medium and long term capacity planning.
The model considers creating and moving capacity, producing products, storing finished goods, and distributing products. Furthermore, the underlying multi facility production problem has two kinds of capacity restrictions.
As can be expected, the resulting model is large and hence hard to solve. However, detailed analysis of the model, together with some practical observations enabled us to solve real life instances.
We consider a subproblem of timetabling problems encountered at the highest levels of many Dutch secondary schools. In this problem, we assume that some decisions have already been carried out (e.g., teacher assignment), whereas others have been postponed to a later moment in time (e.g., classroom assignment). The problem shares some characteristics with other school timetabling problems. One of the decisions is to assign lessons to timeslots (timeslot assignment) such that no person has to attend more than one lesson at the same time. Moreover, it is difficult to formulate all requirements as constraints that must be satisfied: there is often a not well-defined area between what is acceptable and what is definitely not There are also features that make timetabling problems in the Netherlands different from those at high schools in some other countries. First, in the highest levels students have the freedom to choose their own curriculum. This implies that the group of students who have chosen one particular subject generally differs from the group for another subject. As for some subjects these groups are too big to be taught to in one classroom, there should be a partitioning of these groups into a given number of subsets, called subjectgroups (subjectgroup assignment). Second, each student should have a reasonable sized group of students of the same level that he or she sees regularly during lessons. That is, we obtain a kind of group binding by introducing studentgroups as subsets of students who will follow all lessons in a subset of their curricula together (studentgroup binding).
More precisely, the timeslot and subjectgroup assignment problem (TSSGAP) is as follows. Let P be the collection of all (studentgroup, subject) pairs. For each (studentgroup, subject) pair (g, v) in P, all students in g have chosen subject v in their curriculum. A subjectgroup assignment is an assignment of (studentgroup, subject) pairs to subjectgroups. Assigning a (studentgroup, subject) pair (g, v) to a subjectgroup k implies assigning all students in g to all lessons for k. Let L be the collection of all lessons. Moreover, each lesson l in L is taught by a teacher to one subjectgroup k. Some lessons have to be taught in specific classrooms. Therefore, we introduce classroom types, and for each classroom type i we have a subset L_i subseteq L and a maximal number of classrooms available. A timeslot assignment is an assignment of lessons to timeslots. A subjectgroup assignment (timeslot assignment) is complete if all pairs p in P (lessons l in L) have been assigned, otherwise it is a partial assignment. A solution of TSSGAP is a subjectgroup assignment and a timeslot assignment. A solution is feasible if and only if
The objective of TSSGAP is to find a feasible complete subjectgroup assignment and a feasible complete timeslot assignment (feasible complete solution).
There are several independent reasons for why TSSGAP is hard to solve from a computational point of view. Amongst others, GRAPH K-COLORABILITY is a special case of TSSGAP. Often, timetabling problems in which
are modeled as finding a vertex coloring in a conflict graph. The transformation is rather trivial: each lesson corresponds to a vertex, two vertices are connected by an edge if at least one person has to attend the corresponding to lessons, and colors play the role of timeslots. In our case, the conflict graph has not been given completely: a large number of edges follow from the subjectgroup assignment, which is also a decision variable. The initial conflict graph contains mainly the cliques introduced by teachers and subjectgroups, and it is assumed that a feasible complete coloring can easily be determined. Suppose we extend a partial subjectgroup assignment by assigning one (studentgroup, subject) pair (g, v) to a subjectgroup k. This implies adding only those edges to the conflict graph which connect lessons to which g has already been assigned and lessons of k. If we are given a feasible complete coloring of the graph before assigning (g, v) to k, then for the resulting new conflict graph the current coloring will be either
These ideas lead to the following two-phase approach for TSSGAP. (We define a timeslot assignment to be feasible if and only if it satisfies constraints C1 up to C5, and a subjectgroup assignment to be feasible if and only if it satisfies C1, C2, and C6.)
// Given: A feasible partial subjectgroup assignment, // and a feasible partial timeslot assignment. Phase 0. Try to determine a feasible complete timeslot assignment. Phase 1. Try to extend the feasible partial subjectgroup assignment step-by-step to a feasible complete subjectgroup assignment while maintaining a feasible complete timeslot assignment.
In Phase 0, a constructive heuristic has been implemented in order to assign all remaining lessons to timeslots. Phase 1 consists of a tree search algorithm with a backtracking mechanism. In both phases we use a tabu search algorithm to find a feasible complete timeslot assignment giving an infeasible complete timeslot assignment.
The success of the approach depends heavily on how general solution techniques like tabu search and tree search make use of problem specific information. We will show how we have adapted these techniques for solving the TSSGAP. Moreover, computational results of solving various real-life instances with our solution approach will be given.
No abstract.
No abstract.