Models and algorithms for a staff scheduling problem

We present mathematical models and solution algorithms for a family of staff scheduling problems arising in real life applications. In these problems, the daily assignments to be performed are given and the durations (in days) of the working and rest periods for each employee in the planning horizon are specified in advance, whereas the sequence in which these working and rest periods occur, as well as the daily assignment for each working period, have to be determined. The main objective is the minimization of the number of employees needed to perform all daily assignments in the horizon. We decompose the problem into two steps: the definition of the sequence of working and rest periods (called pattern) for each employee, and the definition of the daily assignment to be performed in each working period by each employee. The first step is formulated as a covering problem for which we present alternative ILP models and exact enumerative algorithms based on these models. Practical experience shows that the best approach is based on the model in which variables are associated with feasible patterns and generated either by dynamic programming or by solving another ILP. The second step is stated as a feasibility problem solved heuristically through a sequence of transportation problems. Although in general this procedure may not find a solution (even if one exists), we present sufficient conditions under which our approach is guaranteed to succeed. We also propose an iterative heuristic algorithm to handle the case in which no feasible solution is found in the second step. We present computational results on real life instances associated with an emergency call center. The proposed approach is able to determine the optimal solution of instances involving up to several hundred employees and a working period of up to 6 months. Mathematics Subject Classification (2000): 90B70, 90C10, 90C27, 90C39, 90C57, 90C59     

多次分组会议安排的最佳混合方案

本文在仔细分析问题条件和要求的基础上,运用了运筹学、图论、矩阵理论和置换等方面的知识和技巧,建立了一个布尔规划模型。     

Flight gate scheduling with respect to a reference schedule

This paper considers the problem of assigning flights to airport gates. We examine the general case in which an aircraft serving a flight may be assigned to different gates for arrival and departure processing and for optional intermediate parking. Restrictions to this assignment include gate closures and shadow restrictions, i.e., the situation where certain gate assignments may cause blocking of neighboring gates. The objectives include maximization of the total assignment preference score, a minimal number of unassigned flights during overload periods, minimization of the number of tows, maximization of a robustness measure as well as a minimal deviation from a given reference schedule. We show that in case of a one period time horizon this objective can easily be integrated into our existing model based on the Clique Partitioning Problem. Furthermore we present a heuristic algorithm to solve the problem for multiple periods.     

A Fast,Network-based,Hybrid Heuristic for the Assignment of Students to Schools

In an era of declining and fluctuating enrolments, the determination of appropriate school sizes and student assignments poses difficult problems for administrators. For two decades, researchers have worked with variants of a linear programming districting model which minimizes total weighted distance as all students are assigned to schools constrained by both capacity and racial balance limitations. This model could aid in the generation of districting alternatives, but is difficult to solve in realistic applications with generalized solution procedures because of overall problem size. This has prompted the development of fast, network-based models, solvable with special algorithms and codes. We show, however, that these approaches all contain major shortcomings. We present a fast, hybrid heuristic based upon two network representations. Computational results demonstrate this to be a very fast solution approach for the general case of this districting problem.     

A repeated matching heuristic for the single-source capacitated facility location problem

Facility location models form an important class of integer programming problems, with application in many areas such as the distribution and transportation industries. An important class of solution methods for these problems are so-called Lagrangean heuristics which have been shown to produce high quality solutions and which are at the same time robust. The general facility location problem can be divided into a number of special problems depending on the properties assumed. In the capacitated location problem each facility has a specific capacity on the service it provides. We describe a new solution approach for the capacitated facility location problem when each customer is served by a single facility. The approach is based on a repeated matching algorithm which essentially solves a series of matching problems until certain convergence criteria are satisfied. The method generates feasible solutions in each iteration in contrast to Lagrangean heuristics where problem dependent heuristics must be used to construct a feasible solution. Numerical results show that the approach produces solutions which are of similar and often better than those produced using the best Lagrangean heuristics.     

A dynamic principal-agent problem as a feedback Stackelberg differential game

We consider situations in which a principal tries to induce an agent to spend effort on accumulating a state variable that affects the well-being of both parties. The only incentive mechanism that the principal can use is a state-dependent transfer of her own utility to the agent. Formally, the model is a Stackelberg differential game in which the players use feedback strategies. Whereas in general Stackelberg differential games with feedback strategy spaces the leader’s optimization problem has non-standard features that make it extremely hard to solve, in the present case this problem can be rewritten as a standard optimal control problem. A linear-quadratic example is used to illustrate our approach.     

On Multi-threaded Metrical Task Systems

