Article Preview
TopIntroduction
Nurse Rostering Problem (NRP) is the multiple operational research constrained combinatorial optimization problem (Wren, 1995). It is the class of assignment problem where shifts are allocated to nurses over a given planning period in such a way that the generated roster satisfies all hard constraints to make the roster viable and all possible soft constraints to get a high-quality roster. The roster is assigning tasks to nurse as per the requirements of the organization including Nurse workload, skills, and different policies adopted by the hospital, nurse's contracts, shift requirements, demands for Nurse and seasonal requirements, etc. These parameters may fluctuate over various hospitals. Producing good quality roster manually is a very delicate task for a manager or head nurse. It requires a lot of paperwork, time, and struggle. Automating the roster will reduce stress on head nurses and they will enjoy their work and focus on their primary duty. The nurse Rostering Problem is classified into NP-hard class problems (Wren, 1995). NP-hard problems are difficult to solve with the help of deterministic methods hence most commonly used approach includes meta-heuristics. Metaheuristics algorithms are general-purpose algorithms, independent of the nature of the problem. These algorithms apply to the problem that having very high candidate solutions and the complexity of problems. The candidate solutions may grow by increasing any single dimension of the problem like reducing a nurse, adding a shift, restriction on work assignment, and size of the roster.
To distinguish between feasible and infeasible roster constraints divide them into two classes for example Hard Constraints and Soft Constraints. An algorithm starts with a stochastic initialization solution. A hard constraint provides feasibility to the roster rather than quality. Soft constraints are contributing to an objective function that concentrates on optimality rather than feasibility. Fitness function measures how well the roster satisfies all soft constraints. Weight is assigned to constraints depending on their priority. A roster can be either cyclic or acyclic. In Cyclic all nurses have the same work pattern for the fixed planning period. A cyclic roster is very rigid while the acyclic roster has more flexibility.
In this work, the population-based Evolutionary technique i.e. Particle Swarm Optimization adapted. Compared to traditional optimization techniques, Evolutionary Algorithms have a few highlights that empower tackling Nurse Rostering Problem. Highlights are: Evolutionary algorithms have stochastic nature, simplicity of execution, global search capability, and very few parameters needed to be tuned, and so on.
Essentially, NRP is a highly constrained problem, when applying PSO on NRP, require more particles to represent to get an optimized roster in the least amount of time. However, as population size raised, it becomes more time consuming to get an optimal solution. To improve the performance of the sequential code, initially, functions that are compute-intensive identified using GNU GCC Profiling Tool and parallelize only these functions. The parallel algorithm gives the same result as sequential with the least amount of time. Finally, compare speedup of sequential with parallel code.