In this paper, we propose a novel bee colony optimization approach to the nurse rostering problem. The bee colony optimization algorithm is motivated by the foraging habits of honey bees. In iterations, artificial bees collectively improve their solutions. The developed algorithm alternates constructive and local search phases. In the constructive phase, unscheduled shifts are assigned to available nurses, while the aim of local search phase is to improve the quality of the solution. The algorithm incorporates a novel intelligent discarding of portions of large neighborhoods for which it is predicted that they will not lead to the improvement of the objective function. Performance of the algorithm was evaluated on real-world data from hospitals in Belgium. The results show that the bee colony optimization is able to efficiently find solutions that are competitive compared to the solutions produced by other algorithms reported in the literature.

An important challenge within hyper-heuristic research is to design search methodologies that work well, not only across different instances of the same problem, but also across different problem domains. This article conducts an empirical study involving three different domains in combinatorial optimisation: bin packing, permutation flow shop and personnel scheduling. Using a common software interface (HyFlex), the same algorithms (high-level strategies or hyper-heuristics) can be readily run on all of them. The study is intended as a proof of concept of the proposed interface and domain modules, as a benchmark for testing the generalisation abilities of heuristic search algorithms. Several algorithms and variants from the literature were implemented and tested. From them, the implementation of iterated local search produced the best overall performance. Interestingly, this is one of the most conceptually simple competing algorithms, its advantage as a robust algorithm is probably due to two factors: (i) the simple yet powerful exploration/exploitation balance achieved by systematically combining a perturbation followed by local search; and (ii) its parameter-less nature. We believe that the challenge is still open for the design of robust algorithms that can learn and adapt to the available low-level heuristics, and thus select and apply them accordingly.

This paper considers a complex real world job shop rescheduling problem, in which jobs with different levels of urgency arrive every day in the shop floor and they need to be integrated in the existent schedule. A fuzzy scheduling system is responsible for inserting idle times on machines in order to produce initial robust schedules; and a rescheduling system which uses match-up approaches accommodates the newly arriving jobs. The main goal is to investigate the performance of this combined system when the arriving jobs are either rush orders or regular ones. Our results and statistical analysis show that a robust initial schedule combined with match-up rescheduling lead to higher quality and more reliable schedules even when jobs with different urgency levels arrive in a dynamic and uncertain shop floor.

Hyper-heuristics or ldquoheuristics to chose heuristicsrdquo are an emergent search methodology that seeks to automate the process of selecting or combining simpler heuristics in order to solve hard computational search problems. The distinguishing feature of hyper-heuristics, as compared to other heuristic search algorithms, is that they operate on a search space of heuristics rather than directly on the search space of solutions to the underlying problem. Therefore, a detailed understanding of the properties of these heuristic search spaces is of utmost importance for understanding the behaviour and improving the design of hyper-heuristic methods. Heuristics search spaces can be studied using the metaphor of fitness landscapes. This paper formalises the notion of hyper-heuristic landscapes and performs a landscape analysis of the heuristic search space induced by a dispatching-rule-based hyper-heuristic for production scheduling. The studied hyper-heuristic spaces are found to be ldquoeasyrdquo to search. They also exhibit some special features such as positional bias and neutrality. It is argued that search methods that exploit these features may enhance the performance of hyper-heuristics.

Radiation is often used in prostate cancer treatments. Radiotherapy treatment planning is a complex decision making process. In order to make a patient well, the oncologist has to make a trade-off between the benefit of radiation i.e. delivering a high enough dose to fight the cancer cells, and risk that refers to the side effects of the treatment. In this research, a case based reasoning system is developed for dose planning in prostate cancer treatment. A case similar to the new patient is retrieved. An adaptation of the suggested plan is performed taking into account trade-offs made in the past to determine the extent to which the maximum dose limits of the new patient (case) can be violated. The performance of the proposed method is validated on the real data sets obtained from the City Hospital Nottingham, University Hospital, NHS Trust, UK.

This paper presents a general numerical method to evaluate the download times in a P2P file sharing application with linear time and memory requirements with respect to the number of different files shared in the system. As this number typically exceeds several million and as the dependencies between file download times grow exponentially with the number of files, this method is useful to study realistic size systems. We apply the method on a system of 20000 files using parameters observed on a real network. The resulting performance is discussed. We show how the method may be extended to take into account initial waiting times before download and present the resulting performance.

