AFSCN scheduling: How the problem and solution have evolved

The Air Force Satellite Control Network (AFSCN) coordinates communications to more than 100 satellites via nine ground stations positioned around the globe. Customers request an antenna at a ground station for a specific time window along with possible alternative slots. Typically, 500 requests per day result in more than 100 conflicts, which are requests that cannot be satisfied because other tasks need the same slot. Scheduling access requests is referred to as the Satellite Range Scheduling Problem (SRSP).This paper presents an overview of three key issues: (1) how has the problem changed over the last 10 years, (2) what algorithms work best and (3) what objective function is appropriate for AFSCN. We compared data sets from 1992 and from 2002/2003 and found significant differences in the problems. Our evaluation of solutions focuses on three algorithms: local search, Gooley’s algorithm from AFIT, and the Genitor genetic algorithm. It can be shown that local search (and therefore metaheuristics based on local search) fail to compete with Gooley’s algorithm and Genitor. Finally, while all prior work on AFSCN minimizes request conflicts, we explore an alternative objective function. Because human schedulers must eventually schedule all requests, it might be better to optimize schedules for “repairability”. Our results suggest that minimizing schedule overlaps makes it easier to fit larger requests into the schedule.     

The k-Client Problem

Virtually all previous research in online algorithms has focused on single-threaded systems where only a single sequence of requests compete for system resources. To model multithreaded online systems, we define and analyze the k-client problem, a dual of the well-studied k-server problem. In the basic k-client problem, there is a single server and k clients, each of which generates a sequence of requests for service in a metric space. The crux of the problem is deciding which client's request the single server should service rather than which server should be used to service the current request. We also consider variations where requests have nonzero processing times and where there are multiple servers as well as multiple clients.We evaluate the performance of algorithms using several cost functions including maximum completion time and average completion time. Two of the main results we derive are tight bounds on the performance of several commonly studied disk scheduling algorithms and lower bounds of on the competitive ratio of any online algorithm for the maximum completion time and average completion time cost functions when k is a power of 2. Most of our results are essentially identical for the maximum completion time and average completion time cost functions.     

Comparison of policies in dynamic routing problems

We consider a company that has to satisfy customers' pick-up requests arriving over time every day. The overall objective of the company is to serve as many requests as possible at a minimum operational cost. When organizing its business the company has to fix some features of the service that may affect both service quality and operational costs. Some of these features concern the time a request is taken into account to plan its service, the associated deadline and the way requests are managed when the system is overloaded. In this paper we analyse several policies that can be implemented by the management of a carrier company in a multi-period context. For example, a company might reject all the requests that cannot be feasibly scheduled or accept all the requests and rely on a backup service in order to serve requests that are difficult to handle. Another interesting issue considered in this paper is the impact of collaborative service where two or more carrier companies, with their own customers, decide to share customers in order to optimize the overall costs. We set up a general framework to allow comparison of alternative service policies. Extensive computational results evaluating the number of lost requests and the distance travelled provide interesting insights.     

The Distributedk-Server Problem—A Competitive Distributed Translator fork-Server Algorithms

We consider thek-server problem23in a distributed setting. Given a network ofnprocessors andkidentical mobile servers, requests for service appear at the processors and a server must reach the request point. In addition to modeling problems in computer networks wherekidentical mobile resources are shared by the processors of the network, this models a realistic situation where the transfer of information is costly and there is no central control that governs the behavior of servers that move around to satisfy requests for service. We give a general translator to transform any deterministic global-control competitivek-server algorithm into a distributed competitive one. As consequences we get poly(k)-competitive distributed algorithms for the line, trees, and the ring. In contrast to the global-control case where there arek-server algorithms with competitive ratio that depends solely onk, we have a lower bound of Ω(max{k, (1/D) ·(log n/log log n)}) on the competitive ratio of any distributedk-server algorithm, where 1/Dis the ratio between the cost to transmit a message and the cost to move a server over the same distance. We also give a distributed version of the Harmonic randomizedk-server algorithm.     

A generic auction algorithm for the minimum cost network flow problem

