Heuristic algorithm for computing reversal distance with multigene families via binary integer programming

Hannenhalli and Pevzner developed the first polynomial-time algorithm for the combinatorial problem of sorting of signed genomic data. Their algorithm solves the minimum number of reversals required for rearranging a genome to another when gene duplication is nonexisting. In this paper, we show how to extend the Hannenhalli-Pevzner approach to genomes with multigene families. We propose a new heuristic algorithm to compute the reversal distance between two genomes with multigene families via the concept of binary integer programming without removing gene duplicates. The experimental results on simulated and real biological data demonstrate that the proposed algorithm is able to find the reversal distance accurately. ©2005 IEEE

Sviluppo e Applicazione di Metodologie per l'Ottimizzazione di Sistemi Energetici

La riduzione dei consumi di combustibili fossili e lo sviluppo di tecnologie per il risparmio energetico sono una questione di centrale importanza sia per l’industria che per la ricerca, a causa dei drastici effetti che le emissioni di inquinanti antropogenici stanno avendo sull’ambiente. Mentre un crescente numero di normative e regolamenti vengono emessi per far fronte a questi problemi, la necessità di sviluppare tecnologie a basse emissioni sta guidando la ricerca in numerosi settori industriali. Nonostante la realizzazione di fonti energetiche rinnovabili sia vista come la soluzione più promettente nel lungo periodo, un’efficace e completa integrazione di tali tecnologie risulta ad oggi impraticabile, a causa sia di vincoli tecnici che della vastità della quota di energia prodotta, attualmente soddisfatta da fonti fossili, che le tecnologie alternative dovrebbero andare a coprire. L’ottimizzazione della produzione e della gestione energetica d’altra parte, associata allo sviluppo di tecnologie per la riduzione dei consumi energetici, rappresenta una soluzione adeguata al problema, che può al contempo essere integrata all’interno di orizzonti temporali più brevi. L’obiettivo della presente tesi è quello di investigare, sviluppare ed applicare un insieme di strumenti numerici per ottimizzare la progettazione e la gestione di processi energetici che possa essere usato per ottenere una riduzione dei consumi di combustibile ed un’ottimizzazione dell’efficienza energetica. La metodologia sviluppata si appoggia su un approccio basato sulla modellazione numerica dei sistemi, che sfrutta le capacità predittive, derivanti da una rappresentazione matematica dei processi, per sviluppare delle strategie di ottimizzazione degli stessi, a fronte di condizioni di impiego realistiche. Nello sviluppo di queste procedure, particolare enfasi viene data alla necessità di derivare delle corrette strategie di gestione, che tengano conto delle dinamiche degli impianti analizzati, per poter ottenere le migliori prestazioni durante l’effettiva fase operativa. Durante lo sviluppo della tesi il problema dell’ottimizzazione energetica è stato affrontato in riferimento a tre diverse applicazioni tecnologiche. Nella prima di queste è stato considerato un impianto multi-fonte per la soddisfazione della domanda energetica di un edificio ad uso commerciale. Poiché tale sistema utilizza una serie di molteplici tecnologie per la produzione dell’energia termica ed elettrica richiesta dalle utenze, è necessario identificare la corretta strategia di ripartizione dei carichi, in grado di garantire la massima efficienza energetica dell’impianto. Basandosi su un modello semplificato dell’impianto, il problema è stato risolto applicando un algoritmo di Programmazione Dinamica deterministico, e i risultati ottenuti sono stati comparati con quelli derivanti dall’adozione di una più semplice strategia a regole, provando in tal modo i vantaggi connessi all’adozione di una strategia di controllo ottimale. Nella seconda applicazione è stata investigata la progettazione di una soluzione ibrida per il recupero energetico da uno scavatore idraulico. Poiché diversi layout tecnologici per implementare questa soluzione possono essere concepiti e l’introduzione di componenti aggiuntivi necessita di un corretto dimensionamento, è necessario lo sviluppo di una metodologia che permetta di valutare le massime prestazioni ottenibili da ognuna di tali soluzioni alternative. Il confronto fra i diversi layout è stato perciò condotto sulla base delle prestazioni energetiche del macchinario durante un ciclo di scavo standardizzato, stimate grazie all’ausilio di un dettagliato modello dell’impianto. Poiché l’aggiunta di dispositivi per il recupero energetico introduce gradi di libertà addizionali nel sistema, è stato inoltre necessario determinare la strategia di controllo ottimale dei medesimi, al fine di poter valutare le massime prestazioni ottenibili da ciascun layout. Tale problema è stato di nuovo risolto grazie all’ausilio di un algoritmo di Programmazione Dinamica, che sfrutta un modello semplificato del sistema, ideato per lo scopo. Una volta che le prestazioni ottimali per ogni soluzione progettuale sono state determinate, è stato possibile effettuare un equo confronto fra le diverse alternative. Nella terza ed ultima applicazione è stato analizzato un impianto a ciclo Rankine organico (ORC) per il recupero di cascami termici dai gas di scarico di autovetture. Nonostante gli impianti ORC siano potenzialmente in grado di produrre rilevanti incrementi nel risparmio di combustibile di un veicolo, è necessario per il loro corretto funzionamento lo sviluppo di complesse strategie di controllo, che siano in grado di far fronte alla variabilità della fonte di calore per il processo; inoltre, contemporaneamente alla massimizzazione dei risparmi di combustibile, il sistema deve essere mantenuto in condizioni di funzionamento sicure. Per far fronte al problema, un robusto ed efficace modello dell’impianto è stato realizzato, basandosi sulla Moving Boundary Methodology, per la simulazione delle dinamiche di cambio di fase del fluido organico e la stima delle prestazioni dell’impianto. Tale modello è stato in seguito utilizzato per progettare un controllore predittivo (MPC) in grado di stimare i parametri di controllo ottimali per la gestione del sistema durante il funzionamento transitorio. Per la soluzione del corrispondente problema di ottimizzazione dinamica non lineare, un algoritmo basato sulla Particle Swarm Optimization è stato sviluppato. I risultati ottenuti con l’adozione di tale controllore sono stati confrontati con quelli ottenibili da un classico controllore proporzionale integrale (PI), mostrando nuovamente i vantaggi, da un punto di vista energetico, derivanti dall’adozione di una strategia di controllo ottima.

