Online scheduling with reassignment

This paper studies online scheduling problems with reassignment on two identical machines. We can reassign some jobs under certain rules after all the jobs have been assigned. Three different versions are studied and optimal algorithms are proposed.     

From fluid relaxations to practical algorithms for job shop scheduling: the makespan objective

We design an algorithm, called the fluid synchronization algorithm (FSA), for the job shop scheduling problem with the objective of minimizing the makespan. We round an optimal solution to a fluid relaxation, in which we replace discrete jobs with the flow of a continuous fluid, and use ideas from fair queueing in the area of communication networks in order to ensure that the discrete schedule is close to the one implied by the fluid relaxation. FSA produces a schedule with makespan at most C _max+(I+2)P _max J _max, where C _max is the lower bound provided by the fluid relaxation, I is the number of distinct job types, J _max is the maximum number of stages of any job-type, and P _max is the maximum processing time over all tasks. We report computational results based on all benchmark instances chosen from the OR library when N jobs from each job-type are present. The results suggest that FSA has a relative error of about 10% for N=10, 1% for N=100, 0.01% for N=1000. In comparison to eight different dispatch rules that have similar running times as FSA, FSA clearly dominates them. In comparison to the shifting bottleneck heuristic whose running time and memory requirements are several orders of magnitude larger than FSA, the shifting bottleneck heuristic produces better schedules for small N (up to 10), but fails to provide a solution for larger values of N. Received: September 1999 / Accepted: September 2001?Published online March 14, 2002     

A network flow-based method to solve performance cost and makespan open-shop scheduling problems with time-windows

This paper deals with several bicriteria open-shop scheduling problems where jobs are pre-emptable and their corresponding time-windows must be strictly respected. The criteria are a performance cost and the makespan. Network flow approaches are used in a lexmin procedure with a bounded makespan and the considered bicriteria problems are solved. Finally, the computational complexity of the algorithm and a numerical example are reported.     

Hybrid Population-Based Algorithms for the Bi-Objective Quadratic Assignment Problem

We present variants of an ant colony optimization (MO-ACO) algorithm and of an evolutionary algorithm (SPEA2) for tackling multi-objective combinatorial optimization problems, hybridized with an iterative improvement algorithm and the robust tabu search algorithm. The performance of the resulting hybrid stochastic local search (SLS) algorithms is experimentally investigated for the bi-objective quadratic assignment problem (bQAP) and compared against repeated applications of the underlying local search algorithms for several scalarizations. The experiments consider structured and unstructured bQAP instances with various degrees of correlation between the flow matrices. We do a systematic experimental analysis of the algorithms using outperformance relations and the attainment functions methodology to asses differences in the performance of the algorithms. The experimental results show the usefulness of the hybrid algorithms if the available computation time is not too limited and identify SPEA2 hybridized with very short tabu search runs as the most promising variant. This research was mainly done while Luís Paquete and Thomas Stützle were with the Intellectics Group at the Computer Science Department of Darmstadt University of Technology, Germany     

Using a Hybrid Evolutionary Algorithm to Minimize Variance in Response Time for Multimedia Object Requests

This research addresses the scheduling problem of multimedia object requests, which is an important problem in information systems, in particular, for World Wide Web applications. The performance measure considered is the variance of response time which is crucial as end users expect fair treatment to their service requests. This problem is known to be NP-hard. The literature survey indicates that two heuristics have been proposed to solve the problem. In this paper, we present a new heuristic, a hybrid evolutionary heuristic, which is shown to perform much better than the two existing ones, e.g., the overall average errors of the existing ones are 1.012 and 2.042 while the error of the proposed hybrid evolutionary heuristic is 0.154.     

Hybrid Metaheuristics for the Vehicle Routing Problem with Stochastic Demands

This article analyzes the performance of metaheuristics on the vehicle routing problem with stochastic demands (VRPSD). The problem is known to have a computationally demanding objective function, which could turn to be infeasible when large instances are considered. Fast approximations of the objective function are therefore appealing because they would allow for an extended exploration of the search space. We explore the hybridization of the metaheuristic by means of two objective functions which are surrogate measures of the exact solution quality. Particularly helpful for some metaheuristics is the objective function derived from the traveling salesman problem (TSP), a closely related problem. In the light of this observation, we analyze possible extensions of the metaheuristics which take the hybridized solution approach VRPSD-TSP even further and report about experimental results on different types of instances. We show that, for the instances tested, two hybridized versions of iterated local search and evolutionary algorithm attain better solutions than state-of-the-art algorithms.     

