Work Plan

Outline of work plan - days may be renegotiated according to timetabling

University Scheduling using Genetic Algorithm

The automated timetabling and scheduling is one of the hardest problem areas. This isbecause of constraints and satisfying those constraints to get the feasible and optimizedschedule, and it is already proved as an NP Complete (1) [1]. The basic idea behind this studyis to investigate the performance of Genetic Algorithm on general scheduling problem underpredefined constraints and check the validity of results, and then having comparative analysiswith other available approaches like Tabu search, simulated annealing, direct and indirectheuristics [2] and expert system. It is observed that Genetic Algorithm is good solutiontechnique for solving such problems and later analysis will prove this argument. The programis written in C++ and analysis is done by using variation in various parameters.

Graphical constraints: a graphical user interface for constraint problems

A constraint satisfaction problem is a classical artificial intelligence paradigm characterized by a set of variables (each variable with an associated domain of possible values), and a set of constraints that specify relations among subsets of these variables. Solutions are assignments of values to all variables that satisfy all the constraints. Many real world problems may be modelled by means of constraints. The range of problems that can use this representation is very diverse and embraces areas like resource allocation, scheduling, timetabling or vehicle routing. Constraint programming is a form of declarative programming in the sense that instead of specifying a sequence of steps to execute, it relies on properties of the solutions to be found, which are explicitly defined by constraints. The idea of constraint programming is to solve problems by stating constraints which must be satisfied by the solutions. Constraint programming is based on specialized constraint solvers that take advantage of constraints to search for solutions. The success and popularity of complex problem solving tools can be greatly enhanced by the availability of friendly user interfaces. User interfaces cover two fundamental areas: receiving information from the user and communicating it to the system; and getting information from the system and deliver it to the user. Despite its potential impact, adequate user interfaces are uncommon in constraint programming in general. The main goal of this project is to develop a graphical user interface that allows to, intuitively, represent constraint satisfaction problems. The idea is to visually represent the variables of the problem, their domains and the problem constraints and enable the user to interact with an adequate constraint solver to process the constraints and compute the solutions. Moreover, the graphical interface should be capable of configure the solver’s parameters and present solutions in an appealing interactive way. As a proof of concept, the developed application – GraphicalConstraints – focus on continuous constraint programming, which deals with real valued variables and numerical constraints (equations and inequalities). RealPaver, a state-of-the-art solver in continuous domains, was used in the application. The graphical interface supports all stages of constraint processing, from the design of the constraint network to the presentation of the end feasible space solutions as 2D or 3D boxes.

Programação de horários usando um algoritmo de busca em vizinhança variável

Pós-graduação em Engenharia Elétrica - FEIS

Enhanced Mixed Integer Programming Techniques and Routing Problems

