INSIGHTS ON SERVICE SYSTEM DESIGN FROM A NORMAL APPROXIMATION TO ERLANG'S DELAY FORMULA

We show how a simple normal approximation to Erlang's delay formula can be used to analyze capacity and staffing problems in service systems that can be modeled as M/M/s queues. The numbers of servers, s, needed in an M/M/s queueing system to assure a probability of delay of, at most, p can be well approximated by s ≅ p + z_***I-p+, where z_1-p, is the (1 - p)th percentile of the standard normal distribution and ρ, the presented load on the system, is the ratio of Λ, the customer arrival rate, to μ, the service rate. We examine the accuracy of this approximation over a set of parameters typical of service operations ranging from police patrol, through telemarketing to automatic teller machines, and we demonstrate that it tends to slightly underestimate the number of servers actually needed to hit the delay probability target—adding one server to the number suggested by the above formula typically gives the exact result. More importantly, the structure of the approximation promotes operational insight by explicitly linking the number of servers with server utilization and the customer service level. Using a scenario based on an actual teleservicing operation, we show how operations managers and designers can quickly obtain insights about the trade-offs between system size, system utilization and customer service. We argue that this little used approach deserves a prominent role in the operations analyst's and operations manager's toolbags.     

An Edge-Splitting Algorithm in Planar Graphs

For a multigraph G = (V, E), let s V be a designated vertex which has an even degree, and let _G (V – s) denote min{c _G(X) | Ø X V – s}, where c _G(X) denotes the size of cut X. Splitting two adjacent edges (s, u) and (s, v) means deleting these edges and adding a new edge (u, v). For an integer k, splitting two edges e ₁ and e ₂ incident to s is called (k, s)-feasible if _G(V – s) k holds in the resulting graph G. In this paper, we prove that, for a planar graph G and an even k or k = 3 with k _G (V – s), there exists a complete (k, s)-feasible splitting at s such that the resulting graph G is still planar, and present an O(n ³ log n) time algorithm for finding such a splitting, where n = |V|. However, for every odd k 5, there is a planar graph G with a vertex s which has no complete (k, s)-feasible and planarity-preserving splitting. As an application of this result, we show that for an outerplanar graph G and an even integer k the problem of optimally augmenting G to a k-edge-connected planar graph can be solved in O(n ³ log n) time.     

面向相继故障的复杂网络上袭击策略研究

针对复杂网络遭遇随机故障和蓄意攻击引发的相继故障问题,采用网络中节点j上的初始负荷为Lj=βkjα(这里kj表示为节点j的度,α和β是可调参数),并基于崩溃节点负荷局域择优重新分配的原则,提出了一个带有可调参数的相继故障模型.通过度量网络鲁棒性的一个新的指标,即:关键阈值Tc,对比了两种袭击策略下网络上的全局相继故障现象.数值模拟得到了一些有趣而又违背直觉的结论:一方面,当模型中的可调参数α<1时,袭击网络中度最小的节点比袭击度最大的节点更易导致相继故障;而另一方面,当α=1时,两种袭击对网络的破坏几乎是相同的.此外,数值模拟结果也得到了理论解析的验证.     

Approximation and Exact Algorithms for Constructing Minimum Ultrametric Trees from Distance Matrices

An edge-weighted tree is called ultrametric if the distances from the root to all the leaves in the tree are equal. For an n by n distance matrix M, the minimum ultrametric tree for M is an ultrametric tree T = (V, E, w) with leaf set {1,..., n} such that d_T(i, j) M[i, j] for all i, j and is minimum, where d_T(i, j) is the distance between i and j on T. Constructing minimum ultrametric trees from distance matrices is an important problem in computational biology. In this paper, we examine its computational complexity and approximability. When the distances satisfy the triangle inequality, we show that the minimum ultrametric tree problem can be approximated in polynomial time with error ratio 1.5(1 + log n), where n is the number of species. We also develop an efficient branch-and-bound algorithm for constructing the minimum ultrametric tree for both metric and non-metric inputs. The experimental results show that it can find an optimal solution for 25 species within reasonable time, while, to the best of our knowledge, there is no report of algorithms solving the problem even for 12 species.     

Geometry of Semidefinite Max-Cut Relaxations via Matrix Ranks