In recent years, hyper-heuristics have emerged as a new search methodology that is motivated by the goal of increasing the level of generality of meta-heuristics. In this paper, we aim at investigating the role of cooperative decision making in the selection process of low level heuristics. We propose a novel cooperative distributed hyper-heuristic framework. The cooperative distributed hyper-heuristic framework is an agent-based system composed of a Hyper-Heuristic Agent (HHA) and a number of Low Level Heuristic Agents (LLHA). The HHA is in charge of the selection of the low level heuristic to apply at a decision point in the search process. The LLHAs search synchronously through the same solution space, starting from the same solution and using different low level heuristics. We conducted several experiments, using the permutation flow shop benchmark instances, to investigate the performance of the developed cooperative distributed hyper-heuristic approaches.

Hyper-heuristics or “heuristics that coordinate heuristics” are fastly becoming popular for solving combinatorial optimisation problems. These methods do not search directly the solution space; they do it indirectly through the exploration of the space of heuristics and/or their combinations. This space is named the associated space. The task of finding the best element in the associated space is referred to as the associated problem. This paper presents a formal definition of the associated problem, and investigates several of its properties. An empirical study of the associated problem is performed using a production scheduling problem as experimental environment. Obtained results allow us to partly explain what are the advantages of hyper-heuristic solution representations over other traditional ones, and, to give recommendations on hyper heuristic design.

This paper presents a new routing strategy, that selects the best network paths in an overlay network, in order to minimize the distortion perceived by the end user. We first propose a model that reports the video distortion as a function of the encoding rate, and the loss process parameters (the packet loss ratio, and the average burst length of errors). We then derive a method to compute an accurate estimation of the end-to-end characteristics of a given path in the network topology, as experienced by the media stream. It allows for reducing a set of streaming paths between the server and the client, to a simple virtual link with equivalent end-to-end parameters. Finally, an algorithm is proposed, that finds the best streaming paths in the overlay network, in terms of media distortion. Our algorithm therefore takes into account not only the conventional network parameters (e. g. end-to-end available bandwidth), but also other application specific metrics (e. g. video distortion measure and loss process). Interestingly, it is shown that the best route in terms of video distortion, does not necessarily use the highest bandwidth links, but carefully trades off channel reliability and bandwidth.

This paper describes a new model for robust predictive/reactive scheduling of steel continuous casting based on the use of multi-agents, tabu search and heuristic approaches. A continuous caster agent generates a predictive production schedule taking into account manufacturing requirements and local constraints using tabu search. The predictive schedule is modifies so as to minimize deviation between the performance measure values of the realized and predictive schedules in order to react to real-time events. We propose several schedule-repair and complete reschedule strategies to handle the real-time events, evaluate and compare their performance. The decision as to whether to locally repair the schedule or reschedule from scratch (complete reschedule) is based on three measures: robustness, utility and stability. Utility measures the change in schedule objective following schedule revision. Stability measures the deviation from the original schedule caused by schedule revision to quantify the undesirability of making large changes to the initial predictive schedule unless absolutely necessary. Robustness combines the utility and stability measures. In order to investigate the performance of these measures and strategies, simulation experiments were carried out and results are reported.

Users of hospital personnel planning software cope with the complex task of translating their needs into several constraints of a very different nature and with differing cost parameters. We present a multi criteria evolutionary approach, which overcomes some of the practical difficulties that personnel schedulers in hospitals often face.

When applying evolutionary algorithms to difficult real-world problems, the fitness function routinely needs evaluating for a very high number of intermediary cases. The paper is concerned with real-world nurse rostering problems with highly constrained resources. We consider a particular approach, which allows for a quick evaluation and is general enough to deal with other kinds of resource planning problems with time-related constraints. The model developed for this approach handles the constraints in a modular way and the addition of new constraints is relatively straightforward. Simple constraints (such as those affecting the personal wishes of employees) and global constraints (such as balancing the workload among people) can be formulated easily using this approach. Our approach can also handle very complex time-related constraints as well as conditions that are related to previously planned work. Moreover, it provides clear feedback about violation of constraints. The approach has been implemented successfully in a nurse rostering program entitled "Plane" which is used in hospitals all over Belgium. It can tackle a high number of specific and modifiable constraints of a very different nature. The benefits from this approach (in terms of software requirements) are small memory use and a computationally simple, single evaluation function allowing for the simultaneous rostering of several hospital wards at the same time.