Search

Patient scheduling is a difficult task involving stochastic factors, such as the unknown arrival times of patients. Similarly, the scheduling of radiotherapy for cancer treatments needs to handle patients with different urgency levels when allocating resources. High-priority patients may arrive at any time, and there must be resources available to accommodate them. A common solution is to reserve a flat percentage of treatment capacity for emergency patients. However, this solution can result in overdue treatments for urgent patients, a failure to fully exploit treatment capacity, and delayed treatments for low-priority patients. This problem is especially severe in large and crowded hospitals. In this paper, we propose a prediction-based approach for online dynamic radiotherapy scheduling that dynamically adapts the present scheduling decision based on each incoming patient and the current allocation of resources. Our approach is based on a regression model trained to recognize the links between patients' arrival patterns and their ideal waiting time in optimal off-line solutions when all future arrivals are known in advance. When our prediction-based approach is compared with flat-reservation policies, it does a better job of preventing overdue treatments for emergency patients and also maintains comparable waiting times for the other patients. We also demonstrate how our proposed approach supports explainability and interpretability in scheduling decisions using Shapley additive explanation values. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: Mitacs Accélération IT26995 and Canada Research Chair in Analytics and Logistics in Healthcare (HANALOG). Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information (https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2023.1289) as well as from the IJOC GitHub software repository (https://github.com/INFORMSJoC/2021.0342) at (http://dx.doi.org/10.5281/zenodo.7579533). [ABSTRACT FROM AUTHOR]

The Radiotherapy Scheduling Problem (RTSP) focuses on optimizing the planning of radiotherapy treatment sessions for cancer patients. In this paper, we propose a two-phase approach for the RTSP. In the first phase, radiotherapy sessions are assigned to specific linear accelerators (linacs) and days. The second phase then decides the sequence of patients on each day/linac and the specific appointment times. For the first phase, an Integer Linear Programming (IP) model is proposed and solved using CPLEX. For the second phase, a Mixed Integer Linear Programming (MIP) and a Constraint Programming (CP) model are proposed. The test data is generated based on real data from CHUM, a large cancer center in Montréal, Canada, with an average of 3,500 new patients and 40,000 radiotherapy treatments per year. The results show that in the second phase, CP is better at finding good solutions quickly while MIP is better at closing optimality gaps with more run time. Lastly, a simulation is conducted to evaluate the impact of different scheduling strategies on the outcome of the scheduling. Preliminary results show that batch scheduling reduces patients' waiting time and overdue time. [ABSTRACT FROM AUTHOR]

This paper proposes a local search algorithm for a specific combinatorial optimisation problem in graph theory: the Hamiltonian completion problem (HCP) on undirected graphs. In this problem, the objective is to add as few edges as possible to a given undirected graph in order to obtain a Hamiltonian graph. This problem has mainly been studied in the context of various specific kinds of undirected graphs (e.g. trees, unicyclic graphs and series-parallel graphs). The proposed algorithm, however, concentrates on solving HCP for general undirected graphs. It can be considered to belong to the category of matheuristics, because it integrates an exact linear time solution for trees into a local search algorithm for general graphs. This integration makes use of the close relation between HCP and the minimum path partition problem, which makes the algorithm equally useful for solving the latter problem. Furthermore, a benchmark set of problem instances is constructed for demonstrating the quality of the proposed algorithm. A comparison with state-of-the-art solvers indicates that the proposed algorithm is able to achieve high-quality results. [ABSTRACT FROM AUTHOR]

In this paper, we introduce a new variant of the travelling salesman problem, namely the intermittent travelling salesman problem (ITSP), which is inspired by real‐world drilling/texturing applications. In this problem, each vertex can be visited more than once and there is a temperature constraint enforcing a time lapse between two consecutive visits. A branch‐and‐bound approach is proposed to solve small instances to optimality. We furthermore develop four variable neighbourhood search metaheuristics which produce high‐quality solutions for large instances. An instance library is built and made publicly available. [ABSTRACT FROM AUTHOR]