Mutual exclusion scheduling with interval graphs or related classes. Part II

This paper is the second part of a study devoted to the mutual exclusion scheduling problem. Given a simple and undirected graph G and an integer k, the problem is to find a minimum coloring of G such that each color is used at most k times. The cardinality of such a coloring is denoted by χ(G,k). When restricted to interval graphs or related classes like circular-arc graphs and tolerance graphs, the problem has some applications in workforce planning. Unfortunately, the problem is shown to be NP-hard for interval graphs, even if k is a constant greater than or equal to four [H.L. Bodlaender, K. Jansen, Restrictions of graph partition problems. Part I. Theoret. Comput. Sci. 148 (1995) 93-109]. In this paper, the problem is approached from a different point of view by studying a non-trivial and practical sufficient condition for optimality. In particular, the following proposition is demonstrated: if an interval graph G admits a coloring such that each color appears at least k times, then χ(G,k)=⌈n/k⌉. This proposition is extended to several classes of graphs related to interval graphs. Moreover, all our proofs are constructive and provide efficient algorithms to solve the MES problem for these graphs, given a coloring satisfying the condition in input.     

THE FFD ALGORITHM FOR THE BIN PACKING PROBLEM WITH KERNEL ITEMS

The FFD algorithm is one of the most famous algorithms for the classical bin packing problem. In this paper,some versions of the FFD algorithm are considered in several bin packing problems. Especially,two of them applied to the bin packing problem with kernel items are analyzed. Tight worst-case performance ratios are obtained.     

Metrics with finite sets of primitive extensions

In this paper, we give a complete characterization for the class of rational finite metrics with the property that the set () of primitive extensions of is finite. Here, for a metric on a setT, a positive extensionm of to a setV T is calledprimitive if none of the convex combinations of other extensions of toV is less than or equal tom. Our main theorem asserts that the following the properties are equivalent: (i) () is finite; (ii) Up to an integer factor, is a submetric of the path metric d ^H of a graphH with |(d ^H )=1; (iii) A certain bipartite graph associated with contains neither isometrick-cycles withk6 nor induced subgraphsK _3,3 ^– . We then show that () is finite if and only if the dimension of the tight span of is at most two. We also present other results, discuss applications to multicommodity flows, and raise open problems.This research was supported by grant 97-01-00115 from the Russian Foundation of Basic Research and a grant from the Sonderforschungsbereich 343, Bielefeld Universität, Bielefeld, Germany.     

Efficiently implementing two methods of the geometrical theory of differential equations: An experience in algorithm and software design

This paper contains an analysis of the two computational schemes for finding the infinitesimal symmetries and conservation laws of arbitrary systems of differential equations. The design of efficient algorithms implementing these computational schemes is described, together with the design of a portable software system, SCoLAr, supporting these algorithms. A test run is listed in the Appendix and the prospect of using the SCoLAr program on middle class personal computers is discussed.     

Machine scheduling with resource dependent processing times

We consider machine scheduling on unrelated parallel machines with the objective to minimize the schedule makespan. We assume that, in addition to its machine dependence, the processing time of any job is dependent on the usage of a discrete renewable resource, e.g. workers. A given amount of that resource can be distributed over the jobs in process at any time, and the more of that resource is allocated to a job, the smaller is its processing time. This model generalizes the classical unrelated parallel machine scheduling problem by adding a time-resource tradeoff. It is also a natural variant of a generalized assignment problem studied previously by Shmoys and Tardos. On the basis of an integer linear programming formulation for a relaxation of the problem, we use LP rounding techniques to allocate resources to jobs, and to assign jobs to machines. Combined with Graham’s list scheduling, we show how to derive a 4-approximation algorithm. We also show how to tune our approach to yield a 3.75-approximation algorithm. This is achieved by applying the same rounding technique to a slightly modified linear programming relaxation, and by using a more sophisticated scheduling algorithm that is inspired by the harmonic algorithm for bin packing. We finally derive inapproximability results for two special cases, and discuss tightness of the integer linear programming relaxations.     

Network Design Via Iterative Rounding Of Setpair Relaxations

