Goto

Collaborating Authors

An Intelligent Model for Solving Manpower Scheduling Problems

arXiv.org Artificial Intelligence

The manpower scheduling problem is a critical research field in the resource management area. Based on the existing studies on scheduling problem solutions, this paper transforms the manpower scheduling problem into a combinational optimization problem under multi-constraint conditions from a new perspective. It also uses logical paradigms to build a mathematical model for problem solution and an improved multi-dimensional evolution algorithm for solving the model. Moreover, the constraints discussed in this paper basically cover all the requirements of human resource coordination in modern society and are supported by our experiment results. In the discussion part, we compare our model with other heuristic algorithms or linear programming methods and prove that the model proposed in this paper makes a 25.7% increase in efficiency and a 17% increase in accuracy at most. In addition, to the numerical solution of the manpower scheduling problem, this paper also studies the algorithm for scheduling task list generation and the method of displaying scheduling results. As a result, we not only provide various modifications for the basic algorithm to solve different condition problems but also propose a new algorithm that increases at least 28.91% in time efficiency by comparing with different baseline models.


A hybrid optimization approach for employee rostering: Use cases at Swissgrid and lessons learned

arXiv.org Artificial Intelligence

Employee rostering is a process of assigning available employees to open shifts. Automating it has ubiquitous practical benefits for nearly all industries, such as reducing manual workload and producing flexible, high-quality schedules. In this work, we develop a hybrid methodology which combines Mixed-Integer Linear Programming (MILP) with scatter search, an evolutionary algorithm, having as use case the optimization of employee rostering for Swissgrid, where it is currently a largely manual process. The hybrid methodology guarantees compliance with labor laws, maximizes employees' preference satisfaction, and distributes workload as uniformly as possible among them. Above all, it is shown to be a robust and efficient algorithm, consistently solving realistic problems of varying complexity to near-optimality an order of magnitude faster than an MILP-alone approach using a state-of-the-art commercial solver. Several practical extensions and use cases are presented, which are incorporated into a software tool currently being in pilot use at Swissgrid.


An Automated Employee Timetabling System for Small Businesses

AAAI Conferences

Employee scheduling is one of the most difficult challenges facing any small business owner. The problem becomes more complex when employees with different levels of seniority indicate preferences for specific roles in certain shifts and request flexible work hours outside of the standard eight-hour block. Many business owners and managers, who cannot afford (or choose not to use) commercially-available timetabling apps, spend numerous hours creating sub-optimal schedules by hand, leading to low staff morale. In this paper, we explain how two undergraduate students generalized the Nurse Scheduling Problem to take into account multiple roles and flexible work hours, and implemented a user-friendly automated timetabler based on a four-dimensional integer linear program. This system has been successfully deployed at two businesses in our community, each with 20+ employees: a coffee shop and a health clinic.


A flexible integer linear programming formulation for scheduling clinician on-call service in hospitals

arXiv.org Artificial Intelligence

Scheduling of personnel in a hospital environment is vital to improving the service provided to patients and balancing the workload assigned to clinicians. Many approaches have been tried and successfully applied to generate efficient schedules in such settings. However, due to the computational complexity of the scheduling problem in general, most approaches resort to heuristics to find a non-optimal solution in a reasonable amount of time. We designed an integer linear programming formulation to find an optimal schedule in a clinical division of a hospital. Our formulation mitigates issues related to computational complexity by minimizing the set of constraints, yet retains sufficient flexibility so that it can be adapted to a variety of clinical divisions. We then conducted a case study for our approach using data from the Infectious Diseases division at St. Michael's Hospital in Toronto, Canada. We analyzed and compared the results of our approach to manually-created schedules at the hospital, and found improved adherence to departmental constraints and clinician preferences. We used simulated data to examine the sensitivity of the runtime of our linear program for various parameters and observed reassuring results, signifying the practicality and generalizability of our approach in different real-world scenarios.


Knowledge engineering mixed-integer linear programming: constraint typology

arXiv.org Artificial Intelligence

In this paper, we investigate the constraint typology of mixed-integer linear programming MILP formulations. MILP is a commonly used mathematical programming technique for modelling and solving real-life scheduling, routing, planning, resource allocation, timetabling optimization problems, providing optimized business solutions for industry sectors such as: manufacturing, agriculture, defence, healthcare, medicine, energy, finance, and transportation. Despite the numerous real-life Combinatorial Optimization Problems found and solved, and millions yet to be discovered and formulated, the number of types of constraints, the building blocks of a MILP, is relatively much smaller. In the search of a suitable machine readable knowledge representation for MILPs, we propose an optimization modelling tree built based upon an MILP ontology that can be used as a guidance for automated systems to elicit an MILP model from end-users on their combinatorial business optimization problems.