A genetic algorithm for the resource constrained multi-project scheduling problem

This paper presents a genetic algorithm for the resource constrained multi-project scheduling problem. The chromosome representation of the problem is based on random keys. The schedules are constructed using a heuristic that builds parameterized active schedules based on priorities, delay times, and release dates defined by the genetic algorithm. The approach is tested on a set of randomly generated problems. The computational results validate the effectiveness of the proposed algorithm.

Analysis of the domain of applicability of an algorithm for a resources system selection problem for Distributed/Agile/Virtual Enterprises integration

The process of resources systems selection takes an important part in Distributed/Agile/Virtual Enterprises (D/A/V Es) integration. However, the resources systems selection is still a difficult matter to solve in a D/A/VE, as it is pointed out in this paper. Globally, we can say that the selection problem has been equated from different aspects, originating different kinds of models/algorithms to solve it. In order to assist the development of a web prototype tool (broker tool), intelligent and flexible, that integrates all the selection model activities and tools, and with the capacity to adequate to each D/A/V E project or instance (this is the major goal of our final project), we intend in this paper to show: a formulation of a kind of resources selection problem and the limitations of the algorithms proposed to solve it. We formulate a particular case of the problem as an integer programming, which is solved using simplex and branch and bound algorithms, and identify their performance limitations (in terms of processing time) based on simulation results. These limitations depend on the number of processing tasks and on the number of pre-selected resources per processing tasks, defining the domain of applicability of the algorithms for the problem studied. The limitations detected open the necessity of the application of other kind of algorithms (approximate solution algorithms) outside the domain of applicability founded for the algorithms simulated. However, for a broker tool it is very important the knowledge of algorithms limitations, in order to, based on problem features, develop and select the most suitable algorithm that guarantees a good performance.

Adaptive tackling of the swinging problem for a 2 DOF crane – payload system

The control of a crane carrying its payload by an elastic string corresponds to a task in which precise, indirect control of a subsystem dynamically coupled to a directly controllable subsystem is needed. This task is interesting since the coupled degree of freedom has little damping and it is apt to keep swinging accordingly. The traditional approaches apply the input shaping technology to assist the human operator responsible for the manipulation task. In the present paper a novel adaptive approach applying fixed point transformations based iterations having local basin of attraction is proposed to simultaneously tackle the problems originating from the imprecise dynamic model available for the system to be controlled and the swinging problem, too. The most important phenomenological properties of this approach are also discussed. The control considers the 4th time-derivative of the trajectory of the payload. The operation of the proposed control is illustrated via simulation results.

A biased random-key genetic algorithm with forward-backward improvement for the resource constrained project scheduling problem

This paper presents a biased random-key genetic algorithm for the resource constrained project scheduling problem. The chromosome representation of the problem is based on random keys. Active schedules are constructed using a priority-rule heuristic in which the priorities of the activities are defined by the genetic algorithm. A forward-backward improvement procedure is applied to all solutions. The chromosomes supplied by the genetic algorithm are adjusted to reflect the solutions obtained by the improvement procedure. The heuristic is tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

A two-level genetic algorithm for the multi-mode resource-constrained project scheduling problem

This paper presents a genetic algorithm for the multimode resource-constrained project scheduling problem (MRCPSP), in which multiple execution modes are available for each of the activities of the project. The objective function is the minimization of the construction project completion time. To solve the problem, is applied a two-level genetic algorithm, which makes use of two separate levels and extend the parameterized schedule generation scheme by introducing an improvement procedure. It is evaluated the quality of the schedule and present detailed comparative computational results for the MRCPSP, which reveal that this approach is a competitive algorithm.

Reverse problem-based learning - a case study with a Braille machine

Engineering Education includes not only teaching theoretical fundamental concepts but also its verification during practical lessons in laboratories. The usual strategies to carry out this action are frequently based on Problem Based Learning, starting from a given state and proceeding forward to a target state. The possibility or the effectiveness of this procedure depends on previous states and if the present state was caused or resulted from earlier ones. This often happens in engineering education when the achieved results do not match the desired ones, e.g. when programming code is being developed or when the cause of the wrong behavior of an electronic circuit is being identified. It is thus important to also prepare students to proceed in the reverse way, i.e. given a start state generate the explanation or even the principles that underlie it. Later on, this sort of skills will be important. For instance, to a doctor making a patient?s story or to an engineer discovering the source of a malfunction. This learning methodology presents pedagogical advantages besides the enhanced preparation of students to their future work. The work presented on his document describes an automation project developed by a group of students in an engineering polytechnic school laboratory. The main objective was to improve the performance of a Braille machine. However, in a scenario of Reverse Problem-Based learning, students had first to discover and characterize the entire machine's function before being allowed (and being able) to propose a solution for the existing problem.

