Project Topics
Get Complete Project Material File(s) Now! »
Complexity Theory
There are several kinds of computerized problems, where it is common that a problem can be considered as a function, that takes inputs (the problem instances) and returns an output (the solution of the problem) [5, p. 1]. The complexity of an algorithm is a measure of how much resources in terms of time and space the algorithm needs to calculate the output, in relation to the input size given to the algorithm [6, p. 29] The complexity can be stated with an asymptotic upper bound (O notation) which states the largest amount of time or space that the algorithm may allocate [6, p. 36{37].
There has been a lot of research about di erent types of problems, nding algorithms to solve them and trying to decrease the complexity of those algorithms [5, p. 10{11]. According to these research the general complexity needed to solve problems has been discovered and complexity classes have been de ned to categorize them, see gure 2. The limits between the classes are not strict { some of them are vague and it is uncertain whether there is a distinction between some classes. Classes with lower complexity can (but do not have to) be subclasses of those with higher complexity [5, p. 10{11]. When an algorithm is to be designed to solve a problem, it can be suitable to de ne which complexity class the problem belongs to. If the complexity class of a problem is known, one can know what kind of complexity one is expected to get from the algorithm. In many applications algorithms with low complexity are preferred even though they give an approximative solution instead of the optimal [6, p. 452].
The complexity classes P, NP, NP-hard and NP-complete are now to be described. One de nition of an e cient algorithm is that the complexity of the algorithm is in polynomial time or space according to the input size to the algorithm [6, p. 33], this de nition will be used further on. One complexity class is polynomial time (P). It means that there are algorithms that solve problems within this class that have polynomial complexity, and according to our de nition of e ciency it means that the problem can be solved e ciently [6, p. 465]. Many problems are formulated as optimization problems, where the objective is to nd the minimum or maximum of some entity according to some criterion. This optimization problem can be reformulated as a decision problem, where the question is if it is possible to get a speci c number of that entity ful lling some criteria. The answer to the problem is either yes or no [6, p. 454]. If there is a polynomial way to verify that the answer is yes, given an instance to a problem and a solution that are said to ful ll the criteria, then the problem belongs to the class nondeterministic polynomial time (NP). P is suspected to be a subclass of NP. It is not proven that the classes are distinct. They might be identical. However all research indicates that there is a distinction [6, p. 464{465].
A problem is de ned to be NP-hard if it is at least as di cult to solve as any problem in NP [5, p. 30]. If a problem is both NP-hard and belongs to NP the problem is said to be NP-complete [5, p. 21]. By de nition it follows that all NP-complete problems are connected in the sense that if there is a way to e ciently solve one of them, it implies that all of them can be solved e ciently. There might exist such an e cient algorithm (the contrary has not been proven), but regardless of all e orts that have been put into nding one, no such solution has been found [6, p. 451{452].
To prove that a problem, X, is NP-hard, one makes a polynomial Karp reduction of another already proven NP-hard problem, Y, to X. The steps of the reduction are illustrated in gure 3. A black-box, or an oracle, is introduced that, given correct input, returns a solution to X. The input to Y is rearranged to the input needed for X, so the answer that is given from the oracle corresponds to the answer of Y, for every correct instance of Y. This shows that if it is possible to solve X e ciently, it is also possible to solve Y e ciently, and since Y is believed to be hard to solve then X is at least as hard to solve as Y. The rearrangement of the input from Y to the input to X needs to be done in polynomial time, otherwise the reduction itself will be ine cient and the proof falls [6, p. 453{454].
To prove that the reduction is correct one needs to consider the complexity of the re-duction (it needs to be polynomial) and prove that the answer to X is always identical to the answer of Y, for all instances that go through the reduction (i.e. it is not needed to consider instances of problem X that never will be input from the reduction of problem Y) [5, p. 17{18].
Approximative Solutions
In the real world, NP-complete problems exist, and it is not su cient to prove that they are NP-complete and then give up on a solution in the belief that an optimal solution cannot be found in polynomial time (if P is distinct from NP). Even those problems need to be solved and can be with approximative solutions. An approximative solution of an NP-hard optimization problem is a solution that ful lls the criteria of the problem and returns an answer, even though the answer is not necessarily optimal. The result from the algorithm is evaluated e ciently and, if possible, compared with the optimal result which gives a measurement of how good the solution is. These algorithms are called approximation algorithms [5, p. 39]. For some algorithms that receive an approximative solution, it is not possible to state how good the solution is compared to the optimal { these algorithms are called heuristics and are useful because of fast evaluation and often high quality of solutions on many instances, even though the quality cannot be guaranteed [5, p. 78{79].
Heuristics
There are numerous heuristics that can yield good solutions to NP-complete problems. Start-ing with an initial solution, local search can be used to nd better solutions within the solution space, where the solution is tweaked and the new solution is analyzed in order to be accepted or rejected [7]. The behavior of a local search algorithm on a certain prob-lem instance depends on three aspects: the quality of the initial solution, the neighborhood function, and the strategy to select new solutions. The neighborhood function de nes which solutions that can be reached by tweaking the current solution. There is a trade-o between narrow and broad neighborhoods. Narrow neighborhoods allow faster traversing through the neighborhood while broad ones cover a larger part of the solution space in each iteration. The selection strategy of new solutions de ne how and when to analyze new solutions [5].
One method of tweaking solutions is using k-opt, in which k edges between nodes in a route are removed and reconnected in a di erent way [7].
Simulated annealing can be used to search for better solutions within the solution space. If the tweaked solution is better than the original, the former is accepted and this solution is tweaked in the next iteration. This way, we hope to move towards better solutions. In order to escape local minima, there is always a possibility to proceed with worse solutions, so as to nd better ones in subsequent iterations [8, p. 25]. Worse solutions are accepted with some probability, which in the beginning of the search is large, resulting in the algorithm accepting almost any solution. The probability of accepting a solution is de ned in equation 1 for maximization problems [8, p. 25], where Quality(S) and Quality(R) are the solution scores of the non-tweaked and tweaked score respectively. t is called a temperature, and determines how large the probability will be. It is set to a large number at rst, so as to allow many solutions to be accepted, and is decreased over time.
P (t; R; S) = e(Quality(R) Quality(S))=t (1)
Tabu search is a way of exploring the solution space by avoiding returning to previously tried solutions. Each new solution is stored in a tabu list and subsequent solutions are compared to them. Solutions may not be reused for l following iterations, where l is a prede ned value [8, p. 26].
Scheduling Problems for Advanced Health Care at Home
A well-studied similar problem to the scheduling problem is the Vehicle routing problem with Time Windows (VRPTW). In VRPTW the aim is to nd routes that minimize the violation of time windows, travel time, and the number of vehicles performing the routes. This problem is NP-hard (see for example [9]). Even deciding if a feasible solution exists is NP-hard [10]. This problem occurs in widespread areas and has been thoroughly studied. There are exact algorithms that solve problem instances with up to 100 stops, but these algorithms require more time than is reasonable in most applications [9]. In order to make the algorithms usable for health care applications additional constraints need to be considered. Although several research studies have been performed on the Home Health Care Scheduling problem (HHCSP), to the best of our knowledge, none of them cover the same combination of constraints as our approach, see tables 2 and 3.
There are more parameters, assumptions and approaches that distinguish those projects than the tables show. The tables were designed to emphasize the relevant similarities and di erences from our project. Furthermore, intended use of those solutions are in home assistance, while our intended use is in advanced health care at home.
Home assistance is designated to elderly home care. The patients are not admitted to a hospital. Home assistance is used for long-term care where the same type of care is needed on a regular basis. Home assistance is a part of primary care whose purpose is to provide basic (medical and non-medical) care that does not require medical or technical competences from the hospital [21]. In advanced health care at home however, as described in the introduction 1, the patients are admitted to a hospital, can be admitted during a varying time span, and the need of care is not regular.
The distinctions between home assistance and advanced health care at home have impli-cations for the implementation of the algorithm. For visits that recur over months or years, it is feasible for the user to enter a large amount of patient information into the software system for each type of visit, as is common for home assistance scheduling tools. It is not so when visits are needed for a very limited period of time and changes in care plan are frequent. In advanced health care at home, where changes are more likely than unlikely, the usefulness of a scheduling tool is augmented if it can solve updates (addressed in [14]).
At a study visit at Tieto Sweden Healthcare & Welfare AB (Jorgen L 2015, Senior Sales Manager, oral communication, 19th February) we were told that most home assistance clinics in Sweden have been using some kind of scheduling tool since the last decade. In the introduction stage it was used to increase the e ciency in the work ow in order to reduce the number of sta . During the last decade the number of patients per work hour has increased and scheduling tools have played an important role in that process. We were also told that their implementation of Eveborn’s [22] solution on HHCSP has been trialed in advanced health care, but it was clear that it was not transferrable without adjustments.
Solomon [23] suggests an insertion heuristic for obtaining an initial solution to VRPTW, which was proven to give optimal or near optimal results in a reasonable amount of time. In his approach the number of vehicles (corresponding to HCPs in our problem) are unlimited. The algorithm is greedy; in each step it chooses the best move in order to optimize the result. A seed customer (corresponding to a visit) is selected and inserted in a route. Then the routes are lled successively with customers until the capacity (corresponding to work hours) of the vehicle is lled. The seed customer is the rst customer in the route, and is selected among the unplanned customers by some criterion, or a combination of criteria (for example farthest customer from the depot (corresponding to the hospital)). The idea is to use the seeds to get a good clustering of visits for each vehicle, then the following customers are selected by a minimization function. When the capacity of one vehicle is lled the procedure starts over with a new vehicle, until all customers are served. The result is widely accepted and used in subsequent research (e.g. [24, 25]) as an initial solution to VRPTW or extensions of it. Potvin and Rousseau [25] show that parallel construction of the routes improve the result with random distributed instances, compared with sequential construction that Solomon performs.
Method
This chapter describes the project methodology, what software development tools that have been used, and testing methods.
As software development method, we used the agile scrum method. We divided the project in small parts, sprints, of one to two weeks. After each sprint we evaluated the process and planned the following sprint in the project management system JIRA. We had as close cooperation with the ward during the entire process as possible.
The problem was de ned based on information from informal interviews and observations at SABH as well as eld studies performed by the Innovation Center at Karolinska University Hospital. The problem was inspected from a theoretical computer science perspective; the complexity class of the problem was identi ed and proven (see section 4.1). Solutions of problems within the same complexity class were studied in order to develop an algorithm that solves the problem (see section 2.3). A prototype of the algorithm was implemented in C#. A database was built using SQL Server Express to store the input and output from the algorithm. The distance matrix was retrieved from Nokia’s REST-API HERE.
We concluded the project with a presentation to the ward to get feedback on our inter-pretation of the problem, understand if we have included all important parameters and learn about what they would like to be done in the future for the system to be usable. We also presented a questionnaire to gather more information about these issues.
Testing
Multiple testing methods were employed to verify that the code performed as intended and to validate that the algorithm ful lled the ward’s functional requirements. Speci cally, the testing objectives were to
i) detect code bugs (and handle them),
ii) understand how the parameters in the objective function should be weighted,
iii) understand which of the suggested swaps in the local search improve the schedule,
iv) obtain an estimate of the runtime of the program,
v) nd the number of iterations that we can run (and if they di er between shifts), and
vi) investigate how a fully functional implementation would a ect the ward’s way of work-ing.
Testing was based on real data from the ward and the number of visits to be sched-uled could easily be controlled by choosing to include only the day, evening or night shift (containing 2{30 visits and 2{8 HCPs). In accordance with the Swedish Patient Data Act all patient data was anonymized by substituting names and social security numbers with ctitious identi cation numbers and addresses with nearby addresses. Furthermore the data was entered manually into our program, due to bureaucracy at the hospital that, in order to respect the Swedish Patient Data Act, had a robust process for access to the journal system.
For veri cation, we ran our program on data from the ward, and compared our schedule with the ward’s. This allowed us to detect and handle code bugs, adjust the weights of di erent optimization parameters (travel time, time window exceeding, person continuity and amount of free time between visits) and estimate runtime. We determined the number of iterations to run for each shift by setting a threshold for an acceptable schedule score.
We investigated how the algorithm was a ected by the weights by changing one of them and keeping the others constant.
Table of contents :
1 Introduction
1.1 Aim and Objectives
1.2 Description of the Ward
1.3 Automated Scheduler Components
1.4 Problem Formulation
1.4.1 Daily Scheduling Problem
1.4.2 Rescheduling Problem
1.5 Limitations
1.6 Input Parameters
2 Theory
2.1 Complexity Theory
2.2 Approximative Solutions
2.2.1 Heuristics
2.3 Scheduling Problems for Advanced Health Care at Home
3 Method
3.1 Testing
4 Results
4.1 Proof of NP-completeness
4.1.1 Daily Scheduling Problem 2 NP
4.1.2 Daily Scheduling Problem is NP-hard
4.1.3 Daily Scheduling Problem is NP-complete
4.1.4 Rescheduling Problem is NP-complete
4.2 Modeling Data
4.3 Algorithm
4.3.1 Initial Solution of the Daily Scheduling Problem
4.3.2 Mathematical Functions
4.3.3 Local Search Algorithm of the Daily Scheduling Problem
4.3.4 Rescheduling Algorithm
4.4 Evaluation of Algorithms
4.4.1 Complexity
4.4.2 Solution’s Distance from the Optimal Solution
4.5 Testing
4.6 Presentation at the Ward
5 Discussion
5.1 Improving the Algorithms
5.2 Testing Method
5.3 Condentiality
5.4 Usefulness of the Automated Scheduler
5.5 Risks and Vulnerabilities
6 Conclusion
