Design of Scheduling Algorithms Using Game Theoretic Ideas

Scheduling a set of jobs over a collection of machines to optimize a certain quality-of-service measure is one of the most important research topics in both computer science theory and practice. In this thesis, we design algorithms that optimize {\em flow-time} (or delay) of jobs for scheduling problems that arise in a wide range of applications. We consider the classical model of unrelated machine scheduling and resolve several long standing open problems; we introduce new models that capture the novel algorithmic challenges in scheduling jobs in data centers or large clusters; we study the effect of selfish behavior in distributed and decentralized environments; we design algorithms that strive to balance the energy consumption and performance.

The technically interesting aspect of our work is the surprising connections we establish between approximation and online algorithms, economics, game theory, and queuing theory. It is the interplay of ideas from these different areas that lies at the heart of most of the algorithms presented in this thesis.

The main contributions of the thesis can be placed in one of the following categories.

1. Classical Unrelated Machine Scheduling: We give the first polygorithmic approximation algorithms for minimizing the average flow-time and minimizing the maximum flow-time in the offline setting. In the online and non-clairvoyant setting, we design the first non-clairvoyant algorithm for minimizing the weighted flow-time in the resource augmentation model. Our work introduces iterated rounding technique for the offline flow-time optimization, and gives the first framework to analyze non-clairvoyant algorithms for unrelated machines.

2. Polytope Scheduling Problem: To capture the multidimensional nature of the scheduling problems that arise in practice, we introduce Polytope Scheduling Problem (\psp). The \psp problem generalizes almost all classical scheduling models, and also captures hitherto unstudied scheduling problems such as routing multi-commodity flows, routing multicast (video-on-demand) trees, and multi-dimensional resource allocation. We design several competitive algorithms for the \psp problem and its variants for the objectives of minimizing the flow-time and completion time. Our work establishes many interesting connections between scheduling and market equilibrium concepts, fairness and non-clairvoyant scheduling, and queuing theoretic notion of stability and resource augmentation analysis.

3. Energy Efficient Scheduling: We give the first non-clairvoyant algorithm for minimizing the total flow-time + energy in the online and resource augmentation model for the most general setting of unrelated machines.

4. Selfish Scheduling: We study the effect of selfish behavior in scheduling and routing problems. We define a fairness index for scheduling policies called {\em bounded stretch}, and show that for the objective of minimizing the average (weighted) completion time, policies with small stretch lead to equilibrium outcomes with small price of anarchy. Our work gives the first linear/ convex programming duality based framework to bound the price of anarchy for general equilibrium concepts such as coarse correlated equilibrium.

Rapid solutions for application specific IGBT module design

The electric car, the all electric aircraft and requirements for renewable energy are prime examples of potential technologies needing to be addressed in the world problem of global warming/carbon emission etc. Power electronics are fundamental for the underpinning of these technologies and with the diverse requirements for electrical configurations and the range of environmental conditions, time to market is paramount for module manufacturers and systems designers alike. This paper presents a 'virtual' design methodology together with theoretical and experimental results that demonstrate enhanced product design with improved reliability, performance and cost value within competitive schemes.

Engineering design knowledge management in de-centralised virtual enterprises

The problems of collaborative engineering design and knowledge management at the conceptual stage in a network of dissimilar enterprises was investigated. This issue in engineering design is a result of the supply chain and virtual enterprise (VE) oriented industry that demands faster time to market and accurate cost/manufacturing analysis from conception. The solution consisted of a de-centralised super-peer net architecture to establish and maintain communications between enterprises in a VE. In the solution outlined below, the enterprises are able to share knowledge in a common format and nomenclature via the building-block shareable super-ontology that can be tailored on a project by project basis, whilst maintaining the common nomenclature of the ‘super-ontology’ eliminating knowledge interpretation issues. The two-tier architecture layout of the solution glues together the peer-peer and super-ontologies to form a coherent system for both internal and virtual enterprise knowledge management and product development.

Agitating for a design and regeneration agenda in a postconflict city: the case of Belfast

Introduction