A mathematical model for assembly line balancing model to consider disordering sequence of workstations

Purpose – A binary integer programming model for the simple assembly line balancing problem (SALBP), which is well known as SALBP-1, was formulated more than 30 years ago. Since then, a number of researchers have extended the model for the variants of assembly line balancing problem.The model is still prevalent nowadays mainly because of the lower and upper bounds on task assignment. These properties avoid significant increase of decision variables. The purpose of this paper is to use an example to show that the model may lead to a confusing solution. Design/methodology/approach – The paper provides a remedial constraint set for the model to rectify the disordered sequence problem. Findings – The paper presents proof that the assembly line balancing model formulated by Patterson and Albracht may lead to a confusing solution. Originality/value – No one previously has found that the commonly used model is incorrect.

Integrated component scheduling models for chip shooter machines

This paper focuses on minimizing printed circuit board (PCB) assembly time for a chipshootermachine, which has a movable feeder carrier holding components, a movable X–Y table carrying a PCB, and a rotary turret with multiple assembly heads. The assembly time of the machine depends on two inter-related optimization problems: the component sequencing problem and the feeder arrangement problem. Nevertheless, they were often regarded as two individual problems and solved separately. This paper proposes two complete mathematical models for the integrated problem of the machine. The models are verified by two commercial packages. Finally, a hybrid genetic algorithm previously developed by the authors is presented to solve the model. The algorithm not only generates the optimal solutions quickly for small-sized problems, but also outperforms the genetic algorithms developed by other researchers in terms of total assembly time.

Approaches to issues of job regulation. A study at branch level in a white collar, public sector trade union. Available in 2 volumes.