Semidefinite programming (SDP) relaxations are proving to be a powerful tool for finding tight bounds for hard discrete optimization problems. This is especially true for one of the easier NP-hard problems, the Max-Cut problem (MC). The well-known SDP relaxation for Max-Cut, here denoted SDP1, can be derived by a first lifting into matrix space and has been shown to be excellent both in theory and in practice.Recently the present authors have derived a new relaxation using a second lifting. This new relaxation, denoted SDP2, is strictly tighter than the relaxation obtained by adding all the triangle inequalities to the well-known relaxation. In this paper we present new results that further describe the remarkable tightness of this new relaxation. Let denote the feasible set of SDP2 for the complete graph with n nodes, let F _n denote the appropriately defined projection of into , the space of real symmetric n × n matrices, and let C _n denote the cut polytope in . Further let be the matrix variable of the SDP2 relaxation and X F _n be its projection. Then for the complete graph on 3 nodes, F ₃ = C ₃ holds. We prove that the rank of the matrix variable of SDP2 completely characterizes the dimension of the face of the cut polytope in which the corresponding matrix X lies. This shows explicitly the connection between the rank of the variable Y of the second lifting and the possible locations of the projected matrix X within C ₃. The results we prove for n = 3 cast further light on how SDP2 captures all the structure of C ₃, and furthermore they are stepping stones for studying the general case n 4. For this case, we show that the characterization of the vertices of the cut polytope via rank Y = 1 extends to all n 4. More interestingly, we show that the characterization of the one-dimensional faces via rank Y = 2 also holds for n 4. Furthermore, we prove that if rank Y = 2 for n 3, then a simple algorithm exhibits the two rank-one matrices (corresponding to cuts) which are the vertices of the one-dimensional face of the cut polytope where X lies.     

On Ring Grooming in optical networks

An instance I of Ring Grooming consists of m sets A ₁,A ₂,…, A _m from the universe {0, 1,…, n − 1} and an integer g ≥ 2. The unrestricted variant of Ring Grooming, referred to as Unrestricted Ring Grooming, seeks a partition {P ₁ , P ₂, …,P _k } of {1, 2, …, m} such that for each 1 ≤ i ≤ k and is minimized. The restricted variant of Ring Grooming, referred to as Restricted Ring Grooming, seeks a partition of {1,2,…,m} such that | P _i | ≤ g for each and is minimized. If g = 2, we provide an optimal polynomial-time algorithm for both variants. If g > 2, we prove that both both variants are NP-hard even with fixed g. When g is a power of two, we propose an approximation algorithm called iterative matching. Its approximation ratio is exactly 1.5 when g = 4, at most 2.5 when g = 8, and at most in general while it is conjectured to be at most . The iterative matching algorithm is also extended for Unrestricted Ring Grooming with arbitrary g, and a loose upper bound on its approximation ratio is . In addition, set-cover based approximation algorithms have been proposed for both Unrestricted Ring Grooming and Restricted Ring Grooming. They have approximation ratios of at most 1 + log g, but running time in polynomial of m ^g . Work supported by a DIMACS postdoctoral fellowship.     

Estimating hybrid frequency moments of data streams

We consider the problem of estimating hybrid frequency moments of two dimensional data streams. In this model, data is viewed to be organized in a matrix form (A _i,j )_1≤i,j,≤n . The entries A _i,j are updated coordinate-wise, in arbitrary order and possibly multiple times. The updates include both increments and decrements to the current value of A _i,j . The hybrid frequency moment F _p,q (A) is defined as \(\sum_{j=1}^{n}(\sum_{i=1}^{n}{A_{i,j}}^{p})^{q}\) and is a generalization of the frequency moment of one-dimensional data streams.We present the first \(\tilde{O}(1)\) space algorithm for the problem of estimating F _p,q for p∈[0,2] and q∈[0,1] to within an approximation factor of 1±ε. The \(\tilde{O}\) notation hides poly-logarithmic factors in the size of the stream m, the matrix size n and polynomial factors of ε ^?1. We also present the first \(\tilde{O}(n^{1-1/q})\) space algorithm for estimating F _p,q for p∈[0,2] and q∈(1,2].     

Approximation algorithms for connected facility location problems

We study Connected Facility Location problems. We are given a connected graph G=(V,E) with nonnegative edge cost c _e for each edge e∈E, a set of clients D⊆V such that each client j∈D has positive demand d _j and a set of facilities F⊆V each has nonnegative opening cost f _i and capacity to serve all client demands. The objective is to open a subset of facilities, say , to assign each client j∈D to exactly one open facility i(j) and to connect all open facilities by a Steiner tree T such that the cost is minimized for a given input parameter M≥1. We propose a LP-rounding based 8.29 approximation algorithm which improves the previous bound 8.55 (Swamy and Kumar in Algorithmica, 40:245–269, 2004). We also consider the problem when opening cost of all facilities are equal. In this case we give a 7.0 approximation algorithm.     

Job stress, job strain, and psychological withdrawal among Dutch university staff: towards a dualprocess model for the effects of occupational stress