Belfast has been a focus of academic attention for the last forty years with most interest centred on various aspects of ‘the Troubles’. Where there has been interest in the built environment, it has largely been about how the ‘security situation’ impacted directly on architecture and on the design and layout of social housing. This paper seeks to go beyond this to explore how the political- administrative culture of ‘the Troubles’ interacted with ‘normal’ market forces to shape the central area of the city, and to consider the responses of a recently formed activist group, known as the Forum for Alternative Belfast (hereafter referred to as the Forum). The paper is written by three of the directors of the Forum.1 Moreover, the empirical research presented here was undertaken by the Forum as part of a campaign to address issues relating to the design, layout and quality of Belfast’s built environment. In the longstanding tradition of participant observation working within an action-research paradigm, the participants have attempted to offer an account that is evidentially and purposefully selfcritical and reflective. It is of course recognised that while this approach offers many positive attributes, such as phenomenological access through immersion in the project, it also has the potential to bring compromise on research detachment and objectivity.2 To address the latter, the authors have attempted
to avoid polemical argument, and to support claims with primary or secondary research evidence. The authors also acknowledge that action-research has a chequered history; however, they would argue
that their approach is faithful to a concept that sees ‘research’ defined as understanding and ‘action’ defined as seeking change. The Forum’s very purpose is to seek change, but to do this requires evidence, collaboration and demonstration. And in this sense, it is a learning process for all participants, including the research activists, government officials, community organisations and students. The authors also recognise the complexity of factors that affect urban management and change, particularly in a city such as Belfast, which has had to cope with political violence for over thirty years. And they appreciate that in the context of conflict, governance is skewed to cope with political realities. Hamdi reminds us, however, that in practice there is an ‘important dialectic between top-down planning, with its formal and designed laws and structures, and bottom-up selforganizing collectivism—those “quantum and emergent systems” which Jane Jacobs argued long ago give cities their life and order.’3

Learning design contingent valuation (LDCV): NOAA guidelines, preference learning and coherent arbitrariness

We extend the contingent valuation (CV) method to test three differing conceptions of individuals' preferences as either (i) a-priori well-formed or readily divined and revealed through a single dichotomous choice question (as per the NOAA CV guidelines [K. Arrow, R. Solow, P.R. Portney, E.E. Learner, R. Radner, H. Schuman, Report of the NOAA panel on contingent valuation, Fed. Reg. 58 (1993) 4601-4614]); (ii) learned or 'discovered' through a process of repetition and experience [J.A. List, Does market experience eliminate market anomalies? Q. J. Econ. (2003) 41-72; C.R. Plott, Rational individual behaviour in markets and social choice processes: the discovered preference hypothesis, in: K. Arrow, E. Colombatto, M. Perleman, C. Schmidt (Eds.), Rational Foundations of Economic Behaviour, Macmillan, London, St. Martin's, New York, 1996, pp. 225-250]; (iii) internally coherent but strongly influenced by some initial arbitrary anchor [D. Ariely, G. Loewenstein, D. Prelec, 'Coherent arbitrariness': stable demand curves without stable preferences, Q. J. Econ. 118(l) (2003) 73-105]. Findings reject both the first and last of these conceptions in favour of a model in which preferences converge towards standard expectations through a process of repetition and learning. In doing so, we show that such a 'learning design CV method overturns the 'stylised facts' of bias and anchoring within the double bound dichotomous choice elicitation format. (C) 2007 Elsevier Inc. All rights reserved.

Spatial Mobility Intentions, the Labour Market and Incapacity Benefit Claimants Evidence from Northern Ireland

The paper analyses the work-related spatial mobility intentions of incapacity benefit (IB) claimants in Northern Ireland using a new survey dataset. Greater understanding of the prospective mobility of benefit claimants contributes to debates about employability, inclusion in the labour market and arguments about spatial mismatch. The analysis finds that IB claimants are not markedly less mobile than other population groups; that mobility is shaped by age, level of qualification, illness type, ability to drive and motivation; and that geography is important in several ways. The paper concludes by arguing that limited spatial mobility is a good indicator of disadvantage and that spatial mobility should be placed nearer the centre of the design and delivery of labour market policy