Mixed integer programming is up today one of the most widely used techniques for dealing with hard optimization problems. On the one side, many practical optimization problems arising from real-world applications (such as, e.g., scheduling, project planning, transportation, telecommunications, economics and finance, timetabling, etc) can be easily and effectively formulated as Mixed Integer linear Programs (MIPs). On the other hand, 50 and more years of intensive research has dramatically improved on the capability of the current generation of MIP solvers to tackle hard problems in practice. However, many questions are still open and not fully understood, and the mixed integer programming community is still more than active in trying to answer some of these questions. As a consequence, a huge number of papers are continuously developed and new intriguing questions arise every year. When dealing with MIPs, we have to distinguish between two different scenarios. The first one happens when we are asked to handle a general MIP and we cannot assume any special structure for the given problem. In this case, a Linear Programming (LP) relaxation and some integrality requirements are all we have for tackling the problem, and we are ``forced" to use some general purpose techniques. The second one happens when mixed integer programming is used to address a somehow structured problem. In this context, polyhedral analysis and other theoretical and practical considerations are typically exploited to devise some special purpose techniques. This thesis tries to give some insights in both the above mentioned situations. The first part of the work is focused on general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. Chapter 1 presents a quick overview of the main ingredients of a branch-and-cut algorithm, while Chapter 2 recalls some results from the literature in the context of disjunctive cuts and their connections with Gomory mixed integer cuts. Chapter 3 presents a theoretical and computational investigation of disjunctive cuts. In particular, we analyze the connections between different normalization conditions (i.e., conditions to truncate the cone associated with disjunctive cutting planes) and other crucial aspects as cut rank, cut density and cut strength. We give a theoretical characterization of weak rays of the disjunctive cone that lead to dominated cuts, and propose a practical method to possibly strengthen those cuts arising from such weak extremal solution. Further, we point out how redundant constraints can affect the quality of the generated disjunctive cuts, and discuss possible ways to cope with them. Finally, Chapter 4 presents some preliminary ideas in the context of multiple-row cuts. Very recently, a series of papers have brought the attention to the possibility of generating cuts using more than one row of the simplex tableau at a time. Several interesting theoretical results have been presented in this direction, often revisiting and recalling other important results discovered more than 40 years ago. However, is not clear at all how these results can be exploited in practice. As stated, the chapter is a still work-in-progress and simply presents a possible way for generating two-row cuts from the simplex tableau arising from lattice-free triangles and some preliminary computational results. The second part of the thesis is instead focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems in the context of routing applications. Chapters 5 and 6 present an integer linear programming local search algorithm for Vehicle Routing Problems (VRPs). The overall procedure follows a general destroy-and-repair paradigm (i.e., the current solution is first randomly destroyed and then repaired in the attempt of finding a new improved solution) where a class of exponential neighborhoods are iteratively explored by heuristically solving an integer programming formulation through a general purpose MIP solver. Chapters 7 and 8 deal with exact branch-and-cut methods. Chapter 7 presents an extended formulation for the Traveling Salesman Problem with Time Windows (TSPTW), a generalization of the well known TSP where each node must be visited within a given time window. The polyhedral approaches proposed for this problem in the literature typically follow the one which has been proven to be extremely effective in the classical TSP context. Here we present an overall (quite) general idea which is based on a relaxed discretization of time windows. Such an idea leads to a stronger formulation and to stronger valid inequalities which are then separated within the classical branch-and-cut framework. Finally, Chapter 8 addresses the branch-and-cut in the context of Generalized Minimum Spanning Tree Problems (GMSTPs) (i.e., a class of NP-hard generalizations of the classical minimum spanning tree problem). In this chapter, we show how some basic ideas (and, in particular, the usage of general purpose cutting planes) can be useful to improve on branch-and-cut methods proposed in the literature.

Un software per la gestione dell'orario delle lezioni

Lo scopo di questa tesi è lo sviluppo di un’interfaccia Web per un software di ottimizzazione, il cui scopo è la definizione dell’orario delle lezioni universitarie. Presenteremo il modello risolutivo al problema del timetabling proposto da Daskalaki et alii, e lo adatteremo alle esigenze della facoltà di Informatica dell’Università di Bologna. In effetti, la necessità di costituire un software atto alla risoluzione del problema dell’orario universitario rappresenta il tema principale trattato in questa tesi, che si ripropone, oltretutto, la costruzione di un’interfaccia grafica accattivante e intuitiva, che possa agevolmente essere utilizzata da docenti e personale di segreteria.

Railway Rapid Transit timetables with variable and elastic demand.

This paper focuses on the design of railway timetables considering a variable elastic demand profile along a whole design day. Timetabling is the third stage in the classical hierarchical railway planning process. Most of previous works on this topic consider a uniform demand behavior for short planning intervals. In this paper, we propose a MINLP model for designing non-periodic timetables on a railway corridor where demand is dependent on waiting times. In the elastic demand case, long waiting times lead to a loss of passengers, who may select an alternative transportation mode. The mode choice is modeled using two alternative methods. The first one is based on a sigmoid function and can be used in case of absence of information for competitor modes. In the second one, the mode choice probability is obtained using a Logit model that explicitly considers the existence of a main alternative mode. With the purpose of obtaining optimal departure times, in both cases, a minimization of the loss of passengers is used as objective function. Finally, as illustration, the timetabling MINLP model with both mode choice methods is applied to a real case and computational results are shown.

Impact of an intensive nursing education course on nurses' knowledge, confidence, attitudes, and perceived skills in the care of patients with cancer