This study examines the internal dynamics of white collar trade union branches in the public sector. The effects of a number of internal and external factors on branch patterns of action are evaluated. For the purposes of the study branch action is taken to be the approach to issues of job regulation, as expressed along the five dimensions of dependence on the outside trade union, focus in issues adopted, initiation of issues, intensity of action in issue pursuit and representativeness. The setting chosen for the study is four branches drawn from the same geographical area of the National and Local Government Officers Association. Branches were selected to give a variety in industry settings while controlling for the potentially influential variables of branch size, density of trade union membership and possession of exclusive representational rights in the employing organisation. Identical methods of data collection were used for each branch. The principal findings of the study are that the framework of national agreements and industry collective bargaining structures are strongly related to the industrial relations climate in the employing organisation and the structures of representation within the branch. Where agreements and collective bargaining structures formally restrict branch job regulation roles, there is a degree of devolution of bargaining authority from branch level negotiators to autonomous shop stewards at workplace level. In these circumstances industrial relations climate is characterised by a degree of informality in relationships between management and trade union activists. In turn, industrial relations climate and representative structures together with actor attitudes, have strong effects on all dimensions of approach to issues of job regulation.

New measures of job control, cognitive demand and production responsibility

Recent research has highlighted several job characteristics salient to employee well-being and behavior for which there are no adequate generally applicable measures. These include timing and method control, monitoring and problem-solving demand, and production responsibility. In this article, an attempt to develop measures of these constructs provided encouraging results. Confirmatory factor analyses applied to data from 2 samples of shop-floor employees showed a consistent fit to a common 5-factor measurement model. Scales corresponding to each of the dimensions showed satisfactory internal and test–retest reliabilities. As expected, the scales also discriminated between employees in different jobs and employees working with contrasting technologies.

Professional standards research:job satisfaction and innovation

Job satisfaction is a significant predictor of organisational innovation – especially where employees (including shop-floor workers) experience variety in their jobs and work in a single-status environment. The relationship between job satisfaction and performance has long intrigued work psychologists. The idea that "happy workers are productive workers" underpins many theories of performance, leadership, reward and job design. But contrary to popular belief, the relationship between job satisfaction and performance at individual level has been shown to be relatively weak. Research investigating the link between job satisfaction and creativity (the antecedent to innovation) shows that job dissatisfaction promotes creative outcomes. The logic is that those who are dissatisfied (and have decided to stay with the organisation) are determined to change things and have little to lose in doing so (see JM George & J Zhou, 2002). We were therefore surprised to find in the course of our own research into managerial practices and employee attitudes in manufacturing organisations that job satisfaction was a highly significant predictor of product and technological innovation. These results held even though the research was conducted longitudinally, over two years, while controlling for prior innovation. In other words, job satisfaction was a stronger predictor of innovation than any pre-existing orientation organisations had towards working innovatively. Using prior innovation as a control variable, as well as a longitudinal research design, strengthened our case against the argument that people are satisfied because they belong to a highly innovative organisation. We found that the relationship between job satisfaction and innovation was stronger still where organisations showed that they were committed to promoting job variety, especially at shop-floor level. We developed precise instruments to measure innovation, taking into account the magnitude of the innovation both in terms of the number of people involved in its implementation, and how new and different it was. Using this instrument, we are able to give each organisation in our sample a "score" from one to seven for innovation in areas ranging from administration to production technology. We found that much innovation is incremental, involving relatively minor improvements, rather than major change. To achieve sustained innovation, organisations have to draw on the skills and knowledge of employees at all levels. We also measured job satisfaction at organisational level, constructing a mean "job satisfaction" score for all organisations in our sample, and drawing only on those companies whose employees tended to respond in a similar manner to the questions they were asked. We argue that where most of the workforce experience job satisfaction, employees are more likely to collaborate, to share ideas and aim for high standards because people are keen to sustain their positive feelings. Job variety and single-status arrangements further strengthen the relationship between satisfaction and performance. This makes sense; where employees experience variety, they are exposed to new and different ideas and, provided they feel positive about their jobs, are likely to be willing to try to apply these ideas to improve their jobs. Similarly, staff working in single-status environments where hierarchical barriers are reduced are likely to feel trusted and valued by management and there is evidence (see G Jones & J George, 1998) that people work collaboratively and constructively with those they trust. Our study suggests that there is a strong business case for promoting employee job satisfaction. Managers and HR practitioners need to ensure their strategies and practices support and sustain job satisfaction among their workforces to encourage constructive, collaborative and creative working. It is more important than ever for organisations to respond rapidly to demands of the external environment. This study shows the positive association between organisational-level job satisfaction and innovation. So if a happy workforce is the key to unlocking innovation and organisations want to thrive in the global economy, it is vital that managers and HR practitioners pay close attention to employee perceptions of the work environment. In a world where the most innovative survive it could make all the difference.