In this paper we broadly generalize the assignment auction algorithm to solve linear minimum cost network flow problems. We introduce a generic algorithm, which contains as special cases a number of known algorithms, including the -relaxation method, and the auction algorithm for assignment and for transportation problems. The generic algorithm can serve as a broadly useful framework for the development and the complexity analysis of specialized auction algorithms that exploit the structure of particular network problems. Using this framework, we develop and analyze two new algorithms, an algorithm for general minimum cost flow problems, called network auction, and an algorithm for thek node-disjoint shortest path problem.     

Applications of random sampling to on-line algorithms in computational geometry

This paper presents a general framework for the design and randomized analysis of geometric algorithms. These algorithms are on-line and the framework provides general bounds for their expected space and time complexities when averaging over all permutations of the input data. The method is general and can be applied to various geometric problems. The power of the technique is illustrated by new efficient on-line algorithms for constructing convex hulls and Voronoi diagrams in any dimension, Voronoi diagrams of line segments in the plane, arrangements of curves in the plane, and others. This work has been supported in part by the ESPRIT Basic Research Action Nr. 3075 (ALCOM).     

On Dynamic Algorithms for Algebraic Problems

In this paper, we examine the problem of incrementally evaluating algebraic functions. In particular, iff(x₁,x₂,…,x_n) = (y₁, y₂,…,y_m) is an algebraic problem, we consider answering on-line requests of the form “change inputx_ito valuev” or “what is the value of outputy_j?” We first present lower bounds for some simply stated algebraic problems such as multipoint polynomial evaluation, polynomial reciprocal, and extended polynomial GCD, proving an Ω(n) lower bound for the incremental evaluation of these functions. In addition, we prove two time-space trade-off theorems that apply to incremental algorithms for almost all algebraic functions. We then derive several general-purpose algorithm design techniques and apply them to several fundamental algebraic problems. For example, we give antime per request algorithm for incremental DFT. We also present a design technique for serving incremental requests using a parallel machine, giving a choice of either optimal work with respect to the sequential incremental algorithm or superfast algorithms withO(log log n) time per request with a sublinear number of processors.     

Competitive Analysis for the On-line Truck Transportation Problem

In this paper, the on-line k-truck transportation problem (k-OLTTP) whose objects are to be transported between the vertices of a given graph on which there are k mobile trucks to be scheduled is proposed. It is motivated by the research concerning on-line k-truck problem and on-line transportation problem. The goal is to minimize the makespan which is consumed to complete some on-line request sequence. Some preliminary knowledge is introduced and the model of k-OLTTP is established firstly. Two versions of a special case of k-OLTTP, namely 1-OLTTP, have been studied and some results are obtained. For the first version, Open-1-OLTTP, a lower bound of competitive ratio 2 is presented and two optimal on-line algorithms, Reschedule Strategy (RS) and Lay Over Strategy (LOS) respectively, are analyzed. For the second version, Close-1-OLTTP, a lower bound of competitive ratio , where θ is the ratio between the time consumed by the loaded truck and the empty truck to travel the same distance, is also developed and on-line algorithms RS and LOS are proved to have competitive ratio 2. Finally, some interesting remarks concerning OLTTP and its future research are discussed.     

On the on-line maintenance scheduling problem

A machine instantly serves requests but needs to undergo maintenance after serving a maximum of L requests. We want to maximize the number of requests served. In the on-line version, we prove that serving L requests before placing a maintenance is 0.5-competitive and is best possible for deterministic algorithms. We describe a 0.585-competitive randomized algorithm and show an upper bound of \(2L/(3L-1)\). We also analyze the empirical performance of various on-line algorithms on specific arrival distributions.     

极小化总加权完工时间的Dial-a-Ride问题的在线随机算法

讨论一般度量空间上带单服务器的极小化总加权完工时间在线Dial-a-Ride问题.通过应用贪婪区间的技巧,提出了一个一般在线随机算法.根据这个算法,对于容量为1或者任意容量的一般度量空间上的在线Dial-a-Ride问题能得到一个竞争比为(2+√2)/ln(1+√2)的在线随机算法,这个算法不仅具有当前最好的竞争比,而且也改进了Krumke等人的结果.     