Combining preference ordering and contingent valuation methods to assess non market benefit of alternative afforestation projects

The application of the contingent valuation method (CVM) in this paper incorporates a prior preference ordering of several alternative future afforestation programmes which could be implemented in Ireland over the next decade. This particular experimental design is thereby shown to reveal the potentially conflicting preferences of different groups within society. These findings are used to devise appropriate CVM scenarios to take account, not only of the efficiency gains of choosing a single policy alternative over others, but also the effects on the distribution of non market benefit between different groups within society, arising from choice between alternatives. (C) 1998 Elsevier Science Ltd. All rights reserved.

Measuring non-use value of environmental goods using the contingent valuation method:problems of information and cognition and the application of cognitive questionnaire design methods

Much interest now focuses on the use of the contingent valuation method (CVM) to assess non-use value of environmental goods. The paper reviews recent literature and highlights particular problems of information provision and respondent knowledge, comprehension and cognition. These must be dealt with by economists in designing CVM surveys for eliciting non-use values. Cognitive questionnaire design methods are presented which invoke concepts from psychology and tools from cognitive survey design (focus groups and verbal reports) to reduce a complex environmnetal good into a meaningful commodity that can be valued by respondents in a contingent market. This process is illustrated with examples from the authors' own research valuing alternative afforestation programmes. -Authors

Colagens têxteis: em busca de um design sustentável

Os desafios dos designers nos dias de hoje são inúmeros, sendo um deles o de desenvolver produtos que atendam ao mercado sem deixar de lado as preocupações com a sustentabilidade, seja ambiental, sócio-ética ou econômica. Assim sendo, a própria disputa para alcançar novos patamares de destaque no mercado também fez proliferar novas tecnologias de produção sustentável como um fator diferenciador nos dias de hoje que, para além de preservar a natureza, conquista uma larga faixa de clientes sensíveis a este tipo de preocupações. É objetivo deste trabalho a criação de produtos de design de moda e decoração e sua verificação enquanto design sustentável. Neste contexto, enquadra-se este trabalho que visa desenvolver produtos de moda e decoração realizados com a técnica da colagem têxtil, resultando assim, em produtos inovadores, únicos, intemporais e com design. A presente investigação desenvolveu-se em parceria com o Banco de Vestuário de Caxias do Sul, que forneceu dados para o estudo do setor têxtil e levantamento dos resíduos da indústria têxtil da região para caracterização do setor, além de disponibilizar os resíduos têxteis que serviram de base para a criação de produtos de moda e de decoração mais sustentáveis. Para a criação das superfícies têxteis coladas foram desenvolvidas amostras com testes de temperaturas e tempos para verificar a combinação que mais se adequa a cada tipo de matéria-prima. Além de fazer uso destes resíduos, a investigação contou com o auxílio de mão-de-obra de artesãs que, por sua vez, foram capacitadas com a técnica da colagem têxtil através de dois workshops. Após esta etapa, para fazer a análise dos níveis de sustentabilidade dos produtos, utilizou-se o Sustainability Design Orienting Toolkit (SDO) que é um conjunto de ferramentas que visa a orientação dos designers no desenvolvimento de produtos em termos de sustentabilidade ambiental, sócio-ética e econômica.

Microstructure design of Titanate-based electroceramics