Optimizing search engines results using linear programming

When a query is passed to multiple search engines, each search engine returns a ranked list of documents. Researchers have demonstrated that combining results, in the form of a "metasearch engine", produces a significant improvement in coverage and search effectiveness. This paper proposes a linear programming mathematical model for optimizing the ranked list result of a given group of Web search engines for an issued query. An application with a numerical illustration shows the advantages of the proposed method. © 2011 Elsevier Ltd. All rights reserved.

Data Flow Analysis and the Linear Programming Model

* The research is supported partly by INTAS: 04-77-7173 project, http://www.intas.be

Applied Aspects of Mathematical Modeling and Optimization of Dynamics of Charged Beams

The complex of questions connected with the analysis, estimation and structural-parametrical optimization of dynamic system is considered in this article. Connection of such problems with tasks of control by beams of trajectories is emphasized. The special attention is concentrated on the review and analysis of spent scientific researches, the attention is stressed to their constructability and applied directedness. Efficiency of the developed algorithmic and software is demonstrated on the tasks of modeling and optimization of output beam characteristics in linear resonance accelerators.

Method of Linear Programming as an Idea for High School Curriculum

2010 Mathematics Subject Classification: 97D40, 97M10, 97M40, 97N60, 97N80, 97R80

A nettó jelenérték maximalizálása erőforrás-korlátos projektekben - egy új harmóniakereső metaheurisztika (A harmony search metaheuristic for the resourceconstrained project scheduling problem with discounted cash flows)

Ebben a tanulmányban a szerző egy új harmóniakereső metaheurisztikát mutat be, amely a minimális időtartamú erőforrás-korlátos ütemezések halmazán a projekt nettó jelenértékét maximalizálja. Az optimális ütemezés elméletileg két egész értékű (nulla-egy típusú) programozási feladat megoldását jelenti, ahol az első lépésben meghatározzuk a minimális időtartamú erőforrás-korlátos ütemezések időtartamát, majd a második lépésben az optimális időtartamot feltételként kezelve megoldjuk a nettó jelenérték maximalizálási problémát minimális időtartamú erőforrás-korlátos ütemezések halmazán. A probléma NP-hard jellege miatt az egzakt megoldás elfogadható idő alatt csak kisméretű projektek esetében képzelhető el. A bemutatandó metaheurisztika a Csébfalvi (2007) által a minimális időtartamú erőforrás-korlátos ütemezések időtartamának meghatározására és a tevékenységek ennek megfelelő ütemezésére kifejlesztett harmóniakereső metaheurisztika továbbfejlesztése, amely az erőforrás-felhasználási konfliktusokat elsőbbségi kapcsolatok beépítésével oldja fel. Az ajánlott metaheurisztika hatékonyságának és életképességének szemléltetésére számítási eredményeket adunk a jól ismert és népszerű PSPLIB tesztkönyvtár J30 részhalmazán futtatva. Az egzakt megoldás generálásához egy korszerű MILP-szoftvert (CPLEX) alkalmaztunk. _______________ This paper presents a harmony search metaheuristic for the resource-constrained project scheduling problem with discounted cash flows. In the proposed approach, a resource-constrained project is characterized by its „best” schedule, where best means a makespan minimal resource constrained schedule for which the net present value (NPV) measure is maximal. Theoretically the optimal schedule searching process is formulated as a twophase mixed integer linear programming (MILP) problem, which can be solved for small-scale projects in reasonable time. The applied metaheuristic is based on the "conflict repairing" version of the "Sounds of Silence" harmony search metaheuristic developed by Csébfalvi (2007) for the resource-constrained project scheduling problem (RCPSP). In order to illustrate the essence and viability of the proposed harmony search metaheuristic, we present computational results for a J30 subset from the well-known and popular PSPLIB. To generate the exact solutions a state-of-the-art MILP solver (CPLEX) was used.