This thesis deals with the description of the state of resource-constrained project scheduling problem. It defines the formal problem and its complexity. It also describes variants of this problem. Algorithms for solving RCPSP are presented. Heuristic genetic algorithm GARTH is analyzed in depth. The implementation of prototypes solving RCPSP using GARTH is outlined. Several improvements to the original algorithm are designed and evaluated.

of Doctoral Thesis Title: Components and Services in Resource-Constrained Envi- ronments Author: Tomáš Pop tomas.pop@d3s.mff.cuni.cz Department: Department of Distributed and Dependable Systems Faculty of Mathematics and Physics Charles University in Prague Advisor: Prof. František Plášil plasil@d3s.mff.cuni.cz Abstract Appliances of every day use such as consumer electronics, automotive and telecommunication devices as well as various kinds of control systems have be- come a common and important part of our everyday lives. In comparison to general-purpose desktop systems, they are limited in terms of various resources, for example memory, CPU power, and battery capacity. Component-based soft- ware engineering is a well-established development technique, which has found its way to industry and has been successfully used for a long time in multiple do- mains. However, the industrially adopted component frameworks were designed for general-purpose systems and they can be hardly used in resource-constrained environments. In the thesis, we explore the potential of component-based system engineer- ing in resource-constrained environments. Stemming from a survey of existing component frameworks targeted to this domain, we identify the most important approaches to overcome resource constraints in...

This paper analyses the current state of research regarding solution methods dealing with resource-constrained project scheduling problems. The intention is to present a concentrated survey and brief scientific overview on models, their decision variables and constraints as well as current solution methods in the field of project scheduling. The allocation of scarce resources among multiple projects with different, conflicting decision variables is a highly difficult problem in order to achieve an optimal schedule which meets all (usually different) of the projects’ objectives. Those projects, e.g. the assembly of complex machinery and goods, consume many renewable, e.g. workforce/staff, and non-renewable, e.g. project budget, resources. Each single process within these projects can often be performed in different ways – so called execution modes can help to make a schedule feasible. On the other hand the number of potential solutions increases dramatically through this fact. Additional constraints, e.g. min/max time lags, preemption or specific precedence relations of activities, lead to highly complex problems which are NP-hard in the strong sense.

Der Planungsprozess des Produktionsablaufes ist insbesondere in personalintensiven Bereichen durch einen hohen Komplexitätsgrad gekennzeichnet. Dies gilt nicht allein für die Domäne der Fertigung von Industriegütern, sondern ist überall dort charakteristisch, wo projektähnliche Aufgaben und Tätigkeiten im Kurzfristbereich hinsichtlich Ressourcenzuteilung determiniert werden müssen. Personal ist hierbei weitaus weniger homogen, als dies auf andere Ressourcentypen zutrifft. Daher gilt es der Heterogenität der Prozesse und Strukturen unter Beachtung individuell ausgeprägter Eigenschaften und Fähigkeiten des Personals einen quantitativ beschreibbaren und damit operationali-sierbaren Rahmen zu geben. Die Komplexität einer personalbezogenen, zielfunktionsorientierten Zuteilungsentscheidung kann im Kontext der Kapazitätsplanung damit signifikant reduziert werden.

It's commonly assumed that experience leads to efficiency, yet this is largely unaccounted for in resource-constrained project scheduling. This thesis considers the idea that learning effects could allow selected activities to be completed within reduced time, if they're scheduled after activities where workers learn relevant skills. This paper computationally explores the effect of this autonomous, intra-project learning on optimal makespan and problem difficulty. A learning extension is proposed to the standard RCPSP scheduling problem. Multiple parameters are considered, including project size, learning frequency, and learning intensity. A test instance generator is developed to adapt the popular PSPLIB library of scheduling problems to this model. Four different Constraint Programming model formulations are developed to efficiently solve the model. Bounding techniques are proposed for tightening optimality gaps, including four lower bounding model relaxations, an upper bounding model relaxation, and a Destructive Lower Bounding method. Hundreds of thousands of scenarios are tested to empirically determine the most efficient solution approaches and the impact of learning on project schedules. Potential makespan reduction as high as 50% is discovered, with the learning effects resembling a learning curve with a point of diminishing returns. A combination of bounding techniques is proven to produce significantly tighter optimality gaps.