A typical problem in network design is to find a minimum-cost sub-network H of a given network G such that H satisfies some prespecified connectivity requirements. Our focus is on approximation algorithms for designing networks that satisfy vertex connectivity requirements. Our main tool is a linear programming relaxation of the following setpair formulation due to Frank and Jordan: a setpair consists of two subsets of vertices (of the given network G); each setpair has an integer requirement, and the goal is to find a minimum-cost subset of the edges of G sucht hat each setpair is covered by at least as many edges as its requirement. We introduce the notion of skew bisupermodular functions and use it to prove that the basic solutions of the linear program are characterized by “non-crossing families” of setpairs. This allows us to apply Jain’s iterative rounding method to find approximately optimal integer solutions. We give two applications. (1) In the k-vertex connectivity problem we are given a (directed or undirected) graph G=(V,E) with non-negative edge costs, and the task is to find a minimum-cost spanning subgraph H such that H is k-vertex connected. Let n=|V|, and let ε<1 be a positive number such that k≤(1−ε)n. We give an -approximation algorithm for both problems (directed or undirected), improving on the previous best approximation guarantees for k in the range . (2)We give a 2-approximation algorithm for the element connectivity problem, matching the previous best approximation guarantee due to Fleischer, Jain and Williamson. * Supported in part by NSERC researchgran t OGP0138432. † Supported in part by NSF Career Award CCR-9875024.     

Scalar conservation laws with moving constraints arising in traffic flow modeling: An existence result

We consider a strongly coupled PDE–ODE system that describes the influence of a slow and large vehicle on road traffic. The model consists of a scalar conservation law accounting for the main traffic evolution, while the trajectory of the slower vehicle is given by an ODE depending on the downstream traffic density. The moving constraint is expressed by an inequality on the flux, which models the bottleneck created in the road by the presence of the slower vehicle. We prove the existence of solutions to the Cauchy problem for initial data of bounded variation.     

NOTE ON INVERSE PROBLEM WITH l∞ OBJECTIVE FUNCTION

In this note, the author proves that the inverse problem of submodular function on digraphs with l∞ objective function can be solved by strongly polynomial algorithm. The result shows that most inverse network optimization problems with l∞ objective function can be solved in the polynomial time.     

The multifit algorithm for set partitioning containing kernels

This pager investigates the set partitioning containing kernels. This problem can alsobe considered as the identical machine scheduling prohlem with nonsimultaneous machine release times. That the algorithm MULTIFIT has a worst ease bound of 6/5 is proved. Throughcombining MULTIFIT and LPT. an algorithm MULTILPT with a worat case bound of 7/6 has been obtained.     

Effective measurement of network vulnerability under random and intentional attacks

The study of the security and stability of complex networks plays a central role in reducing the risk and consequences of attacks or disfunctions of any type. The concept of vulnerability helps to measure the response of complex networks subjected to attacks on vertices and edges and it allows to spot the critical component of a network in order to improve its security. We introduce an accurate and computable definition of network vulnerability which is directly connected with its topology and we analyze its basic properties. We discuss the relationship of the vulnerability with other parameters of the network and we illustrate this with some examples.     

A dynamical model for solving degenerate quadratic minimax problems with constraints

This paper presents a new neural network model for solving degenerate quadratic minimax (DQM) problems. On the basis of the saddle point theorem, optimization theory, convex analysis theory, Lyapunov stability theory and LaSalle invariance principle, the equilibrium point of the proposed network is proved to be equivalent to the optimal solution of the DQM problems. It is also shown that the proposed network model is stable in the sense of Lyapunov and it is globally convergent to an exact optimal solution of the original problem. Several illustrative examples are provided to show the feasibility and the efficiency of the proposed method in this paper.     

An annotated bibliography of combinatorial optimization problems with fixed cardinality constraints

In this paper, we consider combinatorial optimization problems with additional cardinality constraints. In k-cardinality combinatorial optimization problems, a cardinality constraint requires feasible solutions to contain exactly k elements of a finite set E. Problems of this type have applications in many areas, e.g. in the mining and oil industry, telecommunications, circuit layout, and location planning. We formally define the problem, mention some examples and summarize general results. We provide an annotated bibliography of combinatorial optimization problems of which versions with cardinality constraint have been considered in the literature.     

Principal structure of submodular systems and hitchcock-type independent flows

This paper discusses the principal structure of submodular systems due to S. Fujishige. It is shown that the principal structure is the coarsest decomposition that is finer than any decomposition induced by the principal partition with respect to a minimal nonnegative superbase. The concept of Hitchcock-type independent flow is introduced so that previously known results on the principal structures for bipartite matchings, layered mixed matrices and independent matchings can be understood as applications of the present result.