Designing simple appointment systems that under uncertainty in service times, try to achieve both high utilization of expensive medical equipment and personnel as well as short waiting time for patients, has long been an interesting and challenging problem in health care. We consider a robust version of the appointment scheduling problem, introduced by Mittal et al. (2014), with the goal of finding simple and easy-to-use algorithms. Previous work focused on the special case where per-unit costs due to under-utilization of equipment/personnel are homogeneous i.e., costs are linear and identical. We consider the heterogeneous case and devise an LP that has a simple closed-form solution. This solution yields the first constant-factor approximation for the problem. We also find special cases beyond homogeneous costs where the LP leads to closed form optimal schedules. Our approach and results extend more generally to convex piece-wise linear costs. For the case where the order of patients is changeable, we focus on linear costs and show that the problem is strongly NP-hard when the under-utilization costs are heterogeneous. For changeable order with homogeneous under-utilization costs, it was previously shown that an EPTAS exists. We instead find an extremely simple, ratio-based ordering that is 1.0604 approximate.

In many scheduling situations, it is important to consider non-linear functions of job completions times in the objective. This was already recognized by Smith (1956). Recently, the theory community has begun a thorough study of the resulting problems, mostly on single-machine instances for which all permutations of jobs are feasible. However, a typical feature of many scheduling problems is that some jobs can only be processed after others. In this paper, we give the first approximation algorithms for min-sum scheduling with (nonnegative, non-decreasing) non-linear functions and general precedence constraints. In particular, for 1|prec|sum w_j f(C_j), we propose a polynomial-time universal algorithm that performs well for all functions f simultaneously. Its approximation guarantee is 2 for all concave functions, at worst. We also provide a (non-universal) polynomial-time algorithm for the more general case 1|prec|sum f_j(C_j). The performance guarantee is no worse than 2+epsilon for all concave functions. Our results match the best bounds known for the case of linear functions, a widely studied problem, and considerably extend the results for minimizing sum w_jf(C_j) without precedence constraints.