Complexity and algorithms for convex network optimization and other nonlinear problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear Knapsack problem's constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. MSC classification: 90C30, 68Q25     

Complexity and algorithms for nonlinear optimization problems

Nonlinear optimization algorithms are rarely discussed from a complexity point of view. Even the concept of solving nonlinear problems on digital computers is not well defined. The focus here is on a complexity approach for designing and analyzing algorithms for nonlinear optimization problems providing optimal solutions with prespecified accuracy in the solution space. We delineate the complexity status of convex problems over network constraints, dual of flow constraints, dual of multi-commodity, constraints defined by a submodular rank function (a generalized allocation problem), tree networks, diagonal dominant matrices, and nonlinear knapsack problem’s constraint. All these problems, except for the latter in integers, have polynomial time algorithms which may be viewed within a unifying framework of a proximity-scaling technique or a threshold technique. The complexity of many of these algorithms is furthermore best possible in that it matches lower bounds on the complexity of the respective problems. In general nonseparable optimization problems are shown to be considerably more difficult than separable problems. We compare the complexity of continuous versus discrete nonlinear problems and list some major open problems in the area of nonlinear optimization. An earlier version of this paper appeared in 4OR, 3:3, 171–216, 2005.     

A pro-active real-time control approach for dynamic vehicle routing problems dealing with the delivery of urgent goods

This paper proposes a new pro-active real-time control approach for dynamic vehicle routing problems in which the urgent delivery of goods is of utmost importance. Without assuming any distribution, stochastic knowledge about future requests is generated using past request information. The generated knowledge is integrated into the transportation process, which is controlled by a Tabu Search algorithm, in order to actively guide vehicles to request-likely areas before requests arrive there. By analyzing the results attained for various test settings, we identify structural diversity as a crucial criterion for classifying the quality of stochastic knowledge attainable from past request information. This criterion provides a promising starting point for assessing the quality of past request information in order to efficiently use the derived stochastic knowledge in real-time control approaches. We prove the efficiency of our approach by a direct comparison with a deterministic approach on test scenarios with varying structural diversity. Thanks to the proposed classification of structural diversity, differences in results obtained among the tested scenarios become explainable.     

Stochastic lot-sizing with backlogging: computational complexity analysis

For a multi-stage stochastic programming problem, one approach is to explore a scenario tree based formulation for the problem and solve the formulation efficiently. There has been significant research progress on how to generate scenario trees in the literature. However, there is limited work on analyzing the computational complexity of the scenario-tree based formulation that considers the number of tree nodes as the input size. In this paper, we use stochastic lot-sizing problems as examples to study the computational complexity issues for the scenario-tree based formulations. We develop production path properties and a general dynamic programming framework based on these properties. The dynamic programming framework allows us to show that the optimal value function is piecewise linear and continuous, which enables us to develop polynomial time algorithms for several different problems, including those with backlogging and varying capacities under certain conditions. As special cases, we develop polynomial time algorithms that run in O(n²){\mathcal{O}(n^2)} and O(n²T log n){\mathcal{O}(n^2T\,{\rm log}\,n)} times, respectively for stochastic uncapacitated and constant capacitated lot-sizing problems with backlogging, regardless of the scenario tree structure.     

Role of Relative <Emphasis Type="Italic">A</Emphasis>-Maximal Monotonicity in Overrelaxed Proximal-Point Algorithms with Applications

A general framework for a class of overrelaxed proximal point algorithms based on the notion of relative A-maximal monotonicity is introduced; then, the convergence analysis for solving a general class of nonlinear variational inclusion problems is explored. The framework developed in this communication is quite suitable, unlike other existing notions of generalized maximal monotonicity, including A-maximal (m)-relaxed monotonicity in literature, to generalize first-order nonlinear evolution equations/evolution inclusions based on the generalized nonlinear Yosida approximations in Hilbert spaces as well as in Banach spaces.     

Algorithms for large scale Shift Minimisation Personnel Task Scheduling Problems