Purpose/Objectives: To evaluate the impact of a cancer nursing education course on RNs. Design: Quasi-experimental, longitudinal, pretest/post-test design, with a follow-up assessment six weeks after the completion of the nursing education course. Setting: Urban, nongovernment, cancer control agency in Australia. Sample: 53 RNs, of whom 93% were female, with a mean age of 44.6 years and a mean of 16.8 years of experience in nursing; 86% of the nurses resided and worked in regional areas outside of the state capital. Methods: Scales included the Intervention With Psychosocial Needs: Perceived Importance and Skill Level Scale, Palliative Care Quiz for Nurses, Breast Cancer Knowledge, Preparedness for Cancer Nursing, and Satisfaction With Learning. Data were analyzed using multiple analysis of variance and paired t tests. Main Research Variables: Cancer nursing-related knowledge, preparedness for cancer nursing, and attitudes toward and perceived skills in the psychosocial care of patients with cancer and their families. Findings: Compared to nurses in the control group, nurses who attended the nursing education course improved in their cancer nursing-related knowledge, preparedness for cancer nursing, and attitudes toward and perceived skills in the psychosocial care of patients with cancer and their families. Improvements were evident at course completion and were maintained at the six-week follow-up assessment. Conclusions: The nursing education course was effective in improving nurses' scores on all outcome variables. Implications for Nursing: Continuing nursing education courses that use intensive mode timetabling, small group learning, and a mix of teaching methods, including didactic and interactive approaches and clinical placements, are effective and have the potential to improve nursing practice in oncology.

Emergent temporal behaviour and collaborative work

Although collaboration manifestly takes place in time, the role of time in shaping the behaviour of collaborations, and collaborative systems, is not well understood. Time is more than clock-time or the subjective experience of time; its effects on systems include differential rates of change of system elements, temporally non-linear behaviour and phenomena such as entrainment and synchronization. As a system driver, it generates emergent effects shaping systems and their behaviour. In the paper we present a systems view of time, and consider the implications of such a view through the case of collaborative development of a new university timetabling system. Teasing out the key temporal phenomena using the notion of temporal trajectories helps us understand the emergent temporal behaviour and suggests a means for improving outcomes.

Student morningness-eveningness type and performance:does class timing matter?

Circadian rhythms have often been linked to people’s performance outcomes, although this link has not been examined within the context of University students. We therefore sought to test whether students’ perceptions of their morning-evening (ME) type had an influence on their performance on modules. We tested this hypothesis using students from a number of modules at two UK Universities. Results indicated that, contrary to our hypothesis, the further the discrepancy between a student’s ME type and the teaching time of the class, the better the student’s performance. These results have implications for teaching as student ME type could be taken into account for timetabling especially if modules need to be taught multiple times. We also provide implications for those seeking to measure ME, as our results are consistent with a 5-item ME scale, a 3-item ME scale, and a single-item ME scale.

Parallel Problem Solving from Nature – PPSN XIV:14th International Conference, Edinburgh, UK, September 17-21, 2016, Proceedings

This book constitutes the refereed proceedings of the 14th International Conference on Parallel Problem Solving from Nature, PPSN 2016, held in Edinburgh, UK, in September 2016. The total of 93 revised full papers were carefully reviewed and selected from 224 submissions. The meeting began with four workshops which offered an ideal opportunity to explore specific topics in intelligent transportation Workshop, landscape-aware heuristic search, natural computing in scheduling and timetabling, and advances in multi-modal optimization. PPSN XIV also included sixteen free tutorials to give us all the opportunity to learn about new aspects: gray box optimization in theory; theory of evolutionary computation; graph-based and cartesian genetic programming; theory of parallel evolutionary algorithms; promoting diversity in evolutionary optimization: why and how; evolutionary multi-objective optimization; intelligent systems for smart cities; advances on multi-modal optimization; evolutionary computation in cryptography; evolutionary robotics - a practical guide to experiment with real hardware; evolutionary algorithms and hyper-heuristics; a bridge between optimization over manifolds and evolutionary computation; implementing evolutionary algorithms in the cloud; the attainment function approach to performance evaluation in EMO; runtime analysis of evolutionary algorithms: basic introduction; meta-model assisted (evolutionary) optimization. The papers are organized in topical sections on adaption, self-adaption and parameter tuning; differential evolution and swarm intelligence; dynamic, uncertain and constrained environments; genetic programming; multi-objective, many-objective and multi-level optimization; parallel algorithms and hardware issues; real-word applications and modeling; theory; diversity and landscape analysis.

Next generation e-learning platform: virtual laboratory simulations