Electrocerâmicos são uma classe de materiais avançados com propriedades eléctricas valiosas para aplicações. Estas propriedades são geralmente muito dependentes da microestrutura dos materiais. Portanto, o objectivo geral deste trabalho é investigar o desenho da resposta dieléctrica de filmes espessos obtidos por Deposição Electroforética (EPD) e cerâmicos monolíticos, através do controlo da evolução da microestrutura durante a sinterização de electrocerâmicos à base de titanatos. Aplicações sem fios na indústria microelectrónica e de comunicações, em rápido crescimento, tornaram-se um importante mercado para os fabricantes de semicondutores. Devido à constante necessidade de miniaturização, redução de custos e maior funcionalidade e integração, a tecnologia de filmes espessos está a tornar-se uma abordagem de processamento de materiais funcionais cada vez mais importante. Uma técnica adequada neste contexto é EPD. Os filmes espessos resultantes necessitam de um passo subsequente de sinterização que é afectada pelo substrato subjacente, tendo este um forte efeito sobre a evolução da microestrutura. Relacionado com a miniaturização e a discriminação do sinal, materiais dieléctricos usados como componentes operando a frequências das microondas em aplicações na industria microelectrónica de comunicações devem apresentar baixas perdas dieléctricas e elevadas permitividade dieléctrica e estabilidade com a temperatura. Materiais do sistema BaO-Ln2O3- TiO2 (BLnT: Ln = La ou Nd), como BaLa4Ti4O15 (BLT) e Ba4.5Nd9Ti18O54 (BNT), cumprem esses requisitos e são interessantes para aplicações, por exemplo, em estações de base para comunicações móveis ou em ressonadores para telefones móveis, onde a miniaturização dos dispositivos é muito importante. Por sua vez, o titanato de estrôncio (SrTiO3, STO) é um ferroeléctrico incipiente com constante dieléctrica elevada e baixas perdas, que encontra aplicação em, por exemplo, condensadores de camada interna, tirando partido de fronteiras de grão altamente resistivas. A dependência da permitividade dieléctrica do campo eléctrico aplicado torna este material muito interessante para aplicações em dispositivos de microondas sintonizáveis. Materiais à base de STO são também interessantes para aplicações termoeléctricas, que podem contribuir para a redução da actual dependência de combustíveis fósseis por meio da geração de energia a partir de calor desaproveitado. No entanto, as mesmas fronteiras de grão resistivas são um obstáculo relativamente à eficiência do STO para aplicações termoeléctricas. Para além do efeito do substrato durante a sinterização constrangida, outros factores, como a presença de fase líquida, a não-estequiometria ou a temperatura de sinterização, afectam significativamente não apenas a microestrutura dos materiais funcionais, mas também a sua resposta dieléctrica. Se adequadamente compreendidos, estes factores podem ser intencionalmente usados para desenhar a microestrutura dos electrocerâmicos e, desta forma, as suas propriedades dieléctricas. O efeito da não-estequiometria (razão Sr/Ti 0.995-1.02) no crescimento de grão e resposta dieléctrica de cerâmicos de STO foi investigado neste trabalho. A mobilidade das fronteiras de grão aumenta com a diminuição da razão Sr/Ti. A resistividade do interior dos grãos e das fronteiras de grão é sistematicamente diminuída em amostras não-estequiométricas de STO, em comparação com o material estequiométrico. O efeito é muito mais forte para as fronteiras de grão do que para o seu interior. Dependências sistemáticas da não-estequiometria foram também observadas relativamente à dependência da condutividade da temperatura (muito mais afectada no caso da contribuição das fronteiras de grão), à capacitância do interior e fronteiras de grão e à espessura das fronteiras de grão. Uma anomalia no crescimento de grão em cerâmicos de STO ricos em Ti foi também observada e sistematicamente analisada. Foram detectadas três descontinuidades na dependência do tipo Arrhenius do crescimento de grão relativamente à temperatura com diminuições no tamanho de grão a temperaturas em torno de 1500, 1550 e 1605 °C. Além disso, descontinuidades semelhantes foram também observadas na dependência da energia de activação relativamente à condutividade das fronteiras de grão e na espessura das fronteiras de grão, avaliadas por Espectroscopia de Impedância. Estas notáveis coincidências suportam fortemente a formação de diferentes complexos de fronteira de grão com transições entre os regimes de crescimento de grão observados, que podem ser correlacionados com diferentes mobilidades de fronteira de grão e propriedades dieléctricas. Um modelo é sugerido, que se baseia na diminuição da fase líquida localizada nas fronteiras de grão, como o aumento da temperatura de sinterização, um cenário compatível com um fenómeno de solubilidade retrógrada, observado anteriormente em metais e semicondutores, mas não em cerâmicos. A EPD de filmes espessos de STO em substratos de folha de Pt e a sinterização constrangida dos filmes fabricados foram também preliminarmente tratadas. Filmes espessos de STO foram depositados com êxito por EPD sobre substratos de Pt e, depois de sinterizados, atingiram densidades elevadas. Um aumento da densificação e do tamanho de grão assim como o alargamento da distribuição de tamanho do grão foram observados com a diminuição da razão Sr/Ti, tal como anteriormente observado em amostras cerâmicas. Grãos equiaxiados foram observados para todas as composições, mas um certo grau de anisotropia na orientação dos poros foi detectado: os poros revelaram uma orientação vertical preferencial. Este trabalho focou-se também na sinterização constrangida do sistema BLnT (Ln = La ou Nd), nomeadamente de filmes espessos de BLT e BNT sobre substratos de folha de platina, e na relação do desenvolvimento de anisotropia microestrutural com as propriedades dieléctricas. As observações durante a sinterização constrangida foram comparadas com cerâmicos monolíticos equivalentes sinterizados livremente. Filmes espessos de BLnT (Ln = La ou Nd) com elevada densidade foram obtidos por EPD e subsequente sinterização constrangida. A anisometria cristalográfica do material em conjunto com um passo de sinterização constrangida resultou em grãos alongados e microestruturas anisotrópicas. O efeito do stress do substrato durante a sinterização constrangida originou graus mais elevados de anisotropia (grãos e poros alongados e orientação preferencial, bem como textura cristalográfica) nos filmes sinterizados relativamente aos cerâmicos equivalentes sinterizados livremente, não obstante o estado equivalente das amostras em verde. A densificação dos filmes de BLnT (Ln = La ou Nd) é retardada em comparação com os cerâmicos, mas depois de longos tempos de sinterização densidades semelhantes são obtidas. No entanto, em oposição a observações na sinterização constrangida de outros sistemas, o crescimento do grão em filmes de BLnT (Ln = La ou Nd) é favorecido pelo constrangimento causado pelo substrato. Além disso, grãos e poros alongados orientados paralelamente ao substrato foram desenvolvidos durante a sinterização constrangida de filmes espessos. Verificou-se uma forte correlação entre a evolução de grãos e poros, que começou assim que o crescimento do grão se iniciou. Um efeito da tensão do substrato no aumento do crescimento de grão, bem como um forte “Zener pinning”, origina microestruturas altamente texturizadas, o que também é observado a nível cristalográfico. Efeitos marcantes da anisotropia microestrutural foram também detectados nas propriedades dieléctricas dos filmes de BLnT (Ln = La ou Nd). Juntamente com o aumento da razão de aspecto dos grãos, do factor de orientação e do grau de textura cristalográfica, a permitividade relativa é ligeiramente diminuída e o coeficiente de temperatura da permitividade evolui de negativo para positivo com o aumento do tempo isotérmico de sinterização. Este trabalho mostra que a não-estequiometria pode ser usada para controlar a mobilidade das fronteiras de grão e, portanto, desenhar a microestrutura e as propriedades dieléctricas de electrocerâmicos à base de STO, com ênfase nas propriedades das fronteiras de grão. O papel da não-estequiometria no STO e dos complexos de fronteira de grão no desenvolvimento microestrutural é discutido e novas oportunidades para desenhar as propriedades de materiais funcionais são abertas. As observações relativamente à sinterização constrangida apontam para o efeito de tensões mecânicas desenvolvidas devido ao substrato subjacente no desenvolvimento da microestrutura de materiais funcionais. É assim esperado que a escolha adequada de substrato permitia desenhar a microestrutura de filmes espessos funcionais com desempenho optimizado. “Stress Assisted Grain Growth” (SAGG) é então proposto como uma técnica potencial para desenhar a microestrutura de materiais funcionais, originando microestruturas anisotrópicas texturizadas com propriedades desejadas.