Health care providers are under tremendous pressure to reduce costs and increase quality of their services. It has long been recognized that well-designed appointment systems have the potential to improve utilization of expensive personnel and medical equipment and to reduce waiting times for patients. In a widely influential survey on outpatient scheduling, Cayirli and Veral (2003) concluded that the "biggest challenge for future research will be to develop easy-to-use heuristics." We analyze the appointment scheduling problem from a robust-optimization perspective, and we establish the existence of a closed-form optimal solution--arguably the simplest and best `heuristic' possible. In case the order of patients is changeable, the robust optimization approach yields a novel formulation of the appointment scheduling problem as that of minimizing a concave function over a supermodular polyhedron. We devise the first constant-factor approximation algorithm for this case.

Abstract We investigate issues of complexity related to welfare maximization in congestion games. In particular, we provide a full classification of complexity results for the problem of finding a minimum cost solution to a congestion game, under the model of Rosenthal. We consider both network and general congestion games, and we examine several variants of the problem concerning the structure of the game and the properties of its associated cost functions. Many of these problem variants turn out to be NP‐hard, and some are hard to approximate to within any finite factor, unlessP=NP. We also identify several versions of the problem that are solvable in polynomial time. © 2011 Wiley Periodicals, Inc. NETWORKS, 2012

Abstract We study the route‐guidance system proposed by Jahn, Möhring, Schulz, and Stier‐Moses Operations Research 53 (2005), 600–616 from a theoretical perspective. As system‐optimal guidance is known to be problematic, this approach computes a traffic pattern that minimizes the total travel time subject to user constraints. These constraints are designed to ensure that routes suggested to users are not much longer than shortest paths for the prevailing network conditions. To calibrate the system, a certain measure—called normal length—must be selected. We show that when this length is defined as the travel time at equilibrium, the resulting traffic assignment is provably efficient and close to fair. To measure efficiency, we compare the output to the best solution without guidance and to user equilibria. To measure unfairness, we compare travel times of different users, and show that they do not differ too much. Inefficient or unfair traffic assignments cause users to travel too long or discourage people from accepting the system; either consequence would jeopardize the potential impact of a route‐guidance system. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 48(4), 223–234 2006

An important class of scheduling problems concerns parallel machines and precedence constraints. We consider precedence delays, which associate with each precedence constraint a certain amount of time that must elapse between the completion and start times of the corresponding jobs. Together with ordinary precedence constraints, release dates and delivery times can be modeled in this manner. We present a 4-approximation algorithm for the total weighted completion time objective for this general class of problems. The algorithm is a rather simple form of list scheduling. The list is in order of job midpoints derived from a linear programming relaxation. Our analysis unifies and simplifies that of a number of special cases heretofore separately studied, while actually improving many of the former approximation results.

Local search algorithms for combinatorial optimization problems are generally of pseudopolynomial running time, and polynomial-time algorithms are not often known for finding locally optimal solutions for NP-hard optimization problems. We introduce the concept of $\varepsilon$-local optimality and show that, for every $\varepsilon > 0$, an $\varepsilon$-local optimum can be identified in time polynomial in the problem size and $1/\varepsilon$ whenever the corresponding neighborhood can be searched in polynomial time. If the neighborhood can be searched in polynomial time for a $\delta$-local optimum, a variation of our main algorithm produces a $(\delta + \varepsilon)$-local optimum in time polynomial in the problem size and $1/\varepsilon$. As a consequence, a combinatorial optimization problem has a fully polynomial-time approximation scheme if and only if the problem of determining a better neighbor in an exact neighborhood has a fully polynomial-time approximation scheme.

We consider the scheduling problem of minimizing the average weighted completion time of n jobs with release dates on a single machine. We first study two linear programming relaxations of the problem, one based on a time-indexed formulation, the other on a completion-time formulation. We show their equivalence by proving that a O(n log n) greedy algorithm leads to optimal solutions to both relaxations. The proof relies on the notion of mean busy times of jobs, a concept which enhances our understanding of these LP relaxations. Based on the greedy solution, we describe two simple randomized approximation algorithms, which are guaranteed to deliver feasible schedules with expected objective function value within factors of 1.7451 and 1.6853, respectively, of the optimum. They are based on the concept of common and independent $\alpha$-points, respectively. The analysis implies in particular that the worst-case relative error of the LP relaxations is at most 1.6853, and we provide instances showing that it is at least $e/(e-1) \approx 1.5819$. Both algorithms may be derandomized; their deterministic versions run in O(n 2 ) time. The randomized algorithms also apply to the on-line setting, in which jobs arrive dynamically over time and one must decide which job to process without knowledge of jobs that will be released afterwards.

We present a new class of randomized approximation algorithms for unrelated parallel machine scheduling problems with the average weighted completion time objective. The key idea is to assign jobs randomly to machines with probabilities derived from an optimal solution to a linear programming (LP) relaxation in time-indexed variables. Our main results are a $(2+\varepsilon)$-approximation algorithm for the model with individual job release dates and a $(3/2+\varepsilon)$-approximation algorithm if all jobs are released simultaneously. We obtain corresponding bounds on the quality of the LP relaxation. It is an interesting implication for identical parallel machine scheduling that jobs are randomly assigned to machines, in which each machine is equally likely. In addition, in this case the algorithm has running time O(n log n) and performance guarantee 2. Moreover, the approximation result for identical parallel machine scheduling applies to the on-line setting in which jobs arrive over time as well, with no difference in performance guarantee.

We consider the problem to minimize the total weighted completion time of a set of jobs with individual release dates which have to be scheduled on identical parallel machines.Job processing times are not known in advance, they are realized on-line according to given probability distributions.The aim is to find a scheduling policy that minimizes the objective in expectation.Motivated by the success of LP-based approaches to deterministic scheduling, we present a polyhedral relaxation of the performance space of stochastic parallel machine scheduling.This relaxation extends earlier relaxations that have been used, among others, by Hall et al. [1997] in the deterministic setting.We then derive constant performance guarantees for priority policies which are guided by optimum LP solutions, and thereby generalize previous results from deterministic scheduling.In the absence of release dates, the LP-based analysis also yields an additive performance guarantee for the WSEPT rule which implies both a worst-case performance ratio and a result on its asymptotic optimality, thus complementing previous work by Weiss [1990].The corresponding LP lower bound generalizes a previous lower bound from deterministic scheduling due to Eastman et al. [1964], and exhibits a relation between parallel machine problems and corresponding problems with only one fast single machine.Finally, we show that all employed LPs can be solved in polynomial time by purely combinatorial algorithms.