Multiple-Retrieval Case-Based Reasoning for Course Timetabling Problems

The structured representation of cases by attribute graphs in a Case-Based Reasoning (CBR) system for course timetabling has been the subject of previous research by the authors. In that system, the case base is organised as a decision tree and the retrieval process chooses those cases which are sub attribute graph isomorphic to the new case. The drawback of that approach is that it is not suitable for solving large problems. This paper presents a multiple-retrieval approach that partitions a large problem into small solvable sub-problems by recursively inputting the unsolved part of the graph into the decision tree for retrieval. The adaptation combines the retrieved partial solutions of all the partitioned sub-problems and employs a graph heuristic method to construct the whole solution for the new case. We present a methodology which is not dependant upon problem specific information and which, as such, represents an approach which underpins the goal of building more general timetabling systems. We also explore the question of whether this multiple-retrieval CBR could be an effective initialisation method for local search methods such as Hill Climbing, Tabu Search and Simulated Annealing. Significant results are obtained from a wide range of experiments. An evaluation of the CBR system is presented and the impact of the approach on timetabling research is discussed. We see that the approach does indeed represent an effective initialisation method for these approaches.

Case-Based Reasoning as a Heuristic Selector in a Hyper-Heuristic for Course Timetabling Problems

This paper studies Knowledge Discovery (KD) using Tabu Search and Hill Climbing within Case-Based Reasoning (CBR) as a hyper-heuristic method for course timetabling problems. The aim of the hyper-heuristic is to choose the best heuristic(s) for given timetabling problems according to the knowledge stored in the case base. KD in CBR is a 2-stage iterative process on both case representation and the case base. Experimental results are analysed and related research issues for future work are discussed.

Knowledge discovery in hyper-heuristic using case-based reasoning on course timetabling

This paper presents a new hyper-heuristic method using Case-Based Reasoning (CBR) for solving course timetabling problems. The term Hyper-heuristics has recently been employed to refer to 'heuristics that choose heuristics' rather than heuristics that operate directly on given problems. One of the overriding motivations of hyper-heuristic methods is the attempt to develop techniques that can operate with greater generality than is currently possible. The basic idea behind this is that we maintain a case base of information about the most successful heuristics for a range of previous timetabling problems to predict the best heuristic for the new problem in hand using the previous knowledge. Knowledge discovery techniques are used to carry out the training on the CBR system to improve the system performance on the prediction. Initial results presented in this paper are good and we conclude by discussing the con-siderable promise for future work in this area.

Case-based reasoning in course timetabling: an attribute graph approach

An earlier Case-based Reasoning (CBR) approach developed by the authors for educational course timetabling problems employed structured cases to represent the complex relationships between courses. Previous solved cases represented by attribute graphs were organized hierarchically into a decision tree. The retrieval searches for graph isomorphism among these attribute graphs. In this paper, the approach is further developed to solve a wider range of problems. We also attempt to retrieve those graphs that have common similar structures but also have some differences. Costs that are assigned to these differences have an input upon the similarity measure. A large number of experiments are performed consisting of different randomly produced timetabling problems and the results presented here strongly indicate that a CBR approach could provide a significant step forward in the development of automated system to solve difficult timetabling problems. They show that using relatively little effort, we can retrieve these structurally similar cases to provide high quality timetables for new timetabling problems.

Multiple-retrieval case-based reasoning for course timetabling problems

The structured representation of cases by attribute graphs in a Case-Based Reasoning (CBR) system for course timetabling has been the subject of previous research by the authors. In that system, the case base is organised as a decision tree and the retrieval process chooses those cases which are sub attribute graph isomorphic to the new case. The drawback of that approach is that it is not suitable for solving large problems. This paper presents a multiple-retrieval approach that partitions a large problem into small solvable sub-problems by recursively inputting the unsolved part of the graph into the decision tree for retrieval. The adaptation combines the retrieved partial solutions of all the partitioned sub-problems and employs a graph heuristic method to construct the whole solution for the new case. We present a methodology which is not dependant upon problem specific information and which, as such, represents an approach which underpins the goal of building more general timetabling systems. We also explore the question of whether this multiple-retrieval CBR could be an effective initialisation method for local search methods such as Hill Climbing, Tabu Search and Simulated Annealing. Significant results are obtained from a wide range of experiments. An evaluation of the CBR system is presented and the impact of the approach on timetabling research is discussed. We see that the approach does indeed represent an effective initialisation method for these approaches.

Enhancing the usability of numerical models with case-based reasoning

Abstract not available

Definition of Model-based diagnosis problems with Altarica

International audience

Meta-analysis and cross-validation of a hyperglycemic status predictor model based on salivary glucose

Poster presented at the First International Congress of CiiEM - From Basic Sciences To Clinical Research. Egas Moniz, Caparica, Portugal, 27-28 November 2015.