Design de unidades funcionais: plataforma para o desenvolvimento novos produtos universidade-indústria

Este trabalho de investigação teve como principais objetivos, por um lado, procurar as relações existentes entre a Instituição Ensino Superior de Design (IES-D) e as empresas, por outro, configurar um modelo que permitisse criar uma plataforma de inovação para o desenvolvimento de novos produtos na IES-D num contexto globalizado. Nos últimos anos, o setor “ensino superior” na Europa e em várias partes do mundo passou por grandes mudanças, o que acentuou o ambiente competitivo entre as IES, incluindo as de Design. Neste âmbito, procurou-se demonstrar o novo posicionamento estratégico da IES-D perante o mercado, e quais as ações a desenvolver que possibilitam alcançar uma vantagem competitiva sustentável. Primeiro, considerou-se fundamental identificar a importância do design perante o ensino, a situação mundial e a mudança da cultura económica. Depois, assinalaram-se as iniciativas de promoção do design e as políticas de inovação europeias. E por fim, reuniram-se os aspetos que obrigam as IES-D a assumir novos papéis de interação com o mercado. Por análise comparativa internacional procedeu-se à seleção de uma amostra de dezoito (18) IES-D – dez europeias, quatro norte americanas e quatro asiáticas. Instituições de ensino com tipologias diversas e pertencentes a distintos contextos socioeconómicos. A caracterização da amostra através de análise estrutural permitiu identificar aspetos comuns às IES-D – ações estratégicas que servem para promover a inovação. Para explicitar a interação do sistema formado por esses elementos comuns, configurou-se um modelo concetual – Hexágono da Inovação (HI). O modelo, enquanto instrumento de análise, permite criar um padrão da inovação da IES-D e posicioná-la perante o setor - ensino superior de design. Foi também realizado um ensaio da aplicabilidade do modelo concetual HI na ESAD.cr/IPL. Através da implementação da plataforma de inovação - ESAD Design Studio - Centro de Estudos e Investigação em Design (EDS/CEID), foram ensaiadas as ações necessárias para promover o design estratégico e o design de inovação.

