This dissertation discusses two independent topics: a resource-constrained shortest-path problem (RCSP) and a literature review on scheduling problems involving sequence-dependent setup (SDS) times (costs). RCSP is often used as a subproblem in column generation because it can be used to solve many practical problems. This dissertation studies RCSP with multiple resource constraints on an acyclic graph, because many applications involve this configuration, especially in column genetation formulations. In particular, this research focuses on a dynamic RCSP since, as a subproblem in column generation, objective function coefficients are updated using new values of dual variables at each iteration. This dissertation proposes a pseudo-polynomial solution method for solving the dynamic RCSP by exploiting the special structure of an acyclic graph with the goal of effectively reoptimizing RCSP in the context of column generation. This method uses a one-time “preliminary” phase to transform RCSP into an unconstrained shortest path problem (SPP) and then solves the resulting SPP after new values of dual variables are used to update objective function coefficients (i.e., reduced costs) at each iteration. Network reduction techniques are considered to remove some nodes and/or arcs permanently in the preliminary phase. Specified techniques are explored to reoptimize when only several coefficients change and for dealing with forbidden and prescribed arcs in the context of a column generation/branch-and-bound approach. As a benchmark method, a label-setting algorithm is also proposed. Computational tests are designed to show the effectiveness of the proposed algorithms and procedures. This dissertation also gives a literature review related to the class of scheduling problems that involve SDS times (costs), an important consideration in many practical applications. It focuses on papers published within the last decade, addressing a variety of machine configurations - single machine, parallel machine, flow shop, and job shop - reviewing both optimizing and heuristic solution methods in each category. Since lot-sizing is so intimately related to scheduling, this dissertation reviews work that integrates these issues in relationship to each configuration. This dissertation provides a perspective of this line of research, gives conclusions, and discusses fertile research opportunities posed by this class of scheduling problems. since, as a subproblem in column generation, objective function coefficients are updated using new values of dual variables at each iteration. This dissertation proposes a pseudo-polynomial solution method for solving the dynamic RCSP by exploiting the special structure of an acyclic graph with the goal of effectively reoptimizing RCSP in the context of column generation. This method uses a one-time

abstract: In contemporary society, sustainability and public well-being have been pressing challenges. Some of the important questions are:how can sustainable practices, such as reducing carbon emission, be encouraged? , How can a healthy lifestyle be maintained?Even though individuals are interested, they are unable to adopt these behaviors due to resource constraints. Developing a framework to enable cooperative behavior adoption and to sustain it for a long period of time is a major challenge. As a part of developing this framework, I am focusing on methods to understand behavior diffusion over time. Facilitating behavior diffusion with resource constraints in a large population is qualitatively different from promoting cooperation in small groups. Previous work in social sciences has derived conditions for sustainable cooperative behavior in small homogeneous groups. However, how groups of individuals having resource constraint co-operate over extended periods of time is not well understood, and is the focus of my thesis. I develop models to analyze behavior diffusion over time through the lens of epidemic models with the condition that individuals have resource constraint. I introduce an epidemic model SVRS ( Susceptible-Volatile-Recovered-Susceptible) to accommodate multiple behavior adoption. I investigate the longitudinal effects of behavior diffusion by varying different properties of an individual such as resources,threshold and cost of behavior adoption. I also consider how behavior adoption of an individual varies with her knowledge of global adoption. I evaluate my models on several synthetic topologies like complete regular graph, preferential attachment and small-world and make some interesting observations. Periodic injection of early adopters can help in boosting the spread of behaviors and sustain it for a longer period of time. Also, behavior propagation for the classical epidemic model SIRS (Susceptible-Infected-Recovered-Susceptible) does not continue for an infinite period of time as per conventional wisdom. One interesting future direction is to investigate how behavior adoption is affected when number of individuals in a network changes. The affects on behavior adoption when availability of behavior changes with time can also be examined. / Dissertation/Thesis / M.S. Computer Science 2013