Collaborative Networked Organizations as System of Systems: A Model-Based Engineering Approach

Part 6: Engineering and Implementation of Collaborative Networks

A novel time computation model based on algorithm complexity for data intensive scientific workflow design and scheduling

Scientific workflow offers a framework for cooperation between remote and shared resources on a grid computing environment (GCE) for scientific discovery. One major function of scientific workflow is to schedule a collection of computational subtasks in well-defined orders for efficient outputs by estimating task duration at runtime. In this paper, we propose a novel time computation model based on algorithm complexity (termed as TCMAC model) for high-level data intensive scientific workflow design. The proposed model schedules the subtasks based on their durations and the complexities of participant algorithms. Characterized by utilization of task duration computation function for time efficiency, the TCMAC model has three features for a full-aspect scientific workflow including both dataflow and control-flow: (1) provides flexible and reusable task duration functions in GCE;(2) facilitates better parallelism in iteration structures for providing more precise task durations;and (3) accommodates dynamic task durations for rescheduling in selective structures of control flow. We will also present theories and examples in scientific workflows to show the efficiency of the TCMAC model, especially for control-flow. Copyright©2009 John Wiley & Sons, Ltd.

An epidemic model based temporal violation prediction strategy for large batch of parallel business cloud workflows

Temporal violations often take place during the running of large batch of parallel business cloud workflow, which have a serious impact on the on-time completion of massive concurrent user requests. Existing studies have shown that local temporal violations (namely the delays of workflow activities) occurring during cloud workflow execution are the fundamental causes for failed on-time completion. Therefore, accurate prediction of temporal violations is a very important yet challenging task for business cloud workflows. In this paper, based on an epidemic model, a novel temporal violation prediction strategy is proposed to estimate the number of local temporal violations and the number of violations that must be handled so as to achieve a certain on-time completion rate before the execution of workflows. The prediction result can be served as an important reference for temporal violation prevention and handling strategies such as static resource reservation and dynamic provision. Specifically, we first analyze the queuing process of the parallel workflow activities, then we predict the number of potential temporal violations based on a novel temporal violation transmission model inspired by an epidemic model. Comprehensive experimental results demonstrate that our strategy can achieve very high prediction accuracy under different situations.

Cost and feasibility of a barrier to halt the spread of invasive cane toads in arid Australia: incorporating expert knowledge into model-based decision-making

1. Active engagement with practitioners is a crucial component of model-based decision-making in conservation management; it can assist with data acquisition, improve models and help narrow the 'knowing-doing' gap.
2. We worked with practitioners of one of the worst invasive species in Australia, the cane toad Rhinella marina, to revise a model that estimates the effectiveness of landscape barriers to contain spread. The original model predicted that the invasion could be contained by managing artificial watering points on pastoral properties, but was initially met with scepticism by practitioners, in part due to a lack of engagement during model development.
3. We held a workshop with practitioners and experts in cane toad biology. Using structured decision-making, we elicited concerns about the original model, revised its structure, updated relevant input data, added an economic component and found the most cost-effective location for a barrier across a range of fixed budgets and management scenarios. We then conducted scenario analyses to test the sensitivity of management decisions to model revisions.
4. We found that toad spread could be contained for all of the scenarios tested. Our modelling suggests a barrier could cost $4·5 M (2015 AUD) over 50 years for the most likely landscape scenario. The incorporation of practitioner knowledge into the model was crucial. As well as improving engagement, when we incorporated practitioner concerns (particularly regarding the effects of irrigation and dwellings on toad spread), we found a different location for the optimal barrier compared to a previously published study (Tingley et al. 2013).
5. Synthesis and applications. Through engagement with practitioners, we turned an academic modelling exercise into a decision-support tool that integrated local information, and considered more realistic scenarios and constraints. Active engagement with practitioners led to productive revisions of a model that estimates the effectiveness of a landscape barrier to contain spread of the invasive cane toad R. marina. Benefits also include greater confidence in model predictions, improving our assessment of the cost and feasibility of containing the spread of toads.

A SCR Model based on Reactor and Engine Experimental Studies for a Cu-zeolite Catalyst

A NOx reduction efficiency higher than 95% with NH3 slip less than 30 ppm is desirable for heavy-duty diesel (HDD) engines using selective catalytic reduction (SCR) systems to meet the US EPA 2010 NOx standard and the 2014-2018 fuel consumption regulation. The SCR performance needs to be improved through experimental and modeling studies. In this research, a high fidelity global kinetic 1-dimensional 2-site SCR model with mass transfer, heat transfer and global reaction mechanisms was developed for a Cu-zeolite catalyst. The model simulates the SCR performance for the engine exhaust conditions with NH3 maldistribution and aging effects, and the details are presented. SCR experimental data were collected for the model development, calibration and validation from a reactor at Oak Ridge National Laboratory (ORNL) and an engine experimental setup at Michigan Technological University (MTU) with a Cummins 2010 ISB engine. The model was calibrated separately to the reactor and engine data. The experimental setup, test procedures including a surrogate HD-FTP cycle developed for transient studies and the model calibration process are described. Differences in the model parameters were determined between the calibrations developed from the reactor and the engine data. It was determined that the SCR inlet NH3 maldistribution is one of the reasons causing the differences. The model calibrated to the engine data served as a basis for developing a reduced order SCR estimator model. The effect of the SCR inlet NO2/NOx ratio on the SCR performance was studied through simulations using the surrogate HD-FTP cycle. The cumulative outlet NOx and the overall NOx conversion efficiency of the cycle are highest with a NO2/NOx ratio of 0.5. The outlet NH3 is lowest for the NO2/NOx ratio greater than 0.6. A combined engine experimental and simulation study was performed to quantify the NH3 maldistribution at the SCR inlet and its effects on the SCR performance and kinetics. The uniformity index (UI) of the SCR inlet NH3 and NH3/NOx ratio (ANR) was determined to be below 0.8 for the production system. The UI was improved to 0.9 after installation of a swirl mixer into the SCR inlet cone. A multi-channel model was developed to simulate the maldistribution effects. The results showed that reducing the UI of the inlet ANR from 1.0 to 0.7 caused a 5-10% decrease in NOx reduction efficiency and 10-20 ppm increase in the NH3 slip. The simulations of the steady-state engine data with the multi-channel model showed that the NH3 maldistribution is a factor causing the differences in the calibrations developed from the engine and the reactor data. The Reactor experiments were performed at ORNL using a Spaci-IR technique to study the thermal aging effects. The test results showed that the thermal aging (at 800°C for 16 hours) caused a 30% reduction in the NH3 stored on the catalyst under NH3 saturation conditions and different axial concentration profiles under SCR reaction conditions. The kinetics analysis showed that the thermal aging caused a reduction in total NH3 storage capacity (94.6 compared to 138 gmol/m3), different NH3 adsorption/desorption properties and a decrease in activation energy and the pre-exponential factor for NH3 oxidation, standard and fast SCR reactions. Both reduction in the storage capability and the change in kinetics of the major reactions contributed to the change in the axial storage and concentration profiles observed from the experiments.

DYNAMIC MODEL BASED STATE ESTIMATION IN A HEAVY DUTY DIESEL AFTERTREATMENT SYSTEM FOR ONBOARD DIAGNOSTICS AND CONTROLS

Estimating un-measurable states is an important component for onboard diagnostics (OBD) and control strategy development in diesel exhaust aftertreatment systems. This research focuses on the development of an Extended Kalman Filter (EKF) based state estimator for two of the main components in a diesel engine aftertreatment system: the Diesel Oxidation Catalyst (DOC) and the Selective Catalytic Reduction (SCR) catalyst. One of the key areas of interest is the performance of these estimators when the catalyzed particulate filter (CPF) is being actively regenerated. In this study, model reduction techniques were developed and used to develop reduced order models from the 1D models used to simulate the DOC and SCR. As a result of order reduction, the number of states in the estimator is reduced from 12 to 1 per element for the DOC and 12 to 2 per element for the SCR. The reduced order models were simulated on the experimental data and compared to the high fidelity model and the experimental data. The results show that the effect of eliminating the heat transfer and mass transfer coefficients are not significant on the performance of the reduced order models. This is shown by an insignificant change in the kinetic parameters between the reduced order and 1D model for simulating the experimental data. An EKF based estimator to estimate the internal states of the DOC and SCR was developed. The DOC and SCR estimators were simulated on the experimental data to show that the estimator provides improved estimation of states compared to a reduced order model. The results showed that using the temperature measurement at the DOC outlet improved the estimates of the CO , NO , NO2 and HC concentrations from the DOC. The SCR estimator was used to evaluate the effect of NH3 and NOX sensors on state estimation quality. Three sensor combinations of NOX sensor only, NH3 sensor only and both NOX and NH3 sensors were evaluated. The NOX only configuration had the worst performance, the NH3 sensor only configuration was in the middle and both the NOX and NH3 sensor combination provided the best performance.

Qualitative Futures

Price, C., Trave-Massuyes, L., Milne, R., Ironi, L., Forbus, K., Bredeweg, B., Lee, M., Struss, P., Snooke, N., Lucas, P., Cavazza, M., Coghill, G. (2006). Qualitative Futures. The Knowledge Engineering Review, 21 (4), 317-334. Sponsorship: MONET European Network on Qualitative and Model-Based Reasoning