Inter layer and cooperative design strategies for green mobile networks

The promise of a truly mobile experience is to have the freedom to roam around anywhere and not be bound to a single location. However, the energy required to keep mobile devices connected to the network over extended periods of time quickly dissipates. In fact, energy is a critical resource in the design of wireless networks since wireless devices are usually powered by batteries. Furthermore, multi-standard mobile devices are allowing users to enjoy higher data rates with ubiquitous connectivity. However, the bene ts gained from multiple interfaces come at a cost in terms of energy consumption having profound e ect on the mobile battery lifetime and standby time. This concern is rea rmed by the fact that battery lifetime is one of the top reasons why consumers are deterred from using advanced multimedia services on their mobile on a frequent basis. In order to secure market penetration for next generation services energy e ciency needs to be placed at the forefront of system design. However, despite recent e orts, energy compliant features in legacy technologies are still in its infancy, and new disruptive architectures coupled with interdisciplinary design approaches are required in order to not only promote the energy gain within a single protocol layer, but to enhance the energy gain from a holistic perspective. A promising approach is cooperative smart systems, that in addition to exploiting context information, are entities that are able to form a coalition and cooperate in order to achieve a common goal. Migrating from this baseline, this thesis investigates how these technology paradigm can be applied towards reducing the energy consumption in mobile networks. In addition, we introduce an additional energy saving dimension by adopting an interlayer design so that protocol layers are designed to work in synergy with the host system, rather than independently, for harnessing energy. In this work, we exploit context information, cooperation and inter-layer design for developing new energy e cient and technology agnostic building blocks for mobile networks. These technology enablers include energy e cient node discovery and short-range cooperation for energy saving in mobile handsets, complemented by energy-aware smart scheduling for promoting energy saving on the network side. Analytical and simulations results were obtained, and veri ed in the lab on a real hardware testbed. Results have shown that up to 50% energy saving could be obtained.

Design e auto-produção : novos paradigmas para o design de artefactos na sociedade pós-industrial : a contribuição das tecnologias digitais

Tese de doutoramento, Belas-Artes (Design de Equipamento), Universidade de Lisboa, Faculdade de Belas-Artes, 2015

Reference clock design for low power and low phase noise with temperature compensation

Thesis (Ph.D.)--University of Washington, 2016-03