In this paper we introduce the Personnel Task Scheduling Problem (PTSP) and provide solution algorithms for a variant of this problem known as the Shift Minimisation Personnel Task Scheduling Problem (SMPTSP). The PTSP is a problem in which a set of tasks with fixed start and finish times have to be allocated to a heterogenous workforce. Personnel work in shifts with fixed start and end times and have skills that enable them to perform some, but not all tasks. In other words, some personnel are qualified to only perform a subset of all tasks. The objective is to minimise the overall cost of personnel required to perform the given set of tasks. In this paper we introduce a special case in which the only cost incurred is due to the number of personnel (shifts) that are used. This variant of the PTSP is referred to as the Shift Minimisation Personnel Task Scheduling Problem (SMPTSP). While our motivation is a real-life Personnel Task Scheduling Problem, the formulation may also be applied to machine shop scheduling. We review the existing literature, provide mathematical formulations, and develop a heuristic approach for the SMPTSP.     

Competitive strategies for an online generalized assignment problem with a service consecution constraint

This work studies a variant of the online generalized assignment problem, where there are m ? 2 heterogeneous servers to process n requests which arrive one by one over time. Each request must either be assigned to one of the servers or be rejected upon its arrival, before knowing any information of future requests. There is a corresponding weight (or revenue) for assigning each request to a server, and the objective is to maximize the total weights obtained from all the requests. We study the above problem with a service consecution constraint, such that at any time each server is only allowed to process up to d consecutive requests.     

Heuristic algorithms for the operator-based relocation problem in one-way electric carsharing systems

This paper addresses an Electric Vehicle Relocation Problem (E-VReP), in one-way carsharing systems, based on operators who use folding bicycles to facilitate vehicle relocation. In order to calculate the economic sustainability of this relocation approach, a revenue associated with each relocation request satisfied and a cost associated with each operator used are introduced. The new optimization objective maximizes the total profit. To overcome the drawback of the high CPU time required by the Mixed Integer Linear Programming formulation of the E-VReP, two heuristic algorithms, based on the general properties of the feasible solutions, are designed. Their effectiveness is tested on two sets of realistic instances. In the first, all the requests have the same revenue, while, in the second, the revenue of each request has a variable component related to the user’s rent-time and a fixed part related to customer satisfaction. Finally, a sensitivity analysis is carried out on both the number of requests and the fixed revenue component.     

A cyclic-service finite source model with round-robin scheduling

A cyclic-service finite source model with round-robin scheduling is considered. A single server scans sources in a cyclic manner whether there is a request or not. Each request consists of multiple tasks and only one task can be served when the server scans. We provide the exact analysis of the average response time in a heterogeneous finite source model, where the service times of tasks are distributed according to general probability distributions which may be different from one source to another. Further, we derive the Laplace-Stieltjes transform of the probability distribution function of the waiting time.     

Multiple-Project Scheduling with Controllable Project Duration and Hard Resource Constraint: Some Solvable Cases

In many large-scale project scheduling problems, multiple projects are either taking place at the same time or scheduled into a tight sequence in order to efficiently share a common resource. One example of this is the computing resource allocation at an Application Service Provider (ASP) which provides data processing services for multiple paying customers. Typical services provided by ASPs are data mining, payroll processing, internet-based storage backup services and Customer Relation Management (CRM) services. The processing mode of an ASP can be either batch or concurrent, depending on the type service rendered. For example, for CPU intensive or long processing time required services, it would be more economical to processes one customer request at a time in order to minimize the context switching overhead. While the data transaction processes within a service request are subject to certain precedence relationships, the requests from different customers to an ASP are independent of each other, and the total time required to process a service request depends on the computing resource allocated to that request. The related issue of achieving an optimal use of resources at ASPs leads to problem of project scheduling with controllable project duration.In this paper, we present efficient algorithms for solving several special cases of such multi-project scheduling problems with controllable project duration and hard resource constraints. Two types of problems are considered. In type I, the duration of each project includes a constant and a term that is inversely proportional to the amount of resource allocated. In type II, the duration of each individual project is a continuous decreasing function of the amount of resource allocated.