This study examined the antecedents of job strain (emotional exhaustion, health complaints) and withdrawal behaviour (e.g. lowered organizational commitment) among a cross-sectional sample of 131 academic staff members of the law department of a large Dutch university. Conservation of resources theory (Hobfoll, 1989) provided the theoretical background for this study. Strains and withdrawal behaviours were expected to be most prominent among those who reported having few resources and/or who reported high job demands. Structural equation modelling revealed that this was indeed the case. As predicted, differential patterns of effects emerged for job demands and job resources. Analysis of the effects of four job-specific stressors revealed that especially the structural aspects of a staff member's teaching task (e.g. the number of students in their classes) contributed strongly to perceived job demands. Theoretical and practical implications of the study are discussed.     

Re-forming the traditional organization medical staff

The traditional, two-bylaws-model organized medical staff was created in another age (1919) to serve a simple health care system, controlled by physicians, in which the only players were patients, doctors, nurses, and small hospitals. This medical staff model does not meet the needs of the U.S. health care system of the 1990s. The purpose of this article is to provide the physician executive with a resource to use when he or she is called on to help determine what, if any, changes are needed in his or her organization to make the role of physician leaders more effective. Finding the right answer to this question is part of discovering ways to reduce health care costs without reducing the funds available to pay for direct delivery of health care services. Maintaining traditional, bureaucratic, legalistic organized medical staff activities is a very expensive game that we can no longer afford to play.     

A 6.55 factor primal-dual approximation algorithm for the connected facility location problem

In the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c _e on the edges, a set of facilities ??V, a set of demands (i.e., clients) $\mathcal{D}\subseteq VIn the connected facility location (ConFL) problem, we are given a graph G=(V,E) with nonnegative edge cost c _e on the edges, a set of facilities ℱ⊆V, a set of demands (i.e., clients) D í V\mathcal{D}\subseteq V , and a parameter M≥1. Each facility i has a nonnegative opening cost f _i and each client j has d _j units of demand. Our objective is to open some facilities, say F⊆ℱ, assign each demand j to some open facility i(j)∈F and connect all open facilities using a Steiner tree T such that the total cost, which is ?_{i ? F}f_i+?_{j ? D}d_jc_i(j)j+M?_{e ? T}c_e\sum_{i\in F}f_{i}+\sum_{j\in \mathcal{D}}d_{j}c_{i(j)j}+M\sum_{e\in T}c_{e} , is minimized. We present a primal-dual 6.55-approximation algorithm for the ConFL problem which improves the previous primal-dual 8.55-approximation algorithm given by Swamy and Kumar (Algorithmica 40:245–269, 2004).     

Decision Support for Airline Schedule Planning

Since the 1950s, the operations research community has developed a large number of computer models to aid in the solution of airline scheduling problems. One notable characteristic of these contributions is that each algorithm was developed with its own input and output structures, user interface, and hardware and software requirements. The result is that many of these contributions are under-utilized because they are cumbersome to use, not integrated with the other airline's systems, and not connected across all functions of the airline (from planning to operations control). What was needed to make these contributions effective was a scheduling environment with a systematic interaction between the human, standardized databases across all functions of the airline, powerful desktop workstations for decision support, a standardized interactive graphical user interface for schedule editing, and the operations research techniques for optimization. This paper reports on the application of the integration of computer science and operations research in a decision support system for airline schedule planning. The application integrates a graphical user interface and the database with the schedule optimization algorithms.     

Employment Protection and Temporary Work Agencies

Employers who use temporary agency staff in contrast to regular staff are not affected by employment protection regulations when terminating a job. Therefore, services provided by temporary work agencies may be seen as a substitute for regular employment. In this paper, we analyse the effects of employment protection on the size of the temporary work agency sector in a model of equilibrium unemployment. We find that higher firing costs may even reduce temporary work agency employment if agencies themselves are subject to employment protection, a consideration that distinguishes our results from those for fixed‐term employment arrangements.     

Hospital and medical staff strategic planning: developing an integrated approach

The physician as the principal customer of the hospital is a relatively new concept, indicative of the shift to a more complete market orientation in strategic planning. Although medical staff and medical community dynamics receive increasing attention in strategic planning, much more sophistication is now needed to involve physicians constructively in strategic planning for the hospital and medical staff. While full consonance of physician and hospital plans may be achievable only in a completely integrated delivery system, there is considerable room for improvement in current organizational models.     

An optimal online algorithm for single machine scheduling to minimize total general completion time