An increasing number of complex applications are being executed on resource constrained devices, such as drones and rovers. Such systems often operate in dynamic and unknown environments, and consequently have dynamic performance requirements based on their surroundings. These systems must consider the trade-off between application and platform performance in order to operate within resource means. This thesis proposes a runtime resource management system for a monolithic localization application. The proposed strategy uses gradient boosting regressors to predict localization accuracy and power consumption at runtime for a set of configurable application and platform parameters. A model-based controller selects parameters at runtime to optimize localization accuracy subject to a power constraint. The testbed used for experiments consists of maplab, a visual-inertial localization and mapping framework, executed monolithically on the Nvdia Jetson AGX platform. The results highlight the importance of incorporating dynamic parameters when identifying predictive models for localization systems. The proposed system is able to track a power reference while maintaining reasonable localization accuracy at runtime, for both platform and application parameters. The results demonstrate that runtime control can achieve better performance than alternative solutions which rely on offline profiling of the configuration space. / Ett ökande antal komplexa program körs på resursbegränsade enheter, till exempel drönare och rover. Sådana system fungerar ofta i dynamiska och okända miljöer och har därför dynamiska prestandakrav som är baserade på deras omgivningar. I dessa system måste hänsyn tas till skillnaden mellan applikations- och plattformsprestanda för att kunna fungera med hjälp av resurser. I den här tesen föreslås ett resurshanteringssystem för körning av ett monolitiskt lokaliseringsprogram. Den föreslagna strategin använder övertoningsförstärkare för att förutsäga lokaliseringens exakthet och energiförbrukning vid körning för en uppsättning konfigurerbara program- och plattformsparametrar. En modellbaserad styrenhet väljer parametrar under körning för att optimera lokaliseringsnoggrannheten under förutsättning att det finns en energibegränsning. Den testbädd som används för experiment består av maplab, en ram för visuell tröghetslokalisering och kartläggning, som utförts monolitiskt på Nvdia Jetson AGX-plattformen. Resultaten belyser vikten av att införliva dynamiska parametrar när man identifierar förutsägbara modeller för lokaliseringssystem. Det föreslagna systemet kan spåra en energireferens samtidigt som man bibehåller en rimlig lokaliseringsnoggrannhet vid körning, för både plattformsparametrar och programparametrar. Resultaten visar att körningskontroll kan ge bättre prestanda än alternativa lösningar som är beroende av offlineprofilering av konfigurationsutrymmet.

Nigerian entrepreneurs face government barriers and lack the skills and awareness needed for successfully creating and scaling public value in resource-constrained environments. The concept of bricolage, which involves doing business by making do with resources at hand, has been addressed in the literature, but not as it occurs among Nigerian entrepreneurs. This study was conducted with the aim of narrowing this gap in knowledge by exploring how Nigerian entrepreneurs have successfully carried out their businesses. The research question addressed how Nigerian entrepreneurs overcame critical situations to successfully address the challenges of scaling and creating public value, and whether the theory of entrepreneurial bricolage can support their actions. A qualitative descriptive single case study with a purposeful sample of 22 interview respondents was employed. A total of 145 critical incidents were analyzed by fitting them into themes constructed a priori from the known behavioral patterns that emerged through the theoretical taxonomy of the concept of entrepreneurial bricolage. The results showed that Nigerian entrepreneurs made do with the resources at hand, improvised, and invoked stakeholder participation and persuasion to solve critical challenges of business continuity. The outcome of the research should help potential entrepreneurs determine strategies to scale their ideas or innovations to achieve positive social change. The results may be useful to any fledgling entrepreneur who needs encouragement when feeling overwhelmed by the challenges of doing business in Nigeria. Budding entrepreneurs can learn from the experiences of those who are deemed successful in their businesses, thereby avoiding challenges when they can and strategizing for those challenges that are unavoidable.

Electricity is the most preferred source of energy, because of its quality and convenience of usage. It is probably one of the most vital infrastructural inputs for economic development of a country. Indeed it is the fulcrum which can leverage the future pace of growth and development. These reasons have made the electric power industry one of the fastest growing sectors in most developing countries and particularly in India. Therefore it is not surprising to observe the economic growth of a country being related to the increase in electricity consumption. In India, the growth rate of demand for power is generally higher than that of Gross Domestic Product (GDP). However, to achieve this kind of growth in electricity supply, the capital investments required are very huge. Even though the electricity sector generally gels a major share in the budgetary allocations in India, this is inadequate to add the required quantum of new generation capacity to keep pace with the increase in demand for electricity. Additional constraints like capital scarcity in the public sector, lack of enthusiasm among the private and foreign investors, and strong opposition from the environmentalists have further contributed to this slow pace of new generating capacity addition. This has resulted in severely constrained systems in India. The main focus of the present research work is on the development of an integrated approach for electricity planning using a mathematical modeling framework in (he context of resource constrained systems. There are very few attempts in the literature to integrate short, medium and long term issues in electricity planning. This is understandable from the point of view of unconstrained electricity systems where this type of integration is unnecessary since such systems have a luxury of surplus capacity to meet the current demand and capacity additions are required only for meeting predicted future increase in demand. However, in the case of constrained electricity systems, which are characterized by shortages, this kind of integration is very essential. These systems have to manage with inadequate capacity in the present, plan capacity additions to bridge the existing gap and to meet future increase in demand, and always explore the possibility of adding capacity with short gestation period. The integrated approach is expected to achieve effective supply-demand matching on a continuous basis encompassing both the short term and long term horizons. To achieve this, we have considered three alternatives- existing supply, new supply and non-supply (rationing) of electricity. The electricity system of the state of Karnataka, which is severely constrained by both limited capital and energy resources, has been selected for this purpose. As a first step, the supply and demand situation has been studied in the context of resource constraints. In terms of supply, both existing and future additions are studied in detail with respect to the potential created, generation types, import potential, technical constraints, energy and power shortages, planned and proposed capacity additions by both public and private sectors, etc. The demand patterns have been studied by introducing a new concept of "Representative Load Curves (RLCs)". These RLCs are used to model the temporal and structural variations in demand for electricity. Also, appropriate non-supply options (rationing measures) for effective management of shortages are identified. Incorporating this information, an integrated mathematical model, which is expected to generate a target plan for a detailed generation scheduling exercises and a requirement plan for a regular generation expansion planning, has been developed. The other important alternative "Demand-Side-Management (DSM)", which could be considered as an effective option to achieve efficient supply-demand matching has not been included in the present research work. The major reason for not including the DSM alternatives is due to the difficulty in integrating these in the modelling approach adopted here. In the present approach we have used typical daily load curves (RLCs) to represent the demand for electricity. These are aggregate load curves and do not contain any sector-wise or end-use-wisc details. On the other hand, DSM alternatives are end-use focused. To incorporate DSM alternatives, we should have information on end-usc-wisc power demand (kW or MW), savings potential, time-of-use, etc. For this purpose it may be required to have end-use-wisc daily load curves. This information is not available and a separate detailed survey may be required to generate these load curves. This, we felt, is out of the scope of this present research work and a separate study may be required to do this. Therefore, we restricted our focus to supply planning alone. A detailed literature review is conducted to understand different types of modeling approaches to electricity planning. For the present study, however, the review of literature has been restricted to the methods of generation expansion planning and scheduling. In doing so, we attempted to bring out the differences in various approaches in terms of solution methods adopted, alternatives included and modifications suggested. Also, we briefly reviewed the literature on models for power and energy rationing, because management of shortages is an important aspect of the present study. Subsequently, a separate section is devoted to present an overview of the non-supply of electricity and its economic impacts on the consumers. We found that the low reliability of the electrical system is an indicator of the existence of severe shortages of power and energy, which cause non-supply of electricity to the consumers. The overview also presented a discussion on reasons for non-supply of electricity, and the types of non-supply options the utilities adopt to over come these shortages. We also attempted to explain what we mean by non-supply of electricity, what are its cost implications, and the methods available in the literature to estimate these costs. The first objective of the research pertains to the development of a new approach to model the varying demand for electricity. Using the concept of Representative Load Curves (RLCs) we model the hourly demand for a period of four years, 1993-94, 1994-95, 1995-96 and 1996-97, to understand the demand patterns of both unconstrained and constrained years. Multiple discriminant analysis has been used to cluster the 365 load curves into nine RLCs for each of the four years. The results show that these RLCs adequately model the variations in demand and bring out the distinctions in the demand patterns existed during the unconstrained and constrained years. The demand analysis using RLCs helped to study the differences in demand patterns with and without constraints, impacts of constraints on preferred pattern of electricity consumption, success of non-supply options in both reducing the demand levels and greatly disturbing the electricity usage patterns. Multifactor ANOVA analyses are performed to quantify the statistical significance of the ability of the logically obtained factors in explaining the overall variations in demand. The results of the ANOVA analysis clearly showed that the considered factors accounted for maximum variations in demand at very high significance levels. It also brought out the significant influence of rationing measures in explaining the variations in demand during the constrained years. Concerning the second objective, we explained in detail, the development of an integrated mixed integer-programming model, which we felt is appropriate for planning in the case of resource constrained electricity systems. Two types of integrations are attempted (i) existing supply, non-supply and new supply options for dynamically matching supply and demand, (ii) operational and strategic planning in terms of providing target plans for the former and requirement plans for the latter. Broadly, the approach addresses the effective management of existing capacity, optimal rationing plan to effectively manage shortages and rationally decide on the new capacity additions both to bridge the existing gap between supply and demand, and to meet the future increases in demand. There is also an attempt to arrive at an optimal mix of public and private capacity additions for a given situation. Finally, it has been attempted to verify the possibility of integration of captive generation capacity with the grid. Further, we discussed in detail about the data required for the model implementation. The model is validated through the development of a number of scenarios for the state of Karnataka. The base case scenario analyses are carried out for both the unconstrained and constrained years to compare the optimal allocations with actual allocations that were observed, and to find out how sensitive are the results for any change in the values of various parameters. For the constrained years, a few more scenarios are used to compare the optimal practice of managing shortages with to what has been actually followed by the utility. The optimal allocations of the predicted demand to various existing supply and non-supply options clearly showed that the actual practice, reflected by the actual RLCs, are highly ad hoc and sub-optimal. The unit cost comparisons among different scenarios show that the least cost choice of options by the utility does not necessarily lead to good choices from the consumers’ perspective. Further, a number of future scenarios are developed to verify the ability of the model to achieve the overall objective of supply-demand matching both in the short and long term. For this purpose both the short horizon annual scenarios (1997-98 to 2000-01) and long horizon terminal year scenarios (2005-06 and 2010-11) are developed assuming capacity additions from only public sector. Overall, the results indicated that with marginal contributions from non-supply options and if the public sector generates enough resources to add the required capacity, optimal matching of supply and demand could be achieved. The scenario analyses also showed that it is more economical to have some level of planned rationing compared to having a more reliable system. The quantum of new capacity additions required and the level of investments associated with it clearly indicated the urgent need of private sector participation in capacity additions. Finally, we made an attempt to verify the applicability of the integrated model to analyse the implications of private sector participation in capacity additions. First, a number of scenarios are developed to study the optimal allocations of predicted hourly demand to private capacity under different situations. Secondly, the impacts of privatisation on the public utility and consumers are analysed. Both short term and long term scenarios are developed for this purpose. The results showed the advantage of marginal non-supply of electricity both in terms of achieving overall effective supply-demand matching and economic benefits that could be generated through cost savings. The results also showed the negative impacts of high guarantees offered to the private sector in terms of the opportunity costs of reduced utilization of both the existing and new public capacity. The estimates of unit cost of supply and effective cost of supply facilitated the relative comparison among various scenarios as well as finding out the merits and demerits of guarantees to private sector and non-supply of electricity. The unit cost estimates are also found to be useful in studying the relative increase in electricity prices for consumers on account of privatization, guarantees and reliable supply of electricity. Using the results of scenario analyses, likely generation expansion plans till the year 2010-11 are generated. The analyses have been useful in providing insights into fixing the availability and plant load factors for the private sector capacity. Based on the analysis, the recommended range for plant utilization factor is 72.88 - 80.57%. The estimated generation losses and the associated economic impacts of backing down of existing and new public capacity on account of guarantees offered to private sector are found to be significantly high. The analyses also showed that the backing down might take place mainly during nights and low demand periods of monsoon and winter seasons. Other impacts of privatization that studied are in terms of increased number of alternatives for the utility to buy electricity for distribution and the associated increase in its cost of purchase. Regarding the consumers, the major impact could be in terms of significant increase in expected tariffs. The major contributions of this thesis are summarized as follows: i. An integrated approach to electricity planning that is reported here, is unique in the sense that it considers options available under various alternatives, namely, existing supply, non-supply and new supply. This approach is most suited for severely constrained systems having to manage with both energy and capital resource shortages. ii. The integration of operational and strategic planning with coherent target plans for the former and requirement plans for the latter bridges the prevailing gap in electricity planning approaches. iii. The concept of Representative Load Curves (RLCs), which is introduced here, captures the hourly, daily and seasonal variations in demand. Together, all the RLCs developed for a given year are expected to model the hourly demand patterns of that year. These RLCs are useful for planning in resource constrained electricity systems and in situations where it is required to know the time variations in demand (e.g. supply-demand matching, seasonal scheduling of hydro plants and maintenance scheduling). RLCs are also useful in identifying the factors influencing variations in demand. This approach will overcome the limitations of current method of representation in the form of static and aggregate annual load duration curves. iv. A new term, "non-supply of electricity" has been introduced in this thesis. A brief overview of non-supply presented here includes reasons for non-supply, type of non-supply, methods to estimate cost of non-supply and factors influencing these estimates. v. The integrated mixed integer programming model developed in the study has been demonstrated as a planning tool for- • Optimal hourly and seasonal scheduling of various existing supply, non-supply and new supply options • Estimation of supply shortages on a representative hourly basis using the information on resource constraints • Effectively planning non-supply of electricity through appropriate power/energy rationing methods • Estimation of the need for the new capacity additions both to bridge the existing gap and to take care of increase in future demand levels • Optimal filling of gaps between demand and supply on a representative hourly basis through new supply of electricity • Optimally arriving at the judicious mix of public and private capacity additions • Studying the impacts of private capacity on the existing and new public sector capacity, and on the consumers • Optimally verifying the feasibility of integrating the captive generation with the total system vi. The demand analysis using RLCs helped to bring out the differences in demand patterns with and without constraints, impacts of constraints on preferred pattern of electricity consumption, success of non-supply options in both reducing the demand levels and greatly disturbing the electricity usage patterns. Multifactor ANOVA analyses results showed that the logically obtained factors accounted for maximum variations in demand at very high significance levels. vii. A comparison of optimal (represented by optimal predicted RLCs) and actual (reflected by actual RLCs) practices facilitated by the model showed that the actual practice during constrained years is highly ad hoc and sub-optimal. viii. The results of the scenario analyses showed that it is more economical to have some amount of planned rationing compared to having a more reliable system, which does not allow non-supply of electricity. ix. The scenarios, which analysed the impacts of high guarantees offered to the private sector, showed the negative impacts of these in terms of reduced utilization of both the existing and new public capacity. x. Generation expansion plans till the year 2010-11 are developed using the results of various kinds of scenario analyses. Two groups of year-wise generation expansion plans are generated, one with only public sector capacity additions and the other with private sector participation. xi. The impacts of privatization of capacity additions are studied from the point of view of the utility and consumers in terms of expected increase in cost of purchase of electricity and tariffs. xii. The analyses are also made for developing some insights into fixing the availability and plant load factors for the private capacity. Based on the analysis, the recommended range for plant utilization factor is 72.88 - 80.57%. We believe that the integrated approach presented and the results obtained in this thesis would help utilities (both suppliers and distributors of electricity) and governments in making rational choices in the context of resource constrained systems. The results reported here may also be used towards rationalization of Government policies vis-a-vis tariff structures in the supply of electricity, planning new generation capacity additions and effective rationing of electricity. It is also hoped that the fresh approach adopted in this thesis would attract further investigations in future research on resource constrained systems.

No description available.

Non-functional requirements such as Security and Dependability (S&D) become more and more important as well as more and more difficult to achieve, particularly in embedded systems development. Such systems come with a large number of common characteristics, including real-time and temperature constraints, security and dependability as well as efficiency requirements. In particular, the development of Resource Constrained Embedded Systems (RCES) has to address constraints regarding memory, computational processing power and/or energy consumption. In this work, we propose a modeling environment which associates model-driven paradigm and a model-based repository, to support the design and the packaging of S&D patterns, resource models and their property models. The approach is based on a set of modeling languages coupled with a model-repository, search and instantiation engines towards specific development environments. These modeling languages allow to specify patterns, resources and a set of property models. These property models will allow to govern the use of patterns and their analysis for reuse. In addition, we propose a specification and generation process of repositories. As part of the assistance for the development of S&D applications, we have implemented a suite of tool-chain based on the Eclipse platform to support the different activities around the repository, including the analysis activities. The proposed solutions were evaluated in the TERESA project through a case study from the railway domain.