Fair optimization of fortnightly physician schedules with flexible shifts

This research addresses a shift scheduling problem in which physicians are assigned to demand periods. We develop a reduced set covering approach that requires shift templates to be generated for a single day and compare it to an implicit modeling technique where shift-building rules are implemented as constraints. Both techniques allow full flexibility in terms of different shift starting times and lengths as well as break placements. The objective is to minimize the paid out hours under the restrictions given by the labor agreement. Furthermore, we integrate physician preferences and fairness aspects into the scheduling model. Computational results show the efficiency of the reduced set covering formulation in comparison to the implicit modeling approach.     

Facility placement with sub-aisle design in an existing layout

In this paper, we consider the integration of facility placement in an existing layout and the configuration of one or two connecting sub-aisles. This is relevant, for example, when placing a new machine/department on a shop floor with existing machines/departments and an existing aisle structure. Our work is motivated by the work of Savas et al. [Savas, S., Batta, R., Nagi, R., 2002. Finite-size facility placement in the presence of barriers to rectilinear travel. Operations Research 50 (6), 1018–1031], that considered the optimal planar placement of a finite-size facility in the presence of existing facilities. Our work differs from theirs in that we consider material handling to be restricted to the aisle structure. We do not allow the newly placed facility to overlap with existing facilities or with the aisle structure. Facilities are rectangular and travel is limited to new or existing aisles. We show that there are a finite number of candidate placements for the new facility. Algorithms are developed to find the optimal placement and the corresponding configurations for the sub-aisles. Complexity of the solution method is analyzed. Also, a numerical example is provided to explore the impact of the number of sub-aisles added.     

A note on the efficiency and fairness of decentralized matching

This note shows by means of simulation experiments that although two-sided matching markets can always converge to a stable outcome via a decentralized process of matching and rematching, the most likely outcome need not be the median matching or a minimum-choice-count matching, whether or not the two coincide.     

Modelling and solving optimal placement problems in wireless sensor networks

In this work, the optimal sensor displacement problem in wireless sensor networks is addressed. It is assumed that a network, consisting of independent, collaborative and mobile nodes, is available. Starting from an initial configuration, the aim is to define a specific sensors displacement, which allows the network to achieve high performance, in terms of energy consumption and travelled distance. To mathematically represent the problem under study, different innovative optimization models are proposed and defined, by taking into account different performance objectives. An extensive computational phase is carried out in order to assess the behaviour of the developed models in terms of solution quality and computational effort. A comparison with distributed approaches is also given, by considering different scenarios.     

Inequality measures and equitable locations

While making location decisions, the distribution of distances (outcomes) among the service recipients (clients) is an important issue. In order to comply with the minimization of distances as well as with an equal consideration of the clients, mean-equity approaches are commonly used. They quantify the problem in a lucid form of two criteria: the mean outcome representing the overall efficiency and a scalar measure of inequality of outcomes to represent the equity (fairness) aspects. The mean-equity model is appealing to decision makers and allows a simple trade-off analysis. On the other hand, for typical dispersion indices used as inequality measures, the mean-equity approach may lead to inferior conclusions with respect to the distances minimization. Some inequality measures, however, can be combined with the mean itself into optimization criteria that remain in harmony with both inequality minimization and minimization of distances. In this paper we introduce general conditions for inequality measures sufficient to provide such an equitable consistency. We verify the conditions for the basic inequality measures thus showing how they can be used in location models not leading to inferior distributions of distances. The research was supported by the Ministry of Science and Information Society Technologies under grant 3T11C 005 27 “Models and Algorithms for Efficient and Fair Resource Allocation in Complex Systems”.     

Partial pole placement with time delay in structures using the receptance and the system matrices

Datta et al. solved the partial pole placement problem for the symmetric definite quadratic eigenvalue problem where part of the spectrum is relocated to predetermined locations and the rest of the spectrum remains unchanged. In this paper, the problem is solved by a hybrid combination of this result and the method of receptances. This allows for the partial assignment of desired poles with no spillover when there is time delay between the measured or estimated state and actuation of the control.     

On the rod placement theorem of Rybko and Shlosman

Given n−1 points on the real line and a set of n rods of strictly positive lengths , we get to choose an n-th point x_n anywhere on the real line and to assign the rods to the points according to an arbitrary permutation π. The rod is thought of as the workload brought in by a customer arriving at time x_k into a first in -first out queue which starts empty at − ∞. If any x_i equals x_j for i < j, service is provided to the rod assigned to x_i before the rod assigned to x_j. Let denote the set of departure times of the customers (rods). Let denote the number of choices for the location of x_n for which . Rybko and Shlosman proved that

Geometric quadrisection in linear time, with application to VLSI placement

We consider the following problem: given a set of points in the plane, each with a weight, and capacities of the four quadrants, assign each point to one of the quadrants such that the total weight of points assigned to a quadrant does not exceed its capacity, and the total distance is minimized.

This problem is most important in placement of VLSI circuits and is likely to have other applications. It is NP-hard, but the fractional relaxation always has an optimal solution which is “almost” integral. Hence for large instances, it suffices to solve the fractional relaxation. The main result of this paper is a linear-time algorithm for this relaxation. It is based on a structure theorem describing optimal solutions by so-called “American maps” and makes sophisticated use of binary search techniques and weighted median computations.

This algorithm is a main subroutine of a VLSI placement tool that is used for the design of many of the most complex chips.     

A polygonal upper bound for the efficient set for single-facility location problems with mixed norms

Summary In this paper it is shown that, in a multiobjective single-facility location problem in which distances are measured by arbitrary mixed norms, the set of efficient points is a subset of apolygonal hull of the demand points. Using a certain type of projection, this hull can be easily built. We apply this to a certain family of norms, containing the set ofl _p -norms, and, in a particular case, classical results are obtained.     

On compact and efficient routing in certain graph classes

In this paper we refine the notion of tree-decomposition by introducing acyclic (R,D)-clustering, where clusters are subsets of vertices of a graph and R and D are the maximum radius and the maximum diameter of these subsets. We design a routing scheme for graphs admitting induced acyclic (R,D)-clustering where the induced radius and the induced diameter of each cluster are at most 2. We show that, by constructing a family of special spanning trees, one can achieve a routing scheme of deviation Δ?2R with labels of size bits per vertex and O(1) routing protocol for these graphs. We investigate also some special graph classes admitting induced acyclic (R,D)-clustering with induced radius and diameter less than or equal to 2, namely, chordal bipartite, homogeneously orderable, and interval graphs. We achieve the deviation Δ=1 for interval graphs and Δ=2 for chordal bipartite and homogeneously orderable graphs.     

Recursive and explicit rules: How can we build student algebraic understanding?

Differing perspectives have been offered about student use of recursive and explicit rules. These include: (a) promoting the use of explicit rules over the use of recursive rules, and (b) encouraging student use of both recursive and explicit rules. This study sought to explore students’ use of recursive and explicit rules by examining the reasoning of 25 sixth-grade students, including a focus on four target students, as they approached tasks in which they were required to develop generalizations while using computer spreadsheets as an instructional tool. The results demonstrate the difficulty that students had moving from the successful use of recursive rules toward explicit rules. In particular, two students abandoned general reasoning, instead focusing on particular values in an attempt to construct explicit rules. It is recommended that students be encouraged to connect recursive and explicit rules as a potential means for constructing successful generalizations.     

Optimizing source and receiver placement in multistatic sonar networks to monitor fixed targets

Multistatic sonar networks consisting of non-collocated sources and receivers are a promising development in sonar systems, but they present distinct mathematical challenges compared to the monostatic case in which each source is collocated with a receiver. This paper is the first to consider the optimal placement of both sources and receivers to monitor a given set of target locations. Prior publications have only considered optimal placement of one type of sensor, given a fixed placement of the other type. We first develop two integer linear programs capable of optimally placing both sources and receivers within a discrete set of locations. Although these models are capable of placing both sources and receivers to any degree of optimality desired by the user, their computation times may be unacceptably long for some applications. To address this issue, we then develop a two-step heuristic process, Adapt-LOC, that quickly selects positions for both sources and receivers, but with no guarantee of optimality. Based on this, we also create an iterative approach, Iter-LOC, which leads to a locally optimal placement of both sources and receivers, at the cost of larger computation times relative to Adapt-LOC. Finally, we perform computational experiments demonstrating that the newly developed algorithms constitute a powerful portfolio of tools, enabling the user to slect an appropriate level of solution quality, given the available time to perform computations. Our experiments include three real-world case studies.     

Boundary labeling: Models and efficient algorithms for rectangular maps

We introduce boundary labeling, a new model for labeling point sites with large labels. According to the boundary-labeling model, labels are placed around an axis-parallel rectangle that contains the point sites, each label is connected to its corresponding site through a polygonal line called leader, and no two leaders intersect. Although boundary labeling is commonly used, e.g., for technical drawings and illustrations in medical atlases, this problem has not yet been studied in the literature. The problem is interesting in that it is a mixture of a label-placement and a graph-drawing problem.

In this paper we investigate several variants of the boundary-labeling problem. We consider labels of identical or different size, straight-line or rectilinear leaders, fixed or sliding ports for attaching leaders to sites and attaching labels to one, two or all four sides of the bounding rectangle. For any variant of the boundary labeling model, we aim at highly esthetical placements of labels and leaders. We present simple and efficient algorithms that minimize the total leader length or, in the case of rectilinear leaders, the total number of bends.     

On the student evaluation of university courses and faculty members’ teaching performance

Trying to determine higher education quality, one gets quickly to one of its significant dimensions, namely the quality of faculty members’ teaching. The latter and, overall, the quality of any university course should be certainly evaluated by their recipients, namely students. In this paper we develop a statistical framework based on Statistical Quality Control mainly, which can be used in order to exploit student evaluations as much as possible. More specifically we present two directions of data monitoring and analysis; the one uses control charts and the other hypotheses testing. The results that can be raised through both directions are crucial for any decision maker.     

Effectively coaching middle school teachers: A case for teacher and student learning

In this paper we report findings from a two-year, large-scale research project that describes the work of middle school mathematics specialists (also referred to as mathematics coaches or instructional coaches) who served in 10 school districts. We use mixed methods to describe how mathematics specialists spent their time supporting teachers and how these supports contributed to meaningful changes that teachers made in their instructional practices. We also report results that correlate student achievement scores with whether or not teachers were highly engaged with the mathematics specialists. We coordinate these quantitative results with findings from several case studies to illustrate the qualitatively different ways that mathematics specialists supported teachers’ ongoing work with their students. We also account for why some teachers participated more fully than others. Importantly, because mathematics specialists’ work was situated in different school settings with different demands, resources and administrative supports, these constraints and affordances contributed in part to how they could effectively support teachers’ work with their students.     

An algorithm for computing the nucleolus of disjunctive non-negative additive games with an acyclic permission structure

A cooperative game with a permission structure describes a situation in which players in a cooperative TU-game are hierarchically ordered in the sense that there are players that need permission from other players before they are allowed to cooperate. In this paper we consider non-negative additive games with an acyclic permission structure. For such a game we provide a polynomial time algorithm for computing the nucleolus of the induced restricted game. The algorithm is applied to a market situation where sellers can sell objects to buyers through a directed network of intermediaries.     

Combining variable neighborhood search and estimation of distribution algorithms in the protein side chain placement problem

The aim of this work is to introduce several proposals for combining two metaheuristics: variable neighborhood search (VNS) and estimation of distribution algorithms (EDAs). Although each of these metaheuristics has been previously hybridized in several ways, this paper constitutes the first attempt to combine both optimization methods. The different ways of combining VNS and EDAs will be classified into three groups. In the first group, we will consider combinations where the philosophy underlying VNS is embedded in EDAs. Considering different neighborhood spaces (points, populations or probability distributions), we will obtain instantiations for the approaches in this group. The second group of algorithms is obtained when probabilistic models (or any other machine learning paradigm) are used in order to exploit the good and bad shakes of the randomly generated solutions in a reduced variable neighborhood search. The last group of algorithms contains the results of alternating VNS and EDAs. An application of the first approach is presented in the protein side chain placement problem. The results obtained show the superiority of the hybrid algorithm in comparison with EDAs and VNS.     

Finding the efficiency score and RTS characteristic of DMUs by means of identifying the efficient frontier in DEA

Data envelopment analysis (DEA) is basically a linear programming based technique used for measuring the relative performance of organizational units, referred to as decision-making units (DMUs), where the presence of multiple inputs and outputs makes comparisons difficult. The ability of identifying frontier DMUs prior to the DEA calculation is of extreme importance to an effective and efficient DEA computation. In this paper, a method for identifying the efficient frontier is introduced. Then, the efficiency score and returns to scale (RTS) characteristic of DMUs will be produced by means of the equation of efficient frontier.     

A technique to choose the most efficient method between secant method and some variants

A few variants of the secant method for solving nonlinear equations are analyzed and studied. In order to compute the local order of convergence of these iterative methods a development of the inverse operator of the first order divided differences of a function of several variables in two points is presented using a direct symbolic computation. The computational efficiency and the approximated computational order of convergence are introduced and computed choosing the most efficient method among the presented ones. Furthermore, we give a technique in order to estimate the computational cost of any iterative method, and this measure allows us to choose the most efficient among them.