A random key based genetic algorithm for the resource constrained project scheduling problem

This paper presents a genetic algorithm for the Resource Constrained Project Scheduling Problem (RCPSP). The chromosome representation of the problem is based on random keys. The schedule is constructed using a heuristic priority rule in which the priorities of the activities are defined by the genetic algorithm. The heuristic generates parameterized active schedules. The approach was tested on a set of standard problems taken from the literature and compared with other approaches. The computational results validate the effectiveness of the proposed algorithm.

An optimization approach for the job shop scheduling problem

This paper presents an optimization approach for the job shop scheduling problem (JSSP). The JSSP is a difficult problem in combinatorial optimization for which extensive investigation has been devoted to the development of efficient algorithms. The proposed approach is based on a genetic algorithm technique. The scheduling rules such as SPT and MWKR are integrated into the process of genetic evolution. The chromosome representation of the problem is based on random keys. The schedules are constructed using a priority rule in which the priorities and delay times of the operations are defined by the genetic algorithm. Schedules are constructed using a procedure that generates parameterized active schedules. After a schedule is obtained a local search heuristic is applied to improve the solution. The approach is tested on a set of standard instances taken from the literature and compared with other approaches. The computation results validate the effectiveness of the proposed approach.

A physical packing sequence algorithm for the container loading problem with static mechanical equilibrium conditions

The container loading problem (CLP) is a combinatorial optimization problem for the spatial arrangement of cargo inside containers so as to maximize the usage of space. The algorithms for this problem are of limited practical applicability if real-world constraints are not considered, one of the most important of which is deemed to be stability. This paper addresses static stability, as opposed to dynamic stability, looking at the stability of the cargo during container loading. This paper proposes two algorithms. The first is a static stability algorithm based on static mechanical equilibrium conditions that can be used as a stability evaluation function embedded in CLP algorithms (e.g. constructive heuristics, metaheuristics). The second proposed algorithm is a physical packing sequence algorithm that, given a container loading arrangement, generates the actual sequence by which each box is placed inside the container, considering static stability and loading operation efficiency constraints.

P53 and Cancer-Associated Sialylated Glycans Are Surrogate Markers of Cancerization of the Bladder Associated with Schistosoma haematobium Infection

BACKGROUND: Bladder cancer is a significant health problem in rural areas of Africa and the Middle East where Schistosoma haematobium is prevalent, supporting an association between malignant transformation and infection by this blood fluke. Nevertheless, the molecular mechanisms linking these events are poorly understood. Bladder cancers in infected populations are generally diagnosed at a late stage since there is a lack of non-invasive diagnostic tools, hence enforcing the need for early carcinogenesis markers. METHODOLOGY/PRINCIPAL FINDINGS: Forty-three formalin-fixed paraffin-embedded bladder biopsies of S. haematobium-infected patients, consisting of bladder tumours, tumour adjacent mucosa and pre-malignant/malignant urothelial lesions, were screened for bladder cancer biomarkers. These included the oncoprotein p53, the tumour proliferation rate (Ki-67>17%), cell-surface cancer-associated glycan sialyl-Tn (sTn) and sialyl-Lewisa/x (sLea/sLex), involved in immune escape and metastasis. Bladder tumours of non-S. haematobium etiology and normal urothelium were used as controls. S. haematobium-associated benign/pre-malignant lesions present alterations in p53 and sLex that were also found in bladder tumors. Similar results were observed in non-S. haematobium associated tumours, irrespectively of their histological nature, denoting some common molecular pathways. In addition, most benign/pre-malignant lesions also expressed sLea. However, proliferative phenotypes were more prevalent in lesions adjacent to bladder tumors while sLea was characteristic of sole benign/pre-malignant lesions, suggesting it may be a biomarker of early carcionogenesis associated with the parasite. A correlation was observed between the frequency of the biomarkers in the tumor and adjacent mucosa, with the exception of Ki-67. Most S. haematobium eggs embedded in the urothelium were also positive for sLea and sLex. Reinforcing the pathologic nature of the studied biomarkers, none was observed in the healthy urothelium. CONCLUSION/SIGNIFICANCE: This preliminary study suggests that p53 and sialylated glycans are surrogate biomarkers of bladder cancerization associated with S. haematobium, highlighting a missing link between infection and cancer development. Eggs of S. haematobium express sLea and sLex antigens in mimicry of human leukocytes glycosylation, which may play a role in the colonization and disease dissemination. These observations may help the early identification of infected patients at a higher risk of developing bladder cancer and guide the future development of non-invasive diagnostic tests.

An integer programming model for the minimum interval graph completion problem

The minimum interval graph completion problem consists of, given a graph G = ( V, E ), finding a supergraph H = ( V, E ∪ F ) that is an interval graph, while adding the least number of edges |F| . We present an integer programming formulation for solving the minimum interval graph completion problem recurring to a characteri- zation of interval graphs that produces a linear ordering of the maximal cliques of the solution graph.