When developing optimisation algorithms, the focus often lies on obtaining an algorithm that is able to outperform other existing algorithms for some performance measure. It is not common practice to question the reasons for possible performance differences observed. These types of questions relate to evaluating the impact of the various heuristic parameters and often remain unanswered. In this paper, the focus is on gaining insight in the behaviour of a heuristic algorithm by investigating how the various elements operating within the algorithm correlate with performance, obtaining indications of which combinations work well and which do not, and how all these effects are influenced by the specific problem instance the algorithm is solving. We consider two approaches for analysing algorithm parameters and components—functional analysis of variance and multilevel regression analysis—and study the benefits of using both approaches jointly. We present the results of a combined methodology that is able to provide more insights than when the two approaches are used separately. The illustrative case studies in this paper analyse a large neighbourhood search algorithm applied to the vehicle routing problem with time windows and an iterated local search algorithm for the unrelated parallel machine scheduling problem with sequence-dependent setup times. [ABSTRACT FROM AUTHOR]

This paper reports on the Second International Nurse Rostering Competition (INRC-II). Its contributions are (1) a new problem formulation which, differently from INRC-I, is a multi-stage procedure, (2) a competition environment that, as in INRC-I, will continue to serve as a growing testbed for search approaches to the INRC-II problem, and (3) final results of the competition. We discuss also the competition environment, which is an infrastructure including problem and instance definitions, testbeds, validation/simulation tools and rules. The hardness of the competition instances has been evaluated through the behaviour of our own solvers, and confirmed by the solvers of the participants. Finally, we discuss general issues about both nurse rostering problems and optimisation competitions in general. [ABSTRACT FROM AUTHOR]

Good Laboratory Practice has been a part of non-clinical research for over 40 years. Optimization Research, despite having many papers discussing standards being published over the same period of time, has yet to embrace standards that underpin its research. In this paper we argue the need to adopt standards in optimization research. Building on previous papers, many of which have suggested that the optimization research community should adopt certain standards, we suggest a concrete set of recommendations that the community should adopt. We also discuss how the proposals in this paper could be progressed. [ABSTRACT FROM AUTHOR]

The 2020 edition of PATAT was to mark the silver anniversary of the PATAT conference series. The PATAT conference series has been running biennially, since 1995, when the very first conference was organised in Edinburgh. We are delighted to present you with a selection of peer reviewed papers from the submissions to the 13th International Conference on the Practice and Theory of Automated Timetabling (PATAT) in 2020 and 2021. [Extracted from the article]

Nurse rostering is a complex task of practical relevance. Over the last years, researchers have been able to solve increasingly larger and more complex problems. In this paper, we describe the full procedure of running the First International Nurse Rostering Competition. The aim of the competition was to develop further interest in the area and to stimulate new solution approaches by bringing together researchers from different areas. We describe the competition's spirit and its rules, the problem description and evaluation of solutions. We also explain the selection process and the final results. In addition, we give a brief description of the algorithmic approaches undertaken by the participants. Finally, we discuss the lessons learned from the competition and future activities to undertake. [ABSTRACT FROM AUTHOR]

In practice nurse rostering problems are often too complex to be expressed through available academic models. Such models are not rich enough to represent the variegated nature of real world scenarios, and therefore have no practical relevance. This article focuses on two particular modelling issues that require careful consideration in making academic nurse rostering approaches re-usable in a real world environment. First: introducing several complex problem characteristics, resulting in a rich, generic model. A detailed description is provided for researchers interested in using this new model. We also present a novel benchmark dataset based on this rich model. Second: the consideration of a consistent evaluation procedure that corresponds to realistic quality measurement. These contributions will enable faster implementation of academic nurse rostering achievements in real hospital environments. A suite of hyper-heuristics is presented. These are capable of solving these rich personnel rostering problems using the presented evaluation procedures. Their performance is compared to that of another meta-heuristic. [ABSTRACT FROM AUTHOR]

The best-fit heuristic is a simple and powerful tool for solving the two-dimensional orthogonal strip packing problem. It is the most efficient constructive heuristic on a wide range of rectangular strip packing benchmark problems. In this paper, the results of the original best-fit heuristic are further improved by adding new item orderings and item placement strategies, resulting in the three-way best-fit heuristic. By applying these steps, significantly better results are obtained in comparable computation time. Furthermore, some data structures are implemented, which increase the scalability of the heuristic for large problem instances and a slightly altered heuristic with an optimal [ABSTRACT FROM AUTHOR]

Motivation: Gene prioritization aims at identifying the most promising candidate genes among a large pool of candidates—so as to maximize the yield and biological relevance of further downstream validation experiments and functional studies. During the past few years, several gene prioritization tools have been defined, and some of them have been implemented and made available through freely available web tools. In this study, we aim at comparing the predictive performance of eight publicly available prioritization tools on novel data. We have performed an analysis in which 42 recently reported disease-gene associations from literature are used to benchmark these tools before the underlying databases are updated.Results: Cross-validation on retrospective data provides performance estimate likely to be overoptimistic because some of the data sources are contaminated with knowledge from disease-gene association. Our approach mimics a novel discovery more closely and thus provides more realistic performance estimates. There are, however, marked differences, and tools that rely on more advanced data integration schemes appear more powerful.Contact: yves.moreau@esat.kuleuven.beSupplementary information: Supplementary data are available at Bioinformatics online. [ABSTRACT FROM PUBLISHER]

Purpose – Mashups have been studied extensively in the literature; nevertheless, the large body of work in this area focuses on service/data level integration and leaves UI level integration, hence UI mashups, almost unexplored. The latter generates digital environments in which participating sources exist as individual entities; member applications and data sources share the same graphical space particularly in the form of widgets. However, the true integration can only be realized through enabling widgets to be responsive to the events happening in each other. The authors call such an integration "widget orchestration" and the resulting application "mashup by orchestration". This article aims to explore and address challenges regarding the realization of widget-based UI mashups and UI level integration, prominently in terms of widget orchestration, and to assess their suitability for building web-based personal environments. Design/methodology/approach – The authors provide a holistic view on mashups and a theoretical grounding for widget-based personal environments. The authors identify the following challenges: widget interoperability, end-user data mobility as a basis for manual widget orchestration, user behavior mining – for extracting behavioral patterns – as a basis for automated widget orchestration, and infrastructure. The authors introduce functional widget interfaces for application interoperability, exploit semantic web technologies for data interoperability, and realize end-user data mobility on top of this interoperability framework. The authors employ semantically enhanced workflow/process mining techniques, along with Petri nets as a formal ground, for user behavior mining. The authors outline a reference platform and architecture that is compliant with the authors' strategies, and extend W3C widget specification respectively – prominently with a communication channel – to foster standardization. The authors evaluate their solution approaches regarding interoperability and infrastructure through a qualitative comparison with respect to existing literature, and provide a computational evaluation of the behavior mining approach. The authors realize a prototype for a widget-based personal learning environment for foreign language learning to demonstrate the feasibility of their solution strategies. The prototype is also used as a basis for the end-user assessment of widget-based personal environments and widget orchestration. Findings – The evaluation results suggest that the interoperability framework, platform, and architecture have certain advantages over existing approaches, and the proposed behavior mining techniques are adequate for the extraction of behavioral patterns. User assessments show that widget-based UI mashups with orchestration (i.e. mashups by orchestration) are promising for the creation of personal environments as well as for an enhanced user experience. Originality/value – This article provides an extensive exploration of mashups by orchestration and their role in the creation of personal environments. Key challenges are described, along with novel solution strategies to meet them. [ABSTRACT FROM AUTHOR]

Timetabling and rostering research often starts from particular real world problems. The last two decennia have seen a large number of papers discussing cases, models and approaches. This large body of publications does not presently constitute a structured domain that provides guidelines for addressing particular problem instances, nor does it allow identifying gaps where new research is needed. In this paper, we instigate a structured model for timetabling and rostering. We present a basic structure for the integrated staff planning and rostering problem. The model can only result in a valid and efficient tool through the input of multiple disciplines. We give a first formal description for short term nurse rostering. Specific problems are positioned in this model. [ABSTRACT FROM AUTHOR]

In this paper, we investigate how the SemanticWeb can enhance web navigation and accessibility by following a hybrid approach of document-oriented and data-oriented considerations. Precisely, we propose a methodology for specifying, extracting, and presenting semantic data embedded in (X)HTML documents with RDFa in order to enable and improve ubiquitous web navigation and accessibility for end-users. In our context, embedded data does not only contain data type property annotations, but also object properties for interlinking, and embedded domain knowledge for enhanced content navigation through ontology reasoning. We provide a prototype implementation, called Semantic Web Component (SWC) and evaluate our methodology along a concrete scenario for mobile devices and with respect to precision, performance, network traffic, and usability. Evaluation results suggest that our approach decreases network traffic as well as the amount of information presented to a user without requiring significantly more processing time, and that it allows creating a satisfactory navigation experience. [ABSTRACT FROM AUTHOR]

In this paper, we investigate how the Semantic Web can enhance web navigation and accessibility by following a hybrid approach of document-oriented and data-oriented considerations. Precisely, we propose a methodology for specifying, extracting, and presenting semantic data embedded in (X)HTML documents with RDFa in order to enable and improve ubiquitous web navigation and accessibility for end-users. In our context, embedded data does not only contain data type property annotations, but also object properties for interlinking, and embedded domain knowledge for enhanced content navigation through ontology reasoning. We provide a prototype implementation, called Semantic Web Component (SWC) and evaluate our methodology along a concrete scenario for mobile devices and with respect to precision, performance, network traffic, and usability. Evaluation results suggest that our approach decreases network traffic as well as the amount of information presented to a user without requiring significantly more processing time, and that it allows creating a satisfactory navigation experience. [ABSTRACT FROM AUTHOR]

Finding the most promising genes among large lists of candidate genes has been defined as the gene prioritization problem. It is a recurrent problem in genetics in which genetic conditions are reported to be associated with chromosomal regions. In the last decade, several different computational approaches have been developed to tackle this challenging task. In this study, we review 19 computational solutions for human gene prioritization that are freely accessible as web tools and illustrate their differences. We summarize the various biological problems to which they have been successfully applied. Ultimately, we describe several research directions that could increase the quality and applicability of the tools. In addition we developed a website (http://www.esat.kuleuven.be/gpp) containing detailed information about these and other tools, which is regularly updated. This review and the associated website constitute together a guide to help users select a gene prioritization strategy that suits best their needs. [ABSTRACT FROM PUBLISHER]

In this paper, we will address privacy and trust issues that arise in more advanced software systems. Though a lot of information is currently available in electronic form, not all of it should widely be accessible to everybody. The involved parties need full control on how their data are used and who has access. If the system consists of autonomous software agents, this problem requires extra attention and new working principles. We illustrate this in the case of a communication platform for multimodal transport. The major aim of the communication platform is to enhance exchanging information and to ultimately improve organisation/collaboration within the transport sector. A better informed view of the transport sector will facilitate better considered decisions for users of the communication platform. The software system merits credibility by accurately modelling all the relevant real world interactions of potential users of the system. We opted for a connectivity solution in which software agents act as representatives of the parties involved. All agents can be equipped with human-like skills and qualities such as intelligence, autonomy, and the ability to cooperate, coordinate and negotiate. We demonstrate how cooperation between parties can be achieved while respecting their sensitivity concerning information. [ABSTRACT FROM AUTHOR]

Constructing timetables of work for personnel in healthcare institutions is known to be a highly constrained and difficult problem to solve. In this paper, we discuss a commercial system, together with the model it uses, for this rostering problem. We show that tabu search heuristics can be made effective, particularly for obtaining reasonably good solutions quickly for smaller rostering problems. We discuss the robustness issues, which arise in practice, for tabu search heuristics. This paper introduces a range of new memetic approaches for the problem, which use a steepest descent improvement heuristic within a genetic algorithm framework. We provide empirical evidence to demonstrate the best features of a memetic algorithm for the rostering problem, particularly the nature of an effective recombination operator, and show that these memetic approaches can handle initialisation parameters and a range of instances more robustly than tabu search algorithms, at the expense of longer solution times. Having presented tabu search and memetic approaches (both with benefits and drawbacks) we finally present an algorithm that is a hybrid of both approaches. This technique produces better solutions than either of the earlier approaches and it is relatively unaffected by initialisation and parameter changes, combining some of the best features of each approach to create a hybrid which is greater than the sum of its component algorithms. [ABSTRACT FROM AUTHOR]