Traditionally, on-line problems have been studied under the assumption that there is a unique sequence of requests that must be served. This approach is common to most general models of on-line computation, such as Metrical Task Systems. However, there exist on-line problems in which the requests are organized in more than one independent thread. In this more general framework, at every moment the first unserved request of each thread is available. Therefore, apart from deciding how to serve a request, at each stage it is necessary to decide which request to serve among several possibilities.In this paper we introduce Multi-threaded Metrical Task Systems, that is, the generalization of Metrical Task Systems to the case in which there are many threads of tasks. We study the problem from a competitive analysis point of view, proving lower and upper bounds on the competitiveness of on-line algorithms. We consider finite and infinite sequences of tasks, as well as deterministic and randomized algorithms. In this work we present the first steps towards a more general framework for on-line problems which is not restricted to a sequential flow of information.     

Balanced home–away assignments

In recent years several approaches for generating sports league schedules have been proposed. In this paper we consider foundations for a two-stage approach to construct schedules for a single round robin tournament (or the first half series of a double round robin tournament). In the first stage for each game a mode (home or away) has to be determined and in the second stage the games have to be scheduled in their assigned modes. We study a problem of the first stage where balanced home–away assignments have to be constructed such that for each team the numbers of home and away games differ by at most one. After showing that it is easy to construct balanced home–away assignments we propose repairing mechanisms for unbalanced home–away assignments. Then, neighborhoods on the set of balanced home–away assignments are defined which are shown to be connected. Finally, situations with preassignments are studied.     

Tabu search for a class of scheduling problems

Scheduling problems are often modeled as resourceconstrained problems in which critical resource assignments to tasks are known and the best assignment of resource time must be made subject to these constraints. Generalization toresource scheduling, where resource assignments are chosen concurrently with times results is a problem which is much more difficult. A simplified model of the general resource scheduling model is possible, however, in which tasks must be assigned a singleprimary resource, subject to constraints resulting from preassignment ofsecondary, or auxiliary, resources. This paper describes extensions and enhancements of tabu search for the special case of the resource scheduling problem described above. The class of problems is further restricted to those where it is reasonable to enumerate both feasible time and primary resource assignments. Potential applications include shift oriented production and manpower scheduling problems as well as course scheduling where classrooms (instructors) are primary and instructors (rooms) and students are secondary resources. The underlying model is a type of quadratic multiple choice problem which we call multiple choice quadratic vertex packing (MCQVP). Results for strategic oscillation and biased candidate sampling strategies are shown for reasonably sized real and randomly generated, synthetic, problem instances. The strategies are compared with other variations using consistent measures of solution time and quality developed for this study.     

Platform exploitation in the sharing economy

We model a revenue sharing contract between a sharing economy platform and a freelance service provider, where the latter hides revenue from the former by canceling some assignments and performing them for cash (“platform exploitation”). The platform counters this via costly, imperfect audits with endogenous success probability, and a variable payment. We show that at equilibrium, all agent types except the highest, indulge in revenue falsification. This problem is exacerbated by the principal's ability to extract restitution from the agent.     

Solving Fixed-Charge Network Flow Problems with a Hybrid Optimization and Constraint Programming Approach

We apply to fixed charge network flow (FCNF) problems a general hybrid solution method that combines constraint programming and linear programming. FCNF problems test the hybrid approach on problems that are already rather well suited for a classical 0–1 model. They are solved by means of a global constraint that generates specialized constraint propagation algorithms and a projected relaxation that can be rapidly solved as a minimum cost network flow problem. The hybrid approach ran about twice as fast as a commercial mixed integer programming code on fixed charge transportation problems with its advantage increasing with problem size. For general fixed charge transshipment problems, however, it has no effect because the implemented propagation methods are weak.     

An existence result of a quasi-variational inequality associated to an equilibrium problem

In this paper we consider a Walrasian pure exchange economy with utility function which is a particular case of a general economic equilibrium problem, without production. We assume that each agent is endowed with at least of a commodity, his preferences are expressed by an utility function and it prevails a competitive behaviour: each agent regards the prices payed and received as independent of his own choices. The Walrasian equilibrium can be characterized as a solution to a quasi-variational inequality. By using this variational approach, our goal is to prove an existence result of equilibrium solutions.     

Relaxed voting and competitive location under monotonous gain functions on trees

We examine competitive location problems where two competitors serve a good to users located in a network. Users decide for one of the competitors based on the distance induced by an underlying tree graph. The competitors place their server sequentially into the network. The goal of each competitor is to maximize his benefit which depends on the total user demand served. Typical competitive location problems include the (1,X₁)-medianoid, the (1,1)-centroid, and the Stackelberg location problem.An additional relaxation parameter introduces a robustness of the model against small changes in distance. We introduce monotonous gain functions as a general framework to describe the above competitive location problems as well as several problems from the area of voting location such as Simpson, Condorcet, security, and plurality.In this paper we provide a linear running time algorithm for determining an absolute solution in a tree where competitors are allowed to place on nodes or on inner points. Furthermore we discuss the application of our approach to the discrete case.     