Bioscience subjects require a significant amount of training in laboratory techniques to produce highly skilled science graduates. Many techniques which are currently used in diagnostic, research and industrial laboratories require expensive equipment for single users; examples of which include next generation sequencing, quantitative PCR, mass spectrometry and other analytical techniques. The cost of the machines, reagents and limited access frequently preclude undergraduate students from using such cutting edge techniques. In addition to cost and availability, the time taken for analytical runs on equipment such as High Performance Liquid Chromatography (HPLC) does not necessarily fit with the limitations of timetabling. Understanding the theory underlying these techniques without the accompanying practical classes can be unexciting for students. One alternative from wet laboratory provision is to use virtual simulations of such practical which enable students to see the machines and interact with them to generate data. The Faculty of Science and Technology at the University of Westminster has provided all second and third year undergraduate students with iPads so that these students all have access to a mobile device to assist with learning. We have purchased licences from Labster to access a range of virtual laboratory simulations. These virtual laboratories are fully equipped and require student responses to multiple answer questions in order to progress through the experiment. In a pilot study to look at the feasibility of the Labster virtual laboratory simulations with the iPad devices; second year Biological Science students (n=36) worked through the Labster HPLC simulation on iPads. The virtual HPLC simulation enabled students to optimise the conditions for the separation of drugs. Answers to Multiple choice questions were necessary to progress through the simulation, these focussed on the underlying principles of the HPLC technique. Following the virtual laboratory simulation students went to a real HPLC in the analytical suite in order to separate of asprin, caffeine and paracetamol. In a survey 100% of students (n=36) in this cohort agreed that the Labster virtual simulation had helped them to understand HPLC. In free text responses one student commented that "The terminology is very clear and I enjoyed using Labster very much”. One member of staff commented that “there was a very good knowledge interaction with the virtual practical”.

'Exploiting problem structure in a genetic algorithm approach to a nurse rostering problem'

There is considerable interest in the use of genetic algorithms to solve problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle the conflict between objectives and constraints that typically occurs in such problems. In order to overcome this, successful implementations frequently make use of problem specific knowledge. This paper is concerned with the development of a GA for a nurse rostering problem at a major UK hospital. The structure of the constraints is used as the basis for a co-evolutionary strategy using co-operating sub-populations. Problem specific knowledge is also used to define a system of incentives and disincentives, and a complementary mutation operator. Empirical results based on 52 weeks of live data show how these features are able to improve an unsuccessful canonical GA to the point where it is able to provide a practical solution to the problem.

Nurse Rostering with Genetic Algorithms

In recent years genetic algorithms have emerged as a useful tool for the heuristic solution of complex discrete optimisation problems. In particular there has been considerable interest in their use in tackling problems arising in the areas of scheduling and timetabling. However, the classical genetic algorithm paradigm is not well equipped to handle constraints and successful implementations usually require some sort of modification to enable the search to exploit problem specific knowledge in order to overcome this shortcoming. This paper is concerned with the development of a family of genetic algorithms for the solution of a nurse rostering problem at a major UK hospital. The hospital is made up of wards of up to 30 nurses. Each ward has its own group of nurses whose shifts have to be scheduled on a weekly basis. In addition to fulfilling the minimum demand for staff over three daily shifts, nurses’ wishes and qualifications have to be taken into account. The schedules must also be seen to be fair, in that unpopular shifts have to be spread evenly amongst all nurses, and other restrictions, such as team nursing and special conditions for senior staff, have to be satisfied. The basis of the family of genetic algorithms is a classical genetic algorithm consisting of n-point crossover, single-bit mutation and a rank-based selection. The solution space consists of all schedules in which each nurse works the required number of shifts, but the remaining constraints, both hard and soft, are relaxed and penalised in the fitness function. The talk will start with a detailed description of the problem and the initial implementation and will go on to highlight the shortcomings of such an approach, in terms of the key element of balancing feasibility, i.e. covering the demand and work regulations, and quality, as measured by the nurses’ preferences. A series of experiments involving parameter adaptation, niching, intelligent weights, delta coding, local hill climbing, migration and special selection rules will then be outlined and it will be shown how a series of these enhancements were able to eradicate these difficulties. Results based on several months’ real data will be used to measure the impact of each modification, and to show that the final algorithm is able to compete with a tabu search approach currently employed at the hospital. The talk will conclude with some observations as to the overall quality of this approach to this and similar problems.