We study the online problem of single machine scheduling to minimize total general completion time. General completion time is defined as C^a_j=(C_j)^aC^{\alpha}_{j}=(C_{j})^{\alpha}, where C _j denotes the completion time of job J _j and α≥1 is a constant integer. Total general completion time characterizes the feather in service that when a customer is served later in time, his dissatisfaction increases in a manner of power function. The objective function ∑(C _j ) ^α can also be viewed as a total weighted completion time, but the “weight” is no longer a constant number. Our purpose to minimize customers’ total dissatisfaction. The problem is online in the sense that all jobs arrive over time. Each job’s processing time becomes known at its arrival time. Preemption is not allowed. For this online problem, we show that a lower bound on competitive ratio is 2 ^α and prove that D-SPT (delayed shortest processing time) algorithm is optimal with a competitive ratio 2 ^α .     

Managerial prerogatives,employee expectations,and property rights in job security: Institutionalizing the “new equity”

Changes in the structure and provisions of the employment relationship create substantial challenges for the management community. The employer-manager's traditional prerogatives to terminate at will are being eroded in response to changing socioeconomic values that recognize the emergence of an employee's reasonable expectations of job security. The United States lags far behind the international community in protecting these expectations. The authors survey the erosion of the employment-at-will doctrine, and review the concepts of corporate due process and property rights relating to employment. To ensure the institutionalization of this new equity, the authors call on the management community to take the initiative in crafting progressive legislation that strikes a sensible balance between managerial prerogatives and employee expectations of job security.     

Online tradeoff scheduling on a single machine to minimize makespan and maximum lateness

In this paper, we consider the following single machine online tradeoff scheduling problem. A set of n independent jobs arrive online over time. Each job \(J_{j}\) has a release date \(r_{j}\), a processing time \(p_{j}\) and a delivery time \(q_{j}\). The characteristics of a job are unknown until it arrives. The goal is to find a schedule that minimizes the makespan \(C_{\max } = \max _{1 \le j \le n} C_{j}\) and the maximum lateness \(L_{\max } = \max _{1 \le j \le n} L_{j}\), where \(L_{j} = C_{j} + q_{j}\). For the problem, we present a nondominated \(( \rho , 1 + \displaystyle \frac{1}{\rho } )\)-competitive online algorithm for each \(\rho \) with \( 1 \le \rho \le \displaystyle \frac{\sqrt{5} + 1}{2}\).     

Mission impossible? Effects of crisis,leader and follower strain on health-oriented leadership

Previous studies underline positive effects of health-oriented leadership for follower well-being. However, it is not clear whether and to what extent situational and personal factors influence health-oriented leadership behavior towards employees (i.e., staff care). We examine the effect of crises and the moderating role of strain for the relationship between strain and staff care in two studies. The first study investigated main and interactive effects of crisis and leader strain on staff care in a cross-sectional survey (N = 201). To test for causality, we complemented our findings with an experimental vignette study (N = 169) and extended our findings with regard to the influence of follower strain. As expected, results of both studies showed negative effects of crisis and leader strain on staff care. Furthermore, crisis effects on staff care were contingent on both leader strain (Study 1 and 2) and follower strain (Study 2): While leader strain strengthened the negative relationships between crisis and staff care, follower strain served as a buffer. These findings support the assumption that staff care is at risk in crises particularly when leaders are strained. However, it is a positive finding that staff care is still feasible on a moderate and relevant level and that leaders respond to follower strain with additional efforts regarding staff care even in crises. The study contributes to the clarification and better understanding of situational contingencies of leadership behavior.     

A Fractional Dickey–Fuller Test for Unit Roots

This paper presents a new test for fractionally integrated (FI) processes. In particular, we propose a testing procedure in the time domain that extends the well–known Dickey–Fuller approach, originally designed for the I(1) versus I(0) case, to the more general setup of FI(d₀) versus FI(d₁), with d₁<d₀. When d₀=1, the proposed test statistics are based on the OLS estimator, or its t–ratio, of the coefficient on Δ^d1y_t−1 in a regression of Δy_t on Δ^d1y_t−1 and, possibly, some lags of Δy_t. When d₁ is not taken to be known a priori, a pre–estimation of d₁ is needed to implement the test. We show that the choice of any T^1/2–consistent estimator of d₁∈[0 ,1) suffices to make the test feasible, while achieving asymptotic normality. Monte–Carlo simulations support the analytical results derived in the paper and show that proposed tests fare very well, both in terms of power and size, when compared with others available in the literature. The paper ends with two empirical applications.     

Trivial Two-Stage Group Testing with High Error Rates

Given a population of cardinality q ^r that contains a positive subset P of cardinality p, we give a trivial two-stage method that has first stage pools each of which contains q ^{r – 2} objects. We assume that errors occur in the first stage. We give an algorithm that uses the results of first stage to generate a set CP of candidate positives with |CP| (r + 1)q. We give the expected value of |CPP|. At most (r + 1)q trivial second stage tests are needed to identify all the positives in CP. We assume that the second stage tests are error free.