Optimal Distributed Dynamic Advertising

We propose a novel approach to modeling advertising dynamics for a firm operating over a distributed market domain based on controlled partial differential equations of the diffusion type. Using our model, we consider a general type of finite-horizon profit maximization problem in a monopoly setting. By reformulating this profit maximization problem as an optimal control problem in infinite dimensions, we derive sufficient conditions for the existence of its optimal solutions under general profit functions, as well as state and control constraints, and provide a general characterization of the optimal solutions. Sharper, feedback-form characterizations of the optimal solutions are obtained for two variants of the general problem. The first author gratefully acknowledges financial support by the NSF, the DAAD, the SFB 611 (Bonn), and the Max-Planck-Institut für Mathematik (Leipzig) through an IPDE fellowship.     

A generalization of max flow—min cut

We present a theorem which generalizes the max flow—min cut theorem in various ways. In the first place, all versions of m.f.—m.c. (emphasizing nodes or arcs, with graphs directed or undirected, etc.) will be proved simultaneously. Secondly, instead of merely requiring that cuts block all paths, we shall require that our general cuts be weight assignments which meet paths in amounts satisfying certain lower bounds. As a consequence, our general theorem will not only include as a special case m.f.—m.c., but also includes the existence of integral solutions to a transportation problem (with upper bounds on row and column sums) and its dual.     

Constraint-Based Job Shop Scheduling with IILOG SCHEDULER

We introduce constraint-based scheduling and discuss its main principles. An approximation algorithm based on tree search is developed for the job shop scheduling problem using ILOG SCHEDULER. A new way of calculating lower bounds on the makespan of the job shop scheduling problem is presented and we show how such results can be used within a constraint-based approach. An empirical performance analysis shows that the algorithm we developed performs well. Finally, taking the job shop scheduling problem as a start point, we discuss how constraint-based scheduling can be used to solve more general scheduling problems.     

The algebraic regulator problem from the state-space point of view

We study the algebraic aspects of the regulator problem, using some new ideas in the state-space (“geometric”) approach to feedback design problems for linear multi- variable systems. Necessary and sufficient conditions are given for the solvability of a general version of this problem, requiring output stability, internal stability, and disturbance decoupling as well. An algorithm is given by which these conditions can be verified from the system parameters.     

Combined analysis of unique and repetitive events in quantitative risk assessment

For risk assessment to be a relevant tool in the study of any type of system or activity, it needs to be based on a framework that allows for jointly analyzing both unique and repetitive events. Separately, unique events may be handled by predictive probability assignments on the events, and repetitive events with unknown/uncertain frequencies are typically handled by the probability of frequency (or Bayesian) approach. Regardless of the nature of the events involved, there may be a problem with imprecision in the probability assignments. Several uncertainty representations with the interpretation of lower and upper probability have been developed for reflecting such imprecision. In particular, several methods exist for jointly propagating precise and imprecise probabilistic input in the probability of frequency setting. In the present position paper we outline a framework for the combined analysis of unique and repetitive events in quantitative risk assessment using both precise and imprecise probability. In particular, we extend an existing method for jointly propagating probabilistic and possibilistic input by relaxing the assumption that all events involved have frequentist probabilities; instead we assume that frequentist probabilities may be introduced for some but not all events involved, i.e. some events are assumed to be unique and require predictive – possibly imprecise – probabilistic assignments, i.e. subjective probability assignments on the unique events without introducing underlying frequentist probabilities for these. A numerical example related to environmental risk assessment of the drilling of an oil well is included to illustrate the application of the resulting method.     

A general method for finding the optimal threshold in discrete time

We develop an approach for solving one-sided optimal stopping problems in discrete time for general underlying Markov processes on the real line. The main idea is to transform the problem into an auxiliary problem for the ladder height variables. In case that the original problem has a one-sided solution and the auxiliary problem has a monotone structure, the corresponding myopic stopping time is optimal for the original problem as well. This elementary line of argument directly leads to a characterization of the optimal boundary in the original problem. The optimal threshold is given by the threshold of the myopic stopping time in the auxiliary problem. Supplying also a sufficient condition for our approach to work, we obtain solutions for many prominent examples in the literature, among others the problems of Novikov-Shiryaev, Shepp-Shiryaev, and the American put in option pricing under general conditions. As a further application we show that for underlying random walks (and Lévy processes in continuous time), general monotone and log-concave reward functions g lead to one-sided stopping problems.