Using interval graphs in an order processing optimization problem

In this paper we address an order processing optimization problem known as minimization of open stacks (MOSP). We present an integer pro gramming model, based on the existence of a perfect elimination scheme in interval graphs, which finds an optimal sequence for the costumers orders.

Problemas associados à instalação de subestações de energia em malha urbana. Caso de estudo da subestação de parceiros em Leiria

No âmbito do desenvolvimento da dissertação do Mestrado de Engenharia Eletrotécnica – Sistemas Elétricos de Energia, surgiu a oportunidade de participar no desenvolvimento de um projeto integrante numa subestação de energia. O presente caso de estudo tem em vista a resolução de condicionantes na conceção desta subestação, tais como cumprir requisitos estéticos projetando todo o tipo de equipamentos dentro de edifícios, a ventilação das salas de transformação assim como insonorização de todo o ruído produzido de forma a cumprir os limites legais e não perturbar a vizinhança. A presente subestação de energia está situada numa zona urbana da cidade de Leiria, localidade de Parceiros, dando origem ao nome Subestação de Energia de Parceiros. Esta subestação pertence ao cliente Energias de Portugal, conhecida como EDP, e visa o melhoramento da distribuição do serviço eléctrico. As tradicionais subestações de energia, com aparência bastante desenquadrada dos meios urbanos, representam um entrave ao nível da aproximação destes centros de produção energética às zonas urbanas, comprometendo a melhoria da rede elétrica. Desta forma, foi implementada a tecnologia Gas-Insolated Switchgear e permite o enquadramento destes centros energéticos em zonas urbanas, constituindo mais um edifício urbano na zona onde se insere. Esta substitui os convencionais barramentos existentes nos Parques Exteriores de Aparelhagem das subestações e apresenta-se com dimensões muito reduzidas quando comparadas com as estruturas instaladas nestes parques. Dado que esta tecnologia é desenvolvida no sentido de permitir a construção destes centros energéticos em zonas urbanas, podem ser alojadas dentro de edifícios produzindo assim vantagens ao nível estético, não perturbando a paisagem. Dado que os principais equipamentos de funcionamento na subestação de Parceiros, nomeadamente o Transformador de Potência, se encontram instalados num edifício completamente fechado, foram construídas duas salas de ventilação, na parte superior deste edifício, cada uma adjacente a uma sala de transformação. O transformador instalado possui elevadas dimensões, pesando 53000 kg e contendo 11000 kg de óleo que em estado normal de funcionamento circula por quase todo o interior da máquina a elevadas temperaturas, provocando um aquecimento elevado no interior do edifício o que condiciona o bom funcionamento do transformador. Para ultrapassar esta condicionante foi realizado um estudo de um sistema de ventilação capaz de avaliar e controlar os valores térmicos existentes e proceder à circulação de ar, que será movimentado ou bloqueado, recorrendo a um sistema autónomo, mantendo a temperatura ideal nas salas de transformação. Este autómato é o cérebro de toda a cadeia lógica que, mediante as leituras efetuadas irá dar ordens de atuação aos diversos equipamentos. Apesar dos TP estarem protegidos dentro do edifício, estes produzem um maior ruído. A necessidade da existência do referido sistema de ventilação das divisões de funcionamento destas máquinas, implica a utilização de aparelhos que, apesar da sua evolução tecnológica os torna cada vez menos ruidosos, mas geram sempre alguma perturbação, o que pode representar um problema no cumprimento do regulamento geral do ruído.

Dynamic stability metrics for the container loading problem

The Container Loading Problem (CLP) literature has traditionally evaluated the dynamic stability of cargo by applying two metrics to box arrangements: the mean number of boxes supporting the items excluding those placed directly on the floor (M1) and the percentage of boxes with insufficient lateral support (M2). However, these metrics, that aim to be proxies for cargo stability during transportation, fail to translate real-world cargo conditions of dynamic stability. In this paper two new performance indicators are proposed to evaluate the dynamic stability of cargo arrangements: the number of fallen boxes (NFB) and the number of boxes within the Damage Boundary Curve fragility test (NB_DBC). Using 1500 solutions for well-known problem instances found in the literature, these new performance indicators are evaluated using a physics simulation tool (StableCargo), replacing the real-world transportation by a truck with a simulation of the dynamic behaviour of container loading arrangements. Two new dynamic stability metrics that can be integrated within any container loading algorithm are also proposed. The metrics are analytical models of the proposed stability performance indicators, computed by multiple linear regression. Pearson’s r correlation coefficient was used as an evaluation parameter for the performance of the models. The extensive computational results show that the proposed metrics are better proxies for dynamic stability in the CLP than the previous widely used metrics.