<div><div>The blockchain offers a decentralized way to provide security guarantees for financial transactions. However, this ability comes with the cost of storing a large (distributed) blockchain state and introducing additional computation and communication overhead to all participants. All these drawbacks raise a challenging scalability problem, especially for resource-constrained blockchain clients. On the other hand, some scaling solutions typically require resource-constrained clients to rely on other nodes with higher computational and storage capabilities. However, such scaling solutions often expose the data of the clients to risks of compromise of the more powerful nodes they rely on (e.g., accidental, malicious through a break-in, insider misbehavior, or malware infestation). This potential for leakage raises a privacy concern for these constrained clients, in addition to other scaling-related concerns. This dissertation proposes several cryptographic constructions and system designs enabling resource-constrained devices to participate in the blockchain network securely and efficiently. </div><div><br></div><div>Our first proposal concerns the storage facet for which we propose two add-on privacy designs to address the scaling issue of storing a large blockchain state. </div><div>The first solution is an oblivious database framework, called T³, that allows resource-constrained clients to obliviously fetch blockchain data from potential malicious full clients. The second solution focuses on the problem of using and storing additional private-by-design blockchains (e.g., Monero or ZCash) to achieve privacy. We propose an add-on tumbler design, called AMR, that offers privacy directly to clients of non-private blockchains such as Ethereum without the cost of storing and using different blockchain states.</div><div><br></div><div>Our second proposal addresses the communication facet with focus on payment channels as a solution to address the communication overhead between the constrained clients and the blockchain network. A payment channel enables transactions between arbitrary pairs of constrained clients with a minimal communication overhead with the blockchain network. However, in popular blockchains like Ethereum and Bitcoin, the payment data of such channels are exposed to the public, which is undesirable for financial applications. Thus, to hide transaction data, one can use blockchains that are private by design like Monero. However, existing cryptographic primitives in Monero prevent the system from supporting any form of payment channels. Therefore, we present <i>Dual Linkable Spontaneous Anonymous Group Signature for Ad Hoc Groups (DLSAG),</i> a linkable ring signature scheme that enables, for the first time, off-chain scalability solutions in Monero. </div><div><br></div><div>To address the computation facet, we address the computation overhead of the gossip protocol used in all popular blockchain protocols. For this purpose, we propose a signature primitive called <i>Flexible Signature</i>. In a flexible signature scheme, the verification algorithm quantifies the validity of a signature based on the computational effort performed by the verifier. Thus, the resource-constrained devices can partially verify the signatures in the blockchain transactions before relaying transactions to other peers. This primitive allows the resource-constrained devices to prevent spam transactions from flooding the blockchain network with overhead that is consistent with their resource constraints. </div></div>

A broader research project was conducted about intergenerational relationships. The focus of this study was about adolescents’ experiences of care in relationships with people older than 60 years, who live in an environment where resources are constrained. Care usually occurs in relationships and can take either the form of practical care or emotional care, or both which can occur simultaneously. Practical care involves behaviours, while emotional care involves feelings. Both are aimed at attending to other people’s needs. Previous studies on intergenerational relationships and care largely focused on either informal and practical care-giving, which are mainly provided by adult children to older people; or on the informal and practical care-giving provided by grandparents to grandchildren. Research on relational experiences between Setswana-speaking older people and young adults in South Africa has indicated ambivalence in their relationships. While another South African study on the relational experiences between Setswana-speaking older people and their grandchildren, who are in their middle childhood, reported supportive and caring relationships. Limited research exists about care in the relationships between adolescents and older people. Care as a relational phenomenon in intergenerational relationships is explained by the Self-Interactional Group Theory (SIGT), and is used in this study as the theoretical framework. SIGT explains the interactional manifestation of intergenerational relations, and conceptualises that intergenerational relationships are continuously created and co-created, which influences the meaning that is attached to care. This theory further explains the intra-individual, inter-individual and group level interactions that take place between the adolescents and older people. According to SIGT, intergenerational interactions are embedded in the socio-cultural, socio-economical, socio-political and the physical environments in which they take place. This study was conducted in Vaalharts, situated in the Northern Cape Province of South Africa. This community is economically vulnerable and resources are constrained. A qualitative research method was used to describe adolescents’ experiences of care. Fourteen adolescents between the ages of 12 and 16 years participated in the research. Non-probability, purposive sampling was used to select the participants. The participants took part in the Mmogo-method ®, which is a visual participatory data gathering method, to elicit the experiences of care. Eight of the participants were part of the care-group, while the other six were part of the respect-group. All 14 participants received a journal with questions about care and respect to enlighten the data further. For this study, only the data about care was used. The Mmogo-method ® required the participants to build a visual presentation using clay, beads and sticks, about their experiences of care in relation to people older than 60 years. On completion, the rest of the participants were then asked to augment the individual’s explanation with their own views. The explanations were recorded and transcribed verbatim, while the visual representations were photographed and served as visual data. The data were analysed by the use of thematic and visual analysis. Trustworthiness was ensured by the use of credibility, dependability, transferability and conformability strategies. Additionally, the ethical guidelines provided by the Health Professions Council of South Africa for Psychologists were followed (Health Professions Act 56 of 1974). It was found that the adolescents were able to identify older people’s practical care and emotional care needs, and take action to provide them with appropriate care. The adolescents showed care in the form of practical activities, emotional support, showing respect, and obtaining an education. Findings further indicated that adolescents received care only in the form of practical care. These findings may be an indication that, from the adolescents’ perspective, there is an imbalance between the giving and receiving of practical and emotional care. Intervention programs can then focus on ways to help ensure that both practical and emotional care occurs in a more balanced manner. / MSc (Research Psychology), North-West University, Potchefstroom Campus, 2015

A broader research project was conducted about intergenerational relationships. The focus of this study was about adolescents’ experiences of care in relationships with people older than 60 years, who live in an environment where resources are constrained. Care usually occurs in relationships and can take either the form of practical care or emotional care, or both which can occur simultaneously. Practical care involves behaviours, while emotional care involves feelings. Both are aimed at attending to other people’s needs. Previous studies on intergenerational relationships and care largely focused on either informal and practical care-giving, which are mainly provided by adult children to older people; or on the informal and practical care-giving provided by grandparents to grandchildren. Research on relational experiences between Setswana-speaking older people and young adults in South Africa has indicated ambivalence in their relationships. While another South African study on the relational experiences between Setswana-speaking older people and their grandchildren, who are in their middle childhood, reported supportive and caring relationships. Limited research exists about care in the relationships between adolescents and older people. Care as a relational phenomenon in intergenerational relationships is explained by the Self-Interactional Group Theory (SIGT), and is used in this study as the theoretical framework. SIGT explains the interactional manifestation of intergenerational relations, and conceptualises that intergenerational relationships are continuously created and co-created, which influences the meaning that is attached to care. This theory further explains the intra-individual, inter-individual and group level interactions that take place between the adolescents and older people. According to SIGT, intergenerational interactions are embedded in the socio-cultural, socio-economical, socio-political and the physical environments in which they take place. This study was conducted in Vaalharts, situated in the Northern Cape Province of South Africa. This community is economically vulnerable and resources are constrained. A qualitative research method was used to describe adolescents’ experiences of care. Fourteen adolescents between the ages of 12 and 16 years participated in the research. Non-probability, purposive sampling was used to select the participants. The participants took part in the Mmogo-method ®, which is a visual participatory data gathering method, to elicit the experiences of care. Eight of the participants were part of the care-group, while the other six were part of the respect-group. All 14 participants received a journal with questions about care and respect to enlighten the data further. For this study, only the data about care was used. The Mmogo-method ® required the participants to build a visual presentation using clay, beads and sticks, about their experiences of care in relation to people older than 60 years. On completion, the rest of the participants were then asked to augment the individual’s explanation with their own views. The explanations were recorded and transcribed verbatim, while the visual representations were photographed and served as visual data. The data were analysed by the use of thematic and visual analysis. Trustworthiness was ensured by the use of credibility, dependability, transferability and conformability strategies. Additionally, the ethical guidelines provided by the Health Professions Council of South Africa for Psychologists were followed (Health Professions Act 56 of 1974). It was found that the adolescents were able to identify older people’s practical care and emotional care needs, and take action to provide them with appropriate care. The adolescents showed care in the form of practical activities, emotional support, showing respect, and obtaining an education. Findings further indicated that adolescents received care only in the form of practical care. These findings may be an indication that, from the adolescents’ perspective, there is an imbalance between the giving and receiving of practical and emotional care. Intervention programs can then focus on ways to help ensure that both practical and emotional care occurs in a more balanced manner. / MSc (Research Psychology), North-West University, Potchefstroom Campus, 2015

A flexible workforce or a versatile machine is employed to perform various types of operations. Often these resources are associated with setups. Whenever a worker or machine switches from processing one type of operation to another a setup time may be required although several operations of a same type can be processed in succession after a single setup. The presence of setups gives rise to the problem of choosing batch sizes that are neither too large nor too small. In the last one and a half decade, many researchers have addressed the problem of scheduling with batching. A majority of articles assumes that there is only one type of scarce resource, which is typically machine. Often there can be two scarce resources such as a worker and a machine or a machine and a tool. We propose a resource constrained scheduling model with a single operator and two or more machines. Whenever the operator changes machine, a setup time is required that may be sequence dependent or sequence independent. We consider the two cases of an open shop and a flow shop. In the open shop case, the order in which a job visits the machines is unrestricted. In the flow shop case, every job must visit the machines in the same order. We consider various scheduling objectives. For variable number of machines, many cases are intractable. We discuss some dominance properties that narrow down the search for an optimal schedule. We present a dynamic programming approach which solves a large number of cases. The running time of the dynamic program is polynomial for a fixed number of machines. For the case of two machines, we show that the dominance properties have a nice interpretation. We develop some algorithms and justify their use by establishing running times, comparing the running times with those of the existing algorithms, and testing the performance of the algorithms.

The main goal of a scheduling process is to decide when and how to execute each of the project's activities. Despite large variety of researched scheduling problems, the majority of them can be described as generalisations of the resource-constrained project scheduling problem (RCPSP). Because of wide applicability and challenging difficulty, RCPSP has attracted vast amount of attention in the research community and great variety of heuristics have been adapted for solving it. Even though these heuristics are structurally different and operate according to diverse principles, they are designed to obtain only one solution at a time. In the recent researches on RCPSPs, it was proven that these kind of problems have complex multimodal fitness landscapes, which are characterised by a wide solution search spaces and presence of multiple local and global optima. The main goal of this thesis is twofold. Firstly, it presents a variation of the RCPSP that considers optimisation of projects in an uncertain environment where resources are modelled to adapt to their environment and, as the result of this, improve their efficiency. Secondly, modification of a novel evolutionary computation method Cuckoo Search (CS) is proposed, which has been adapted for solving combinatorial optimisation problems and modified to obtain multiple solutions. To test the proposed methodology, two sets of experiments are carried out. Firstly, the developed algorithm is applied to a real-life software development project. Secondly, the performance of the algorithm is tested on universal benchmark instances for scheduling problems which were modified to take into account specifics of the proposed optimisation model. The results of both experiments demonstrate that the proposed methodology achieves competitive level of performance and is capable of finding multiple global solutions, as well as prove its applicability in real-life projects.

Lithium is a highly interesting metal, in part due to the increasing interest in lithium-ion batteries. Several recent studies have used different methods to estimate whether the lithium production can meet an increasing demand, especially from the transport sector, where lithium-ion batteries are the most likely technology for electric cars. The reserve and resource estimates of lithium vary greatly between different studies and the question whether the annual production rates of lithium can meet a growing demand is seldom adequately explained. This study presents a review and compilation of recent estimates of quantities of lithium available for exploitation and discusses the uncertainty and differences between these estimates. Also, mathematical curve fitting models are used to estimate possible future annual production rates. This estimation of possible production rates are compared to a potential increased demand of lithium if the International Energy Agency’s Blue Map Scenarios are fulfilled regarding electrification of the car fleet. We find that the availability of lithium could in fact be a problem for fulfilling this scenario if lithium-ion batteries are to be used. This indicates that other battery technologies might have to be implemented for enabling an electrification of road transports. / Stand

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.

As the next evolutionary step in digital communication systems, mobile ad hoc networks (MANETs) and their specialization like wireless sensor networks (WSNs) have been attracting much interest in both research and industry communities. In MANETs, network nodes can come together and form a network without depending on any pre-existing infrastructure and human intervention. Unfortunately, the salient characteristics of MANETs, in particular the absence of infrastructure and the constrained resources of mobile devices, present enormous challenges when designing security mechanisms in this environment. Without necessary measures, wireless communications are easy to be intercepted and activities of users can be easily traced. This thesis presents our solutions for two important aspects of securing MANETs, namely efficient key management protocols and fast implementations of cryptographic primitives on constrained devices. Due to the tight cost and constrained resources of high-volume mobile devices used in MANETs, it is desirable to employ lightweight and specialized cryptographic primitives for many security applications. Motivated by the design of the well-known Enigma machine, we present a novel ultra-lightweight cryptographic algorithm, referred to as Hummingbird, for resource-constrained devices. Hummingbird can provide the designed security with small block size and is resistant to the most common attacks such as linear and differential cryptanalysis. Furthermore, we also present efficient software implementations of Hummingbird on 4-, 8- and 16-bit microcontrollers from Atmel and Texas Instruments as well as efficient hardware implementations on the low-cost field programmable gate arrays (FPGAs) from Xilinx, respectively. Our experimental results show that after a system initialization phase Hummingbird can achieve up to 147 and 4.7 times faster throughput for a size-optimized and a speed-optimized software implementation, respectively, when compared to the state-of-the-art ultra-lightweight block cipher PRESENT on the similar platforms. In addition, the speed optimized Hummingbird encryption core can achieve a throughput of 160.4 Mbps and the area optimized encryption core only occupies 253 slices on a Spartan-3 XC3S200 FPGA device. Bilinear pairings on the Jacobians of (hyper-)elliptic curves have received considerable attention as a building block for constructing cryptographic schemes in MANETs with new and novel properties. Motivated by the work of Scott, we investigate how to use efficiently computable automorphisms to speed up pairing computations on two families of non-supersingular genus 2 hyperelliptic curves over prime fields. Our findings lead to new variants of Miller's algorithm in which the length of the main loop can be up to 4 times shorter than that of the original Miller's algorithm in the best case. We also generalize Chatterjee et al.'s idea of encapsulating the computation of the line function with the group operations to genus 2 hyperelliptic curves, and derive new explicit formulae for the group operations in projective and new coordinates in the context of pairing computations. Efficient software implementation of computing the Tate pairing on both a supersingular and a non-supersingular genus 2 curve with the same embedding degree of k = 4 is investigated. Combining the new algorithm with known optimization techniques, we show that pairing computations on non-supersingular genus 2 curves over prime fields use up to 55.8% fewer field operations and run about 10% faster than supersingular genus 2 curves for the same security level. As an important part of a key management mechanism, efficient key revocation protocol, which revokes the cryptographic keys of malicious nodes and isolates them from the network, is crucial for the security and robustness of MANETs. We propose a novel self-organized key revocation scheme for MANETs based on the Dirichlet multinomial model and identity-based cryptography. Firmly rooted in statistics, our key revocation scheme provides a theoretically sound basis for nodes analyzing and predicting peers' behavior based on their own observations and other nodes' reports. Considering the difference of malicious behaviors, we proposed to classify the nodes' behavior into three categories, namely good behavior, suspicious behavior and malicious behavior. Each node in the network keeps track of three categories of behavior and updates its knowledge about other nodes' behavior with 3-dimension Dirichlet distribution. Based on its own analysis, each node is able to protect itself from malicious attacks by either revoking the keys of the nodes with malicious behavior or ceasing the communication with the nodes showing suspicious behavior for some time. The attack-resistant properties of the resulting scheme against false accusation attacks launched by independent and collusive adversaries are also analyzed through extensive simulations. In WSNs, broadcast authentication is a crucial security mechanism that allows a multitude of legitimate users to join in and disseminate messages into the networks in a dynamic and authenticated way. During the past few years, several public-key based multi-user broadcast authentication schemes have been proposed in the literature to achieve immediate authentication and to address the security vulnerability intrinsic to μTESLA-like schemes. Unfortunately, the relatively slow signature verification in signature-based broadcast authentication has also incurred a series of problems such as high energy consumption and long verification delay. We propose an efficient technique to accelerate the signature verification in WSNs through the cooperation among sensor nodes. By allowing some sensor nodes to release the intermediate computation results to their neighbors during the signature verification, a large number of sensor nodes can accelerate their signature verification process significantly. When applying our faster signature verification technique to the broadcast authentication in a 4×4 grid-based WSN, a quantitative performance analysis shows that our scheme needs 17.7%~34.5% less energy and runs about 50% faster than the traditional signature verification method.