Search

Patient unpunctuality significantly disrupts the operations of healthcare facilities, reduces provider productivity, and increases healthcare costs. To alleviate the negative impact of unpunctual patients, this study addresses the appointment scheduling (AS) in the simultaneous presence of unpunctual patients, multiple servers, and no-shows. To determine the appointment schedule, we propose a two-stage stochastic mixed-integer programming model to minimise the total cost incurred by patient waiting and clinic overtime. It becomes challenging for a standard solver to solve this model due to the dynamic patient-to-server assignment decisions that are proactively anticipated in the determination of appointment times. To deal with this problem, a stochastic approximation algorithm is proposed under unbiased gradient estimators. The effectiveness and efficiency of this algorithm are validated in extensive numerical experiments that compare it with Benders decomposition and a heuristic algorithm. Further, the features of the optimal appointment schedule are analysed: (i) the shape of the appointment intervals relies on the number of servers; (ii) the length of intervals is sensitive to no-shows; (iii) the initial block size is greatly affected by patient unpunctuality. Managerial insights are also provided for hospital managers to schedule unpunctual patients in practice. [ABSTRACT FROM AUTHOR]

We consider a conflict-free minimum latency data aggregation problem that occurs in different wireless networks. Given a network that is presented as an undirected graph with one selected vertex (a sink), the goal is to find a spanning aggregation tree rooted in the sink and to define a conflict-free aggregation minimum length schedule along the arcs of the tree directed to the sink. Herewith, at the same time slot, each element of the network can either send or receive at most one message. Only one message should be sent by each network element during the whole aggregation session, and the conflicts caused by signal interference should be excluded. This problem is NP-hard and remains NP-hard even in the case when the aggregation tree is given. Therefore, the development of efficient approximation algorithms is very important for this problem. In this paper, we present new heuristic algorithms based on genetic local search and variable neighbourhood search metaheuristics. We conducted an extensive simulation that demonstrates the superiority of our algorithms compared with the best of the previous approaches. [ABSTRACT FROM AUTHOR]

Fuzzy testing is the most effective method for vulnerability mining, which can deal with complex programmes better than other vulnerability mining techniques and has strong scalability. However, in the large-scale vulnerability analysis test, the fuzzy test input sample set faces the challenges of low quality, high repeatability and low availability etc. Therefore, this paper studies the input sample set and proposes heuristic genetic algorithm. By using 0–1 matrix, the genetic algorithm is improved with a consideration of practical problems and the execution path for sample set is selected and compressed through approximation algorithm, thus obtaining a smallest sample set and accelerating the efficiency of fuzzy test. Experimental results show that the proposed method is effective. [ABSTRACT FROM AUTHOR]

The problem we study in this paper arises from the washing step of hospital sterilisation services. Washers in the washing step are capable of handling more than one medical device set as long as their capacity is not exceeded. The medical device set sizes and arrival times to the sterilisation service may be different, but they all have the same washing duration. Thus, we model the washing step as a batch scheduling problem where medical device sets are treated as jobs with non-identical sizes and release dates, but equal processing times. The main findings we present in this paper are the following. First, we study two special cases for which polynomial algorithms are presented. We then develop a 2-approximation algorithm for the general problem. Finally, we develop a MILP model and compare it with another MILP model from the literature. Computational results show that our MILP model outperforms the model from the literature. [ABSTRACT FROM PUBLISHER]

In this paper, we present a meta-heuristic algorithm for the resource-constrained project scheduling problem with discounted cash flows. We assume fixed payments associated with the execution of project activities and develop a heuristic optimisation procedure to maximise the net present value of a project subject to the precedence and renewable resource constraints. We investigate the use of a bi-directional generation scheme and a recursive forward/backward improvement method from literature and embed them in a meta-heuristic scatter search framework. We generate a large dataset of project instances under a controlled design and report detailed computational results. The solutions and project instances can be downloaded from a website in order to facilitate comparison with future research attempts. [ABSTRACT FROM AUTHOR]

Today is an era where multiprocessor technology plays a major role in designs of modern computer architecture. While multiprocessor systems offer extra computing power, it also opens a new range of opportunities to improve fault-robustness. This paper focuses on a problem of achieving fault-tolerance using replications in real-time, multiprocessor systems. In the problem, multiple replicas, or copies, of a computing task are executed on distinct processors to resist potential processor failures and computing faults. Two greedy, approximation heuristics, named Worst Fit Increasing K-Replication and First Fit Increasing K-Replication, are studied to maximise the number of real-time tasks assigned on a system with identical processors, respecting to the tasks’ replicating and timely requirements. Worst case performance is analysed by using an approximation ratio between the algorithms and an optimal solution. We mathematically prove that the ratios of using both algorithms are infinitely close to 2. Simulations are performed on a large set of testing cases which can be used to bring to light the average performance of using the algorithms in practice. The results show that both heuristic algorithms provide simple but fast and effective solutions to solve the problem. Assigning real-time tasks to a multiprocessor system with replications. [ABSTRACT FROM PUBLISHER]

This work studies a scheduling problem where each job must be either accepted and scheduled to complete within its specified due window, or rejected altogether. Each job has a certain processing time and contributes a certain profit if accepted or penalty cost if rejected. There is a set of renewable resources, and no resource limit can be exceeded at any time. Each job requires a certain amount of each resource when processed, and the objective is to maximize total profit. A mixed-integer programming formulation and three approximation algorithms are presented: a priority rule heuristic, an algorithm based on the metaheuristic for randomized priority search and an evolutionary algorithm. Computational experiments comparing these four solution methods were performed on a set of generated benchmark problems covering a wide range of problem characteristics. The evolutionary algorithm outperformed the other methods in most cases, often significantly, and never significantly underperformed any method. [ABSTRACT FROM PUBLISHER]

A lot of heuristic algorithms, such as Evolutionary algorithms (EAs), are used to solve the maximum leaf spanning tree (MLST) problem which is non-deterministic polynomial time hard (NP-hard). However, the performance analysis of EAs on the MLST problem has seldom been studied theoretically. In this paper, we theoretically analyze the performance of the (1+1) EA on the MLST problem. We demonstrate that the (1+1) EA obtains-approximation ratio and 3-approximation ratio on this problem in expected polynomial runtimeO(nm2) andO(nm4), respectively, wherenis the number of nodes andmis the number of edges in a connected undirected graph. Furthermore, we reveal that the (1+1) EA can outperform the local search algorithms on two instances of the MLST problem. [ABSTRACT FROM AUTHOR]

The main focus of this article is to present a proposal to solve, viaUDUTfactorisation, the convergence and numerical stability problems that are related to the covariance matrix ill-conditioning of the recursive least squares (RLS) approach for online approximations of the algebraic Riccati equation (ARE) solution associated with the discrete linear quadratic regulator (DLQR) problem formulated in the actor–critic reinforcement learning and approximate dynamic programming context. The parameterisations of the Bellman equation, utility function and dynamic system as well as the algebra of Kronecker product assemble a framework for the solution of the DLQR problem. The condition number and the positivity parameter of the covariance matrix are associated with statistical metrics for evaluating the approximation performance of the ARE solution via RLS-based estimators. The performance of RLS approximators is also evaluated in terms of consistence and polarisation when associated with reinforcement learning methods. The used methodology contemplates realisations of online designs for DLQR controllers that is evaluated in a multivariable dynamic system model. [ABSTRACT FROM AUTHOR]

This article addresses the flow shop scheduling problem to minimize the sum of the completion times. On the basis of the properties in job sequencing, the triangular shortest processing time (TSPT) first and dynamic triangular shortest processing time first heuristics are designed to solve the static and dynamic versions of this problem, respectively. Moreover, an improvement scheme is provided for these heuristics to enhance the quality of the original solutions. For further numerical evaluation of the heuristics, two new lower bounds with performance guarantees are presented for the two versions of the problem. At the end of the article, a series of numerical experiments is conducted to demonstrate the effectiveness of the algorithms. [ABSTRACT FROM AUTHOR]

The single-vehicle cyclic inventory routing problem (SV-CIRP) consists of a repetitive distribution of a product from a single depot to a selected subset of customers. For each customer, selected for replenishments, the supplier collects a corresponding fixed reward. The objective is to determine the subset of customers to replenish, the quantity of the product to be delivered to each and to design the vehicle route so that the resulting profit (difference between the total reward and the total logistical cost) is maximised while preventing stockouts at each of the selected customers. This problem appears often as a sub-problem in many logistical problems. In this article, the SV-CIRP is formulated as a mixed-integer program with a nonlinear objective function. After a thorough analysis of the structure of the problem and its features, an exact algorithm for its solution is proposed. This exact algorithm requires only solutions of linear mixed-integer programs. Values of a savings-based heuristic for this problem are compared to the optimal values obtained for a set of some test problems. In general, the gap may get as large as 25%, which justifies the effort to continue exploring and developing exact and approximation algorithms for the SV-CIRP. [ABSTRACT FROM PUBLISHER]

This note considers the single-machine total weighted tardiness problem. Three new heuristic algorithms are suggested and compared with other competing heuristics from the literature, such as Apparent Tardiness Cost, Weighted Covert and Weighted Modified Due Date. The experimental tests show that the suggested heuristic algorithms outperform the existing heuristics. [ABSTRACT FROM AUTHOR]

The generalized robust colouring problem (GRCP) deals with a robust colouring for a given graph with a fixed number of colours, not necessarily the chromatic number and considers the distance between colours as the penalization of complementary edges. This problem provides a way to solve timetabling problems that consider 'event spread constraints' such as 'there must be at least d days between two events'. Because this problem is NP-hard, a heuristic approach is necessary to produce good solutions in a reasonable amount of time for large instances. In this work a greedy randomized adaptive search procedure (GRASP) is proposed to solve GRCP, which was used in instances to schedule course lectures requiring from 30 to 120 h per week in total, in which the bound of the optimal solution is reached in almost every instance. [ABSTRACT FROM AUTHOR]

In this paper, we propose a tabu search heuristic in order to solve the expansion problem (also known as update problem) of universal mobile telecommunications system (UMTS) networks. The expansion problem is currently being faced by several service providers. In fact, all network planners usually have to decide how to update the current infrastructure in order to meet new demand. This kind of problem is a generalization of the regular planning problem. This means that both the planning and the expansion problems can be solved with the proposed heuristic. Since the expansion problem has been shown to be NP-hard, we concentrate our effort on the development of an approximative approach based on tabu search. The computational results show that our heuristic is providing good results with respect to the optimal solution. [ABSTRACT FROM AUTHOR]