Search

The nurse-to-patient assignment is one of the main decisions in planning Home Care (HC) services under continuity of care. In the literature, this problem has been tackled with several approaches to take demand variability into account. However, patient’s demands at different time periods have been always assumed as independent, while they are highly correlated in practice. In this work, we propose a robust assignment model that includes the time-dependency of the demands in the HC nurse-to-patient assignment problem, based on the implementor-adversarial framework. Results from a relevant test case show the appropriateness of the approach and the capability to contain costs while respecting the continuity of care constraints.

We study the shift scheduling problem in a multi-shift, flexible call center. Differently from previous approaches, the staffing levels ensuring the desired quality of service are considered uncertain, leading to a two-stage robust integer program with right-hand-side uncertainty. We show that, in our setting, modeling the correlation of the demands in consecutive time slots is easier than in other staffing approaches. The complexity issues of a Benders type reformulation are investigated and a branch-and-cut algorithm is devised. The approach can efficiently solve real-world problems from an Italian call center and effectively support managers decisions. In fact, we show that robust shifts have very similar costs to those evaluated by the traditional (deterministic) method while ensuring a higher level of protection against uncertainty.

The Closest String Problem (CSP) calls for finding an n-string that minimizes its maximum distance from m given n-strings. Integer linear programming (ILP) proved to be able to solve large CSPs under the Hamming distance, whereas for the Levenshtein distance, preferred in computational biology, no ILP formulation has so far be investigated. Recent research has however demonstrated that another metric, rank distance, can provide interesting results with genomic sequences. Moreover, CSP under rank distance can easily be modeled via ILP: optimal solutions can then be certified, or information on approximation obtained via dual gap. In this work we test this ILP formulation on random and biological data. Our experiments, conducted on strings with up to 600 nucleotides, show that the approach outperforms literature heuristics. We also enforce the formulation by cover inequalities. Interestingly, due to the special structure of the rank distance between two strings, cover separation can be done in polynomial time.

We investigate polyhedral properties of the following scheduling problem: given two sets of unit, indivisible jobs and revenue functions of the jobs completion times, find a one-machine schedule maximizing the total revenue under the constraint that the schedule of each job set respects a prescribed chain-like precedence relation. A solution to this problem is an order preserving assignment of the jobs to a set of time-slots. We study the convex hull of the feasible assignments and provide families of facet-defining inequalities in two cases: (i) each job must be assigned to a time-slot and (ii) a job does not need to be assigned to any time-slot. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011 © 2011 Wiley Periodicals, Inc.