Nicolaï I Reeds

Sylvie Faucheux
email: sylvie.faucheux@uvsq.fr

Senior Isabelle Nicolaï
email: isabelle.nicolai@uvsq.fr

IT for Green and Green IT: a proposed typology of eco-innovation

Keywords: IT, ecological economics, eco-innovation, externalities, business ecosystem, collective innovation, smart grid

This article is in support of the development of an ecological economic framework. It discusses, from an interdisciplinary perspective, the increasing use of green IT and their applications (IT for green). IT and sustainable development have had a concomitant rise and reach. The future world emerging from their respective interpretations enables, in both cases, a shift from today's questionable industrial capitalism towards post-industrial capitalism. This paper addresses the following questions: What is known about green IT and IT for green? Are smart solutions (buildings, energy grids, transport) always beneficial to an ecological economy? And, if so, in what ways? In the first part of this article, we analyse the economic, social and environmental impact of IT and argue for the need for green applications of green IT in order to achieve sustainable outcomes. The second part focuses on the managerial dimension of eco-innovation theory and presents one of the distinctive features of green applications of green IT: the collective organisation of innovation. A typology of eco-innovation aimed at reconciling IT development and green growth is then proposed explicitly addressing four kinds of changes towards sustainable development: technological, social, institutional and organisational innovation.

IT for Green and Green IT: a proposed typology of eco-innovation

Since the late 1970's, with the increase of global threats to the environment, the idea that the economy can no longer be studied independently from the reproduction of the natural environment has gradually spread. This is the very foundation of ecological economics [START_REF] Costanza | Toward an ecological economics[END_REF]. It is in that context that the concept of sustainable development, which gradually emerged as a new development paradigm, arose in 1987. Though initially a constraint, it has become an opportunity, as it combines three advantages in today's uncertain times: a response to climate and energy challenges; a way out of a possible crisis; and a potential growth path. 1 The radical technological breakthrough represented by the emergence of IT 2 in the 1970's is now acknowledged by all. Its spreading in the 1990's to all areas of the economic and social spectra has led to many changes. Its development is based on strong knowledge content and is based on intangible capital. They are the source of the new economy, which is also referred to as the knowledge economy or the post-industrial economy. 3 IT are to the latter what the deployment of electricity was to the industrial model [START_REF] Muet | Impacts économiques de la révolution numérique[END_REF]. It is not difficult to see how one might perceive the new paradigm of development or ecological economics as having entered its technological revolution stage. This became evident in 2005 with the production of a plethora of government, intergovernmental and sector-based reports, as well as scholarly work combining IT and sustainable development [START_REF] Faucheux | TIC et Développement Durable[END_REF]. In this respect, the Tunis Commitment, from the second World Summit on the Information Society (WSIS), is revealing when it declares that it "represents a unique opportunity to raise awareness about the benefits that IT can bring to humanity and the manner in which they can transform people's activities, interaction and lives, and thus increase confidence in the future", 4 as the European Commission's announcement of its support of the use of IT to achieve energy efficiency targets across all economic sectors by 2015 (C(2009) 7604 final).

Yet, if IT and sustainable development are closely intertwined, rebound effects are, in many cases, a likely result [START_REF] Greening | Energy efficiency and consumption: the rebound effect. A survey[END_REF]. Their direct and indirect effects must be known, anticipated and evaluated. However, IT and their relationship to sustainable development are most often addressed in a broad way, which sometimes lacks rigour when it comes to their relationship to economic, social and environmental change.

This article avoids this pitfall by integrating the following elements to its methodological framework: i) Two concepts are used depending on the nature of IT:

-Green IT defined as IT sector's own activity and its impact on environmental efficiency.

-Green applications of IT or IT for green defined as the impact of IT on other sectors' environmental productivity, particularly in terms of energy efficiency and carbon footprint.

ii) The hypothesis that green applications drive positive externalities, only when green IT is used.

Given the study presented on the impact of IT on sustainable development, we argue that green IT can only lead to sustainable growth if IT themselves are green. In that case, they can be understood as equivalent to an eco-innovating contribution to ecological economics [START_REF] Rennings | Redefining innovation -eco-innovation research and the contribution from ecological economics[END_REF]. An ecoinnovation is an innovation (as defined by Schumpeter (1934)) that reduces environmental burdens and contributes to improving a situation according to given sustainable targets. In addition to this, because demonstrating the ways in which green IT has an impact on the production and consumption of IT remains complex, the integration of elements of management of eco-innovation systems to the economic analysis of eco-innovation is required.

iii) Methodological pluralism as established in ecological economics with contributions of neoclassical and evolutionary approaches would be very valuable for IT eco-innovation research [START_REF] Witt | What is specific about evolutionary economics[END_REF]. We intend to open up this framework to managerial changes. Eco-innovation, which spreads concomitantly in clusters, is studied drawing on the theme of eco-city, and bringing together the sectors with the greatest impact in terms of CO 2 emissions, and significant social repercussions (construction, transport, energy). These sectors were chosen based on about twenty surveys 5 (qualitative, of semi-directional type) with stakeholders (in Europe and the USA) involved in major technological and environmental prospective activities (ECF, 2010;IPTS, 2003). We argue that, in that context, green IT belongs to a collective innovation perspective [START_REF] Allen | Collective invention[END_REF] referring to various stakeholders and internal and external factors influencing the process of eco-innovation. A neoinstitutional approach has been used to explain this additional feature of eco-innovation with an emphasis on business ecosystems' interactions, social innovation and user acceptance. This contribution discusses the increasing use of green IT and their green application in support of the development of ecological economics from an interdisciplinary perspective. In the first part, we analyse the economic, social and environmental impact of IT on sustainable development. We argue that the complex effects IT have on sustainable development leads us to an examination of IT as an eco-innovation that experiences changes at technical, social and institutional levels. The second part defines the different determinants of eco-innovation, derived or generated by green IT as well as IT for green. This article examines the ways in which eco-innovations' determinants interrelate in ecological economics to explicitly address technological, social, institutional and managerial changes.

The arguable effects of IT on sustainable development

The effects of IT on the three dimensions of sustainable development can directly be assessed on the technology or indirectly on IT's application as they occur at different stages of its lifecycle. Their real or estimated global impact is difficult to identify as it occurs at different levels of influence. Drawing on [START_REF] Faucheux | TIC et Développement Durable[END_REF], we can, however, distinguish: first order effects, with an impact resulting from all stages of production through to the end of IT equipment and infrastructure's lifecycle, and second order effects, with an impact linked to the development of IT and its use. This distinction will enable us to establish different types of sustainable impact according to their effects, but also in relation to the position of various stakeholders in terms of responsibility and engagement. These different strategies are the basis of an analysis in terms of business ecosystems that is discussed in the 2 nd part of this article. Third order effects are systemic changes that emerge from the aggregated effects of a large number of private or public IT stakeholders.

1.1. The economic benefits of IT According to Pilat (OECD, 2008), investment in IT increases the capital stock and improves labour productivity. Fast technological progress in the production of goods and services of IT can contribute towards the development of capital and labour efficiency, or multifactor productivity (MFP) in the IT production sector as well as in the global economy. IT are also likely to intensify the effects of network/external effects, such as reducing transaction costs and accelerating innovation, which can also improve MFP. They are also able to both rapidly create a crisis and be responsible for increased market volatility.

First order effects are generally positive, but unevenly distributed across countries.

The IT sector has contributed towards 16% of global GDP growth between 2002 and 2007 and has seen its share in the latter year rise from 5.8 to 7.3%. This contribution is expected to reach 10% between 2007[START_REF]Impacts of Information and Communication Technologies on Energy Efficiency[END_REF](The Climate Group, 2008), with an increased weight for emerging and developing countries.

The digital economy is becoming the most dynamic sector of the global economy. In most developed countries, its growth rate is double that of their total economy. This evolution is reflected in the increase in the number of jobs created in this sector (an average of 20% between 1995 and 2005 in OECD countries).

The IT sector has become in terms of R&D the greatest investor and employer in Europe, the USA and Japan. For OECD countries, it accounts for 26% of all private sector R&D, employs 32% of its researchers and is responsible for 21% of all patents (Turley et al., 2009). In fact, total expenses of the private sector's IT R&D is even greater when outcomes generated by other R&D sectors (e.g. transport) contributing to the IT sector are taken into account. The weight of this additional expense is estimated at a third more than that of the IT sector per se. Given the weight of R&D in IT, businesses' positions within this sector are changing rapidly and significantly with the emergence of new markets (e.g. mobile telecommunications and fibre optics) and challenging established competitive positions.

Second order effects are both providers of opportunities and obstacles according to sectors, businesses and countries.

Investment in IT hardware and software has a significant impact on productivity (higher than in the industrial sector) [START_REF] Clayton | What can we tell from OECD economies about impact of IT use on economic growth? Can we tell if the lessons are transferable to developing economies? Notes conférence CNUCED sur les TIC et le développement[END_REF]. However, the use of electronic business processes, integrated or multiple, has a dual effect on manufacturing and services businesses: in the first instance, positive effects come mainly from the management of purchases and supply chain; and the effects arise primarily from customer relations (Legner and Schemm, 2008).

The 2006 survey conducted by Watch, the e-business observatory, gives an overview of IT for European businesses and underlines the persistent gap between SME and large companies [START_REF] Ec | The European e-Business Report: A portrait of e-business in 10 sectors of the EU economy[END_REF].

The use of IT in French SME and small businesses is significantly low [START_REF] Eurostats | IT Impact Assessment by Data linking[END_REF].

The use of IT is changing the way businesses think about their markets. It is a source of inspiration for new business models turned towards virtual markets or customised markets. It gives consumers the opportunity to enhance their position and encourage greater corporate social responsibility.

Meanwhile, electronic commerce has reduced transaction costs and improved the competitive functioning of the market.

According to stakeholders involved in major international prospective activities, a certain number of future innovations, eco-innovation, 6 will be linked to progresses in all sectors of IT. This refers to IT for green defined in introduction and analysed in section 2.1. This constitutes a lever for businesses' competitiveness to such an extent that many agree on the fact that new growth, often described as green, can only be generated by these eco-innovations, which are at the centre of a current economic race (Faucheux and Nicolaï, 2006). Table 1 summarises the main eco-innovations enabled by IT for green in the context of eco-cities as well as their economic and competitive dimensions.

Insert Table 1: The main eco-innovation enabled by IT for green within the domain of sustainable city.

Eco-innovation is thus a real option in the fight against climate change and to foster economic recovery. Some specialists (California Clean Tech Open, 2008) describe the potential of IT for green as "the biggest growth opportunity of the 21 st century". These are thus proving inseparable from competitive advantage and international competitiveness, both at a micro and macro-economic level [START_REF] Beise | Lead markets and regulation: a framework for analyzing the international diffusion of environmental innovations[END_REF].

The social impact of IT

The impact of IT on the social realm is less well defined and probably more difficult to measure than its impact on the economic realm. Separating economic and social impacts isn't always obvious. This is why IT is increasingly present in social surveys. These surveys reveal that IT is changing the ways in which people act and work (Statistics Finland, 2006), the jobs they do, their daily activities, such as their shopping and banking habits or their interactions with government services (ABS, 2006), their spending habits, their use of time and the ways in which they communicate with their families or in groups (ONS, 2006). Furthermore, IT have an impact on health (Pew, 2006), crime and education.

The main first order social impacts are linked to unequal employment opportunities in the IT sector and to the digital split. 7 In Europe, the annual IT sector employment growth rate is around 8%. Each job created in this sector can be linked to the creation of four others in the entire European economy, either upstream in the suppliers' sector or downstream in the software industry service sector. At a macro-economic level, the increased use of IT leads to the creation of highly skilled jobs, and the loss of less skilled jobs in other sectors. The marginalisation of unskilled workers is a significant threat to social cohesion that may become more critical as IT's development expends to all sectors of the economy. Owing to the application of IT green, new skilled professions will be on the rise, in the construction or heritage management sectors for example, with the development of intelligent buildings or in the car industry with the development of carbon-free cars (electric or hybrid) and other transport services. This implies anticipating and supporting an ambitious lifelong training program [START_REF] Rennings | The employment impact of cleaner production on the firm levelempirical evidence from a survey in five European countries[END_REF].

Obstacles to global access to IT (what is known as the digital split) could also reinforce existing patterns of exclusion [START_REF] Ecofys | From workplace to anyplace assessing the opportunities to reduce greenhouse gas emissions with virtual meetings and telecommuting[END_REF]. The digital split is not just about access to the Internet and its use, but to all IT (computers, interactive digital television, multimedia, mobile telecommunications, digital photography and digital video). There is a pressing need for data and indicators to measure the level of access as the currently available information on which international comparisons is based pertains almost exclusively to the use of the Internet and, to a lesser degree, to the use of mobile phones (Eurostats, 2009). For people, obstacles can range from inconvenience to more significant losses, such as unequal opportunities in the labour market. For countries or territories, obstacles include the lack of infrastructure, likely to result in greater economic gaps.

Social impacts linked to the use of IT (second order effects) should not be overlooked either.

They transform lifestyles and the organisation of labour. This is especially true of teleworking (Ecofys, 2008). Teleworkers represent an average of 13% of the workforce in Europe and 25% in the USA. Denmark is the leader with nearly 20% of its workforce engaged in regular or occasional teleworking. In France, the rate is only of 7%, which is why "Digital France 2012", the French government's digital economy development plan, outlines a range of incentives to increase this rate (CGTI, 2008). If teleworking is linked to economic benefits such as reduced overheads for businesses, it can also be linked to social benefits, such as reduced commuting time, more flexible working hours, greater work-life balance, the inclusion of traditionally excluded groups (e.g. mobility impaired people for instance) and opportunities to work from remote locations. However, it is not without a negative impact: it suits a project-based work culture that is not yet mainstream; traditional hierarchical management models are replaced with other forms of control; and new structures may lead to increased levels of stress due to unusual working hours (nightshifts, weekends, etc.) (Askénazy, 2005).

The global impact is also very difficult to define as the substitution effects vs. the induction effects linked to green applications have only partially been evaluated and are contingent upon the solution offered [START_REF] Hilty | Information Technology and Sustainability[END_REF].

As the Internet reaches all nations and spheres of activity, many voices can be heard that challenge the socio-economic and political control of this technical device and request that it be managed internationally and in compliance with principles of Participatory Governance for Sustainable Development [START_REF] Raboy | Rapport sur la communication au coeur de la gouvernance globale[END_REF]. Indeed, the Internet's physical core is only located within five countries (the USA, Japan, the UK, Spain and Sweden). Information pertaining to objects, such as origin, place of production, technical or health checks, etc., is still traceable over the Internet. These are thus major issues, not only in terms of nations' sovereignty, but also in terms of individual freedom. Thus, the social effects of IT linked to the production as well as to the use remain mostly undefined.

IT's environmental and health effects

Numerous studies on the environmental impact of IT production (first degree effect) highlight the following elements:

The over-consumption of non-renewable and toxic resources, especially of heavy metals 8 (lead, mercury, cadmium, beryllium, etc.), during the phase of extraction of raw materials used in the production of IT is frequently identified as a source of problem.

Production processes require the use of products that are highly toxic and dangerous for the environment and people's health. For example, brominated flame retardants 9 are linked to neurological and blood diseases or certain types of cancers [START_REF] Hilty | The Precautionary Principle in the Information Society -Effects of Pervasive Computing on Health and Environment[END_REF]. High levels of energy and water consumption are also necessary. Although much of this water can be recycled, none of the microchips producers seem to do so. It is not uncommon that newly built data centres consume more energy than the cities where they are located. In 2008, the total energy consumption of IT equipment and services represented about 8% of the electricity consumed in the EU. The IT sector itself generates 2% of carbon emissions in Europe, 1.75% resulting from the use of IT products and services and 0.25% from their production (BioIS, 2008). Material flow studies show that only 2% of them could be found in IT products (Erdman et al., 2004).

Similarly, according to several ACV studies, 10 the production phase represents between 15 and 25% of the total energy consumption for IT's lifecycles (based on agreed lifecycle spans). A number of manufacturers of computers and other electronic goods are no longer satisfied with this situation.

Aware that there is a genuine issue of acceptability and competitiveness for their products, they are rising to the challenge, as evidenced by the emergence of green IT (see 2.1).

Waste from electrical and electronic goods, linked to the end of IT lifecycles, represents a significant environmental problem difficult to manage because of its increasing volume and its very specific nature (SVTC, 2004). In 2007, in France, it was estimated that 16kg of electrical and electronic products per capita/year were placed on the market, while only 2.5kg per capita/year were recycled.

The recycling target imposed by the European Waste Electrical and Electronic Equipment (WEEE) directive (2002/96/CE) requires that 4kg per capita/year be recycled for each member country, with an obligation for producers to finance the recycling efforts. Some European countries are proactive in this area. This is the case for Scandinavian countries (15kg per capita/year), the UK (10kg per capita/year) and Germany (8kg per capita/year). Several components of IT waste are now recycled, but the organisations that collect and recycle these products remain limited in terms of efficiency and structure. In the USA, three quarters of computers are stacked in garages or in storage [START_REF] Pnue | Les Déchets Electroniques, la face cachée de l'ascension des technologies de l'information et des communications[END_REF].

When computers are discarded, they end up in landfills or in incinerators or, more recently, exported by some countries to Asia or Africa. The report entitled "Exporting Harm: The High Tech' trashing of Asia" 11 states that 50 to 80% of IT waste collected on the West Coast of the USA 12 is placed in containers and loaded onto ships for China, Pakistan or India at a 10 times lower recycling cost, but with drastic health and environmental consequences. In France, the recycling processes are complex and involve a range of players. The dismantling is often given to rehabilitation companies. The various components are then handled by companies specialised in recycling metals and plastics. Local organisations' participation is often difficult to determine and environmental burdens are nonnegligible.

The IT usage and implementation phase (second order effects) is not free of environmental externalities either, but these are less well defined than the first-order effects.

In Europe, a significant percentage of domestic electricity consumption is linked to the use of IT. It was estimated at 8% of total electricity consumption in 2005, and will be increasing regularly till 2020 (BioIS, 2008).

In France, the share of electricity consumption of IT is estimated at 13.5% of the total level of consumption, and this despite the regular improvement of energy efficiency equipment [START_REF] Idate | Understanding the Digital World, presentation[END_REF]BCG 2010). The carbon footprint 13 of IT in 2007 was 830 MtCO 2 e, which represents 2% of the estimated total emission from human activity measured for the year, which represents a 6% increase per year until 2020 (The Climate Group, 2008). The share of carbon footprint linked to the use of IT is about four times greater than that linked to their production. This footprint is expected to triple over the next 20 years according to a "business as usual" scenario of economic development. The exponential growth of data centres will be the main culprit.

At the same time, the replacement of traditional technologies by IT leads to a reduction in the amount of resources consumed in manufacturing goods as described in the virtualisation or dematerialisation of hardware [START_REF] Haake | L'entreprise légère, Delachaux et Niestlé editions[END_REF]: music stored and transmitted on the web, digital photography, transaction via the Internet, e-commerce, etc. However, the consequences of the spread of e-commerce, and e-work, may also be the cause of rebound effects 14 [START_REF] Faucheux | NTIC et environnement : enjeux, risques et opportunités[END_REF]. For example, teleworking changes our relationship to urban and rural spaces and provides tertiary industry sector workers with new opportunities, such as the choice of place of residence, which may have a negative impact on urban, town and country planning and, thus, on transportation energy costs.

Finally, IT has an important role to play in promoting eco-innovation in other sectors such as transport, building or energy distribution, and thus enabling greater energy and environmental efficiency within those sectors that are amongst the largest contributors to greenhouse gas emission.

That is why, although an increase in CO 2 emission is expected for the IT sector, this should be offset over time, by a drop generated by their implementation across all sectors. The overall environmental effects are generally extremely difficult to assess and are largely dependent on third order effects (i.e. users' behaviour). The networked development of eco-innovations becomes a defining aspect of IT when taken into consideration within the managerial approach of the analytical framework of ecoinnovation.

Green IT and IT for green: catalysers and drivers of eco-innovation

IT are thus increasingly exerting pressure on the environment while also being a source of potential social problems. Furthermore, they significantly alter the economic structures and contribute to economic growth in an ambivalent manner. The medium to long term aggregated impacts (which can be described as cumulative effects) linked to their mainstreaming in most parts of economic and social sectors are difficult to identify, because at each level of sustainable development the first and second order effects vary according to the country, the era, the sector, etc., as well as the scope of analysis and the type of IT innovations examined.

However, in view of the above, it appears that many positive externalities, not only at an environmental but also at an economic and social level, are to be expected from the mainstreaming of IT for green, and to a greater extend if green IT is to become mainstream too. If we are to combine IT for green with green IT to achieve an ecological economy (OECD, 2009), it is important to better understand the nature of eco-innovations that are likely to be generated from it.

2.1. Green IT and IT for green: What are we talking about?

Green IT refers to IT with low environmental impacts (in terms of first and/ or second-order effects).

We expect the IT sector to innovate in order to reduce its use of toxic substances and consumption of natural resources, especially energetic resources throughout their products and services' lifecycle. The European Commission is encouraging IT businesses to use eco-efficiency and eco-design processes (IP-09-393, March 2009) by implementing eco-labels and standards in the form of voluntary codes of conduct. Systemic improvements in production processes are sought throughout IT sector's entire value chain, including operations, manufacturing, service delivery and management of the supply chain. Increasingly, computer manufacturers are playing the green card and many of them have achieved the environmental standard ISO 14 004 (renovated in 2004). In France, collaborative projects have emerged between NGOs, local authorities and IT companies. This is the case with lifecycle extension policies based on the recycling of computers and mobile phones.

The term "IT for green" refers to the mainstreaming of IT in other sectors with, if we limit ourselves to the main applications within eco-city, smart buildings, intelligent transport or intelligent energy grids. It is these green applications, provided they resort to green IT, which are truly able to reduce the overall environmental footprint and especially to create structural change, enabling the well-known decoupling between economic growth and climate change. According to the Climate Group ( 2008), IT for green could significantly increase efficiency across all sectors of the economy and deliver CO 2 emission savings of 15% of the total of "Business As Usual" emissions in 2020. The IT sector has a powerful role to play by enabling other sectors to become more efficient by promoting dematerialisation, smart logistics, smart buildings and smart grids for instance.

As a case in point, a key motivation for the implementation of a smart grid is a more efficient use of existing electrical generation, transmission and distribution infrastructures. This could help the distribution sector improve its management of energy supply and demand. 15 A smart grid is presented as a set of software and hardware tools that allows generators to deliver energy more efficiently by reducing the need of surplus and enabling two-way paths and information exchange with consumers to address requests in real time. According to [START_REF] Rifkin | Engager la troisième révolution industrielle : un nouvel ordre du jour énergétique pour l'Union européenne du XXIe siècle[END_REF], the key to the future of energy lies in local decentralised energy production from renewable energy sources, which the smart grid integrates.

Finally, the smart grid's third objective is to control demand. Within the context of a collective platform developed around the management of incremental and radical innovations, industries, local authorities and individuals would then become producers as well as consumers of their own energy. This would occur based given pathways, irreversibility and discontinuous sources and unpredictable events. Electric Power Research Institute (EPRI), an America electricity sector think tank, concluded in its "Perspectives for the future" that this type of distributed production is bound to bloom in the same way the computer industry did. In future, producers and energy processors will have to work with IT specialists. For example, Intel invested over $100 million in 5 industrial electric grid industry companies to provide solutions for individuals and businesses with data centres or in the delivery of electricity and meters management. Intel is thus positioning itself at all levels of the energy sector, from energy production to its distribution and use. But how can heterogeneous parties, producing and using green IT, be defined as collective eco-innovation managers?

A typology of eco-innovation stemming from an economic approach to green IT for green

The definition of eco-innovation most commonly used within the ecological economics movement focuses on three points: an issue of double externality; the importance of a regulating framework; and the importance of social and institutional aspects of eco-innovation. The methodological pluralism drawn from ecological economics enables us to highlight eco-innovating green IT's following characteristics: § Type of innovation (or intensity). A spectrum of innovations ranging from incremental to radical, based on the degree of novelty associated to new practices. These time-based modifications are evaluated in terms of incremental or radical changes [START_REF] Freeman | The Economics of Hope[END_REF]. § The scope of innovation. Taking into account changes in production processes such as added eco-innovation, which intervenes in a curative manner, and integrated eco-innovation, which avoids environmental degradation (Frosh, 1995). Lock-in effect of technological trajectories, irreversibility and path dependencies or given technological trajectory are some of different aspects that need to be taken into account in green IT. § The nature of skills to be developed. Depending on the level and scope of innovation, the need for knowledge and new skills differs, thereby influencing the innovation process [START_REF] Nonaka | La connaissance créatrice[END_REF]. With the dissemination of IT, skills are developed at a distance and change the ways in which we acquire knowledge [START_REF] Miles | Network organizations: new concepts for new forms[END_REF] within dynamic capabilities 16 networks (as defined in [START_REF] Teece | Explicating Dynamic Capabilities: the Nature and Microfoundations of (sustainable) Enterprise Performance[END_REF]. This implies the need to develop organisations' coordination capacities as well as their ability to integrate mixed inputs into a group system through mindful contributions and representations [START_REF] Weick | Collective Mind in Organizations: Heedful Interrelating on Flight Decks[END_REF]. § Field of application. The scope of innovations' applications is analysed based on the need to take organisational, behavioural and institutional change into consideration, beyond the simple definition of technological innovation. As such, strategic innovations pertaining to green IT objectives or new modes of consumption as well as methods of production are defined (service economy).

Eco-innovation can effectively take on different forms and table 2 presents these characteristics for IT for green with green IT.

Insert Table 2: Characteristics of eco-innovations applied to green IT and IT for green.

The impact analysis of green applications of green IT has enabled the identification other key elements essential in defining eco-innovation in a management approach: § User dimension of eco-innovation. In order to develop eco-innovations, businesses should be able to anticipate the acceptance of innovations in the market. The conditions of acceptance can be seen at the production-diffusion of technology level as well in users' behaviour [START_REF] Pujari | Eco-innovation and new product development: understanding the influences on market performance[END_REF]. This dimension is drawn from a neo-institutional theoretical framework based on the development of collective agreements around the agreed upon dissemination of goods and services. Substitution/induction and rebound effects controlled or at least understood in order to provide a global impact assessment of IT. Within that context, the kinds of relationships between green IT producers and consumers must be taken into consideration in the economic analysis of eco-innovation. § Support for innovation. In some cases, eco-innovation is triggered by regulations through social pressure. In other cases, different competitive motivations prevail [START_REF] Porter | The Link Between Competitive Advantage and Corporate Social Responsibility[END_REF]Azzone and Nocci, 1998). Standard management of eco-innovation's double externality gives rise to technology that is dependent on technology push, market pull and regulatory push. All these elements have been identified in green IT, with an additional response to technological development: the development of a network that voluntarily combines actions and change their environment through regulatory mechanisms [START_REF] Astley | Collective Strategy: Social Ecology of Organizational Environments[END_REF]. Collective strategies thus defined can be seen as IT platforms. 17

Within that context, an analysis of eco-innovation highlights the dynamics pertaining to the organisation of innovation systems. The analysis of eco-innovation's determinants must be able to integrate the analysis of dynamic clusters of capabilities between producers and consumers of IT. A business ecosystems' theoretical framework [START_REF] Moore | The Death of Competition: Leadership and Strategy in the Age of Business Ecosystems[END_REF] is a useful tool to analyse additional characteristics of green IT, such as the "collective" eco-innovation, in as far as the added value comes from the proliferation of relationships, interactions amongst heterogeneous stakeholders with specific skills [START_REF] Cowan | The dynamics of collective invention[END_REF] and able to intervene at different levels and stages of IT's lifecycle.

These exchanges between producers and consumers of eco-innovation are the basis of a business ecosystem drawing on solid co-evolution processes between partners and a strategic approach that goes beyond a simple competitive business approach [START_REF] Lundvall | National Systems of Innovation[END_REF][START_REF] Freeman | The National System of Innovation in Historical Perspectives[END_REF]. Two additional criteria have been included in the typology of the so-called collective eco-innovations enabling the definition of a "platform" integrating rebound, substitutions and inductions effects linked to users' acceptance of IT:

Figure 1 summarises the position of some eco-innovations based on green IT and green applications for IT depending on all these criteria. We assess the dimensions of the selected eco-innovations by using a 1 to 5 rating Likert scale (where 0 means no change, 1 marginal and 5 radical change). Each eco-innovation could be characterised by these criteria as a mix of green IT and IT for green. Two ecocity examples are included in figure 1 to illustrate this typology and highlight the changing profiles of eco-innovations' determinants in relation to given digital business systems: Building Management System (BMS), smart grid. BMS aims to automate and take control of services in order to provide facilities in the most efficient way possible for businesses, within the constraints of an installed plant. BMS is a "stand alone" computer system that can calculate the pre-set requirements of a building and control the connected plant to meet those needs.

In terms of eco-innovation determinants, the profile examined highlights an innovation added in terms of production process and evolving through time with an issue of double externality (environmental externality's eco-efficiency and interoperable standards for R&D spill overs). But in relation to different stakeholders' acceptance criteria or those of other heterogeneous stakeholders 'emerging business model, this eco-innovation significantly lags behind. BMS is a holistic management system that offers tools that enable the reduction of energy consumption not reliant on users' behavioural transformation. Thus, according to the international studies already undertaken, the economic gains made won't be able to meet ecological economics' objectives.

A smart grid is an electricity grid that can intelligently integrate the actions of all the users connected to it -grid managers, IT technicians (middleware such as telecom or embedded systems), energy production experts, car manufacturers, builders, energy providers, unions, consumers and those that do both -, in order to efficiently deliver secure electricity supplies and greater control of energy needs. It does pertain to an organised cooperation between different sector parties, from a range of professions and with various strategic approaches enabling a better control of energy demand and supply. This collective innovation is also called open (as defined by [START_REF] Chesbrough | Open Innovation: The New Imperative for Creating and Profiting from Technology[END_REF]) in as far as a shared invention amongst competitors or other partners leads to sharing results and create new opportunities.

For example, in the medium-term, the electric car will take an important position within the smart grid market with a building-block development, probably within the construction sector.

Insert Figure 1: A variety of eco-innovations based on green IT and IT for green: some case studies It is worth noting that smart grids find a natural place within users' technological ecosystems that are situated at different levels of the energy supply chain: in the building industry, in the domestic sector as well as at the level of production means. Thus, a collective technological eco-innovation necessarily requires a social innovation reliant on the significant transformation of a particular way of life.

Conclusion:

Defining green applications of IT green as eco-innovation within a digital business ecosystem framework has highlighted new eco-innovations' determinants. Defining "user acceptance" and "innovation support" have enabled the description of new eco-innovation profiles linked to the creation of collective "platforms" for the collaboration of heterogeneous stakeholders. It is essential to integrate a management dimension within the theory of eco-innovation if we are to be better understand third order systemic effects.

Thus, based on our example, smart grids will foster change amongst grid managers to include relationship management of new economic partners (especially those from the IT sector) and a valorisation of their expertise that will lead to new services. However, the theoretical and empirical work on business ecosystems in the context of green IT is still in its infancy. These platforms impose new business models as well as a finer analysis of what fosters user acceptance, which will help better holistically assess these new technologies. Moreover, conditions for optimum allocation of costs between consumers and producers will need to be examined further. These questions won't find "universal" answers, because they are dependent on specific national regulatory contexts and each country's stated priorities. Thus, a range of level of cooperation amongst stakeholders participating in the same business network is essential:

cooperation amongst sector stakeholders is essential to support the emergence of new activities and the integration of players new to the field of energy production; cooperation between regulators, beyond the European borders, in order to learn from international experiences to better manage risks; finally, a support of technological, management and organisational public policy development is crucial to foster users' behavioural change. Incentive schemes such as green cards can facilitate adherence to such devices, offering a reward for green homes, by linking them to simple and fun individual power consumption control systems.

Figures and diagrams:

Figure 1 :

 1 Figure 1: A variety of eco-innovation based on green IT and IT for green: some case studies (extract from Faucheux et al. (2010))

Table 1 : The main eco-innovations allowed by IT for green in the field of a sustainable city

 1

	Areas of applications Applications		Economic perspectives
				This area benefits from an economic,
		• Regulation, metering, remote
				political and regulatory context which is
		management
				favourable at an international level,
		• Low consuming technologies
	Energy Efficiency			making it a very attractive market. The
		• Storage and management of
				USA, the countries of Northern Europe,
		micro-energy
				Germany and Japan have gained a head
		• Efficient distribution
				start.
				This is a huge market driven by an
		• Thermal modelling
				economic and a regulatory environment
		• Thermal, acoustic insulation
	Sustainable building			at an international level. It implies that
		• Intelligent	building,	home
				those in the building sector find new
		automation, remote management
				technological partners.
				The economic context is very
		• Solar and wind production
				favourable. These eco-innovations will
		• Hydrogen
				start to be widely distributed around
	Renewable energies	• Electricity storage
				2020. Europe is less advanced than the
		• Energy conversion
				USA or Japan in this area.
		• Decentralised distribution
				The economic regulatory and political
		• Sensors
				context is very favourable at an
		• Monitoring networks
				international level. This market will
	Clean transport	• Flow model
				expand rapidly from 2015. Europe,
		• Regulation, metering, remote
				especially France, is in a good position,
		management.
				but not ahead of Japan.

Table 2 : Characteristics of eco-innovations applied to green IT and IT for green

 2

The carbon footprint measures the amount of carbon dioxide (CO 2 ) emitted by burning fossil fuels, by businesses or by living beings.

Concerning the rebound effect,[START_REF] Pearce | Consuming myths[END_REF] highlights that improving energy efficiency doesn't necessarily lead to reduced energy consumption (quite the contrary) for a couple of combined reasons: the substitution effect (replacing cheaper energy with other energy commodities through a reallocation of income) and the income effect (cheaper energy makes money available for other energy commodities).

See the document referring to the European Technology Platform Smart Grid on http://www.smartgrids.eu.

Dynamic capabilities are defined as a business's capacity to integrate, build and reorganise internal and external competencies in order to better deal with changing environments.

[START_REF] Gawer | Platforms, Markets and Innovation[END_REF] defines industry platforms as technological building blocks that act as a foundation on top of which a group of businesses organised in a set of interdependent businesses sometimes called an industry ecosystem, develop a set of inter-related products, technologies and services.


F Maaroufi
email: fetenmaaroufi@yahoo.fr

H Camus

O Korbaa

A mixed integer linear programming approach to schedule the operating room

Keywords: health care, operating rooms, mixed integer linear programming, constraint programming

the problem studied in this paper is to allocate and to sequence the elective operation on operating rooms (ORs). We develop a mixed integer linear programming (MILP) model to solve this problem. Decisions in this model include the allocation of operations to material resources and human resources, the starting time of them and the starting time for each surgeon. To show the efficiency of this model, we decide to compare it with a constraints programming (CP) approach. The performance of these models is tested using a benchmark of the literature. The results indicate the efficiency of the MILP model compared with the CP model in terms of computational time.

I. INTRODUCTION

Operating room is the most critical resources in hospitals. It is the most precious and costly resources. ORs account for approximately 40 % of hospital's total expenses [START_REF] Jebali | Operating rooms scheduling[END_REF]. In addition, ORs contribute the largest amount of revenues to most hospitals [START_REF] Ghazalbash | Operating room scheduling in teaching hospitals[END_REF]. However, ORs draw their importance from their potential revenues and prohibitive costs for the society, patients and health care service.

ORs center in hospital always face problems in scheduling elective operations. In fact, these problems are among the complex encountered by healthcare organization, indeed they have to take many constraints into account, in particular those related to the availability of staff, materials and financial resources. In addition, demand for operation very often overwhelms supply therefore causing long waiting times for patients and reducing their quality of life. Therefore, OR manager are interested in finding new approaches to improve their surgical suite, which has encouraged the development of research in this domain.

This paper describes the problem of scheduling a known set of elective operations to OR. The scheduling decisions include two aspects: (1) assignment of surgery to induction beds, OR, recovery beds and surgeon, and (2) the surgery sequence within each material resource. A MILP model and a CP model are built to find a daily schedule that minimizes the Makespan which represents the completion time of the last patient's operation. This objective is studied in the literature of OT scheduling by [START_REF] Hanset | Using constraint programming to schedule an operating theatre[END_REF] and [START_REF] Ghazalbash | Operating room scheduling in teaching hospitals[END_REF]. The performance of these two models is tested using a series of computational experiments based on benchmark of the literature and the results show that the MILP model is more efficient than the CP model in terms of computational times. This paper is organized as follows. In the next section, we propose a literature review of the OR scheduling and we identify our contribution. A MILP model and a CP model are proposed in section 3. Section 4 compares the computational performance of the two proposed models. Finally, the paper ends with concluding remarks and future research prospects in section 5.

II. LITERATURE REVIEW

The OR daily scheduling problem studied in this paper consists of allocation elective operations on human and material resources and sequencing them within each material resource within a day planning horizon. Due to the high complexity of these two components, there are many papers ( [START_REF] Augusto | Operating theatre scheduling with patient recovery in both rooms and recovery beds[END_REF], [START_REF] Maaroufi | A VSCP approach for solving the operating theater scheduling problem, the first international conference on Reasoning and Optimization in Information Systems (ROIS[END_REF], [START_REF] Pham | Surgical case scheduling as a generalized job shop scheduling problem[END_REF], [START_REF] Roberto | A two level metaheuristic for the operatig room scheduling and assignement problem[END_REF] and [START_REF] Zaho | Scheduling elective surgeries with sequencedependent setup times to multiple operating rooms using constraint programming[END_REF]) decompose the problem in two sub problems: assignment operations and sequencing operations. In this paper, we address the studies which directly focus on deterministic programming approach and combining the allocation and sequencing phases in the same problem.

Mathematical programming models, especially integer and mixed integer programming, are the most approaches used in the literature to solve the OR scheduling problem. [START_REF] Marques | An interger programming approach to elective surgery scheduling[END_REF] Propose an integer linear programming (ILP) model to schedule a real case of elective operations from the waiting list on a weekly time horizon with the objective of maximizing the use of the surgical suite. The aim of the purposed model is to employ more efficiently the resources installed in the surgical suite of the hospital. [START_REF] Ghazalbash | Operating room scheduling in teaching hospitals[END_REF] Investigate the deterministic daily scheduling of surgical case problem. A new MIP is presented with the objective of minimizing the total idle times of ORs and the Makespan. With the MIP model, the authors determine the allocation of resources and the sequence of operations within OR and the start time of them. [START_REF] Koksalmis | How to schedule surgical operations into operating rooms? An application in Turkey[END_REF] Develop a mathematical programming approach to solve the surgical operations scheduling problem. They propose a MILP model to minimize the number of unscheduled surgical operation. The proposed model takes into account the constraints of human (surgeons) and material (ORs) resources. There are others papers propose a mathematical programming approaches and compare their performance with heuristics approaches, for instance [START_REF] Zaho | Scheduling elective surgeries with sequencedependent setup times to multiple operating rooms using constraint programming[END_REF] Use a RCPSP (Resource Constraint Project Scheduling Problem) to generate scheduling and planning of the surgical operations while focusing as much attention on human resources (surgeons) as on economic factors. They develop a MIP model including the planning and scheduling problem. They compare the results of MIP with a heuristic solution procedure based on genetic algorithm. [START_REF] Hanset | Using constraint programming to schedule an operating theatre[END_REF] Investigate the deterministic daily scheduling operating rooms problem for elective patient. They propose a constraint programming model to solve their problem taking into account some constraints on human (surgeons) and material (OR and recovery bed) resources and they compare the CP model with a MILP model.

Although these papers study the allocation and sequencing phases and resolve with mathematical programming approach, we cannot use those approaches because all of these assume that the human resources (surgeons) are already known in advance (i.e. the allocation of the human resources to operation is known) to reduce the complexity of the problem and in our approaches the allocation of the human resources (surgeons) are unknown. In addition, in this paper the operating theatre (OT) composes of induction beds, ORs and recovery beds; while these previous papers focus on the OR or\and the recovery beds. The new structure of the OT is studied in [START_REF] Maaroufi | A VSCP approach for solving the operating theater scheduling problem, the first international conference on Reasoning and Optimization in Information Systems (ROIS[END_REF] but the authors resolve the allocation problem with heuristic approach and propose a MILP model to sequence the operations into material resources.

The contributions made in this study are follows: we model the deterministic OT scheduling problem, integrating allocation and sequencing decisions in the same model; we consider surgeons, nurses, induction beds, ORs as well as recovery beds, as resources and we provide a more realistic model of the surgery process by explicitly considering the induction, the operations and the recovery tasks.

III. PROBLEM DEFINITION

Many paper focus on the ORs and recovery room when discussing OT scheduling problem. Furthermore, induction task is always performed in the OR. The contribution of the paper is to separate the induction and the operation task to improve the use of the ORs. With the new structure of the OT, the goal is to perform the induction task in induction room while the OR is prepared for another operation.

A MILP model is proposed to minimize the Makespan of the OT. To show the efficiency of the MILP model, we develop a CP model and we compare the results of the MILP with the CP model. Here are the notations used for the two proposed models. The criterion obj to optimize is the maximum completion time for operation in the OT. In order to obtain the most balanced operation schedule with smaller amount of opening hours in the OT on the day, we employ the Makespan of the OT. Constraints (1.4) ensure that an operation can be assigned to an OR only if it is opened and each operation is assigned to exactly one OR, respectively. Constraints sets (1.2) -(1.3) impose a daily operating time limit on each OR and surgeon. Constraints (1.5) -(1.6) ensure that each operation should be assigned to at most one induction bed and one recovery bed. Constraints (1.7) impose the minimal number of nurses who can participate in one operation. Constraints (1.8) and (1.9) ensure that a nurse does not overlap between operating rooms during the day. Constraints (1.10) are related to OR accessibility and verify that the operations happen in an appropriate OR.

A precedence relation exists between two operations if and only if they are assigned to the same OR (resp. induction beds, recovery beds, surgeons). This is enforced by constraints (1.11) - (1.22). The set of the constraints (1.23) and (1.24) define the precedence constraints. Constraints (1.25) and (1.27) ensure that an induction bed and a recovery bed cannot be occupied by more than one patient in the same time. The constraints (1.26) imply that an OR cannot be occupied by more than one patient. Constraints (1.28) verify that a nurse cannot participate in more than one operation at the same time. Constraints (1.30) ensure that a surgeon cannot operate more than one patient at the same time. Constraints (1.25) -(1.30) make sure that two operations do not overlap in time if their assigned resource (OR or surgeon or nurse) is the same. Observe that the constraints (1.26) are inutile if the operating room r is not assigned to o and p, respectively, since then θ o,p,r + OR o,r + OR p,r ≤ 1 and hence M (3 -θ o,p,r -OR o,r -OR p) is greater than the left-hand side because of a very large value of M. If the operating room r is assigned to o and p then the constraints (1.15) are necessary, depending on whether θ o,p,r =1 or θ o,p,r =0. For instance θ o,p,r =1, constraints (1.15) say that the operation p starts after the completion time of operation o with a minimum time tr (cleaning time of OR). The M parameter used is an upper bound on the surgery completion time, this value is sufficient to keep the constraints (1.25) -(1.31) inutile when necessary. Constraints (1.29) ensure that operation of a surgeon cannot be started before his or her arrival to the surgical suite. Constraints (1.19) ensure that the starting time of each operation cannot be more than the daily regular availability. Constraints (1.31) and (1.32) ensure that each surgeon operates during the interval of time in which he/she is available. Finally, the constraints (1.33) and (1.34) express the variables' domain.

B. a CP model

This section presents the CP model we build for solving the elective scheduling problem. In this model, time has a discrete representation as a set of time periods available for scheduling, {1…T}. This representation of time is used in the literature such as [START_REF] Hanset | Using constraint programming to schedule an operating theatre[END_REF] and [START_REF] Zaho | Scheduling elective surgeries with sequencedependent setup times to multiple operating rooms using constraint programming[END_REF] when they solve the scheduling problem with the CP mechanism. Let SA(s,t,r) represents the matrix surgeons availability. Each surgeon s expresses her/ his availability in time slot t in preference room r ϵ Rs; which represents the set of preference room of surgeons. Before formulating the problem, we define the set of binary variables: Here, constraints sets (2.2) and (2.3) impose a daily operating time limit on each OR and surgeon. Constraints (2.4) (resp. (2.6) and (2.7)) prevent the assignment of several overlapping operations in the same room (resp. the same induction bed and the same recovery bed). These constraints also present tr empty periods for room cleaning at the end of each operation. The set of constraints (2.5) guarantees that a surgeon is assigned to at most one operation at any time. The surgeons may exchange operating rooms. This exchange allows surgeons to work in another OR during hygiene periods in the previous room (about 15 min idle). This is also the reason why the cleaning time is not incorporated in the operations' duration. Constraints (2.8) ensure that an operation begins once and only once. Constraints (2.11) express that there are at least NM nurses in per operation. The constraints (2.9) (resp. 2.10) ensure that only one operation can stay in the induction bed (resp. recovery bed) at time slots t. The precedence constraints are described in the set of constraints ((2.12) -(2.13)). In constraints (2.14) every surgeon expresses her/his preference and the availabilities for certain time slots, the availability is presented by the matrix SA (s, t, r). Constraints (2.15) verify that the surgeon cannot be in two ORs by the same time. Constraints (2.16) ensure that the surgeons perform the preference operations. Constraints (2.17) are related to OR accessibility and verify that the operations happen in an appropriate ORs. The set of constraints (2.18) bound the limited capacity for OT in number of available hours. Constraints (2.19) express the variables' domains.

IV. EXPERIMENTAL RESULTS

This section presents a comparison between both proposed models described in section 3. These two models are implemented under Windows 8 with an Intel® Celeron® 1.4 GHz processor and 4.0 GB RAM. The MILP model is solved using IBM-ILOG-CPLEX 12.2. The CP model is based on the constraint programming method. It is solved by the solver included in the Java library CHOCO 3.0.0 using JDK 1.8. CHOCO is a library for constraint satisfaction problems (CSP) and CP and is based on a mechanism of propagation of instantiation with structures which use a "backtracking" algorithm. This solver is used by [START_REF] Hanset | Using constraint programming to schedule an operating theatre[END_REF] and [START_REF] Meskens | Multi-objective operating room scheduling considering desiderata of the surgical team[END_REF] for solving OR scheduling problem using a CP mechanism. These two models are evaluated by solving several problem instances described in Table IV where O denotes the number of operations and R, S, IB and B represent respectively the number of OR, surgeons, induction beds and recovery beds. The setup time for OR and surgeons is tr = ts= 15 min. For all ORs and all surgeons the regular operating time RAT=RATS= 480 min. For the CP model, the duration of the time slot is set to 15 min, thus creating 32 daily time periods in regular working time, whilst overtime is not provided for planning.

A. The comparaison of the two models

Table V summarizes the computational performance of the two models. The first column lists the number of the instances. The columns Variables and Constraints represent respectively, the number of variables and constraints in the two models. The Obj column shows the optimal objective value found when the program is terminate; and the CPU column is the computational time (in seconds) when the optimal solution is obtained. The performance of the two models is compared from four aspects. The results are shown in Table V. As we can see, the MILP model is efficient to solve the operation scheduling problem. Both the number of variables and constraints of the MILP model are smaller than the CP model. Partially due to the smaller number of constraints and variables, the MILP model is solved faster and can make the optimal solution compared with the CP model. For all instance, the MILP model is able to find the optimal solution in a reasonable time for this problem; in average the CPLEX solver take 700 seconds (11 minutes) to find the optimal solution.

We show that the optimal solutions found by the CP model are the same with the ones obtained by the MILP model. Nevertheless, if we look at the CPU time to obtain the optimal solution, we notice that the CP proves more computational times than the MILP model. We also notice that the more the instance has a large number of constraints, the more the values of the time computing is increase, which is normal. This shows us that the CP, when there is a large number of constraints, takes advantage of the parceling of the search space.

In this section, we compare an exact method (MILP) by an approximate method (CP). We push the CP model to find the optimal solution to compare with the MILP model in terms of computational times. We notice that The CP model uses more time to find an optimal solution unlike the MILP model which finds the optimal solution in a reasonable time. Therefore, to our problem, The MILP approach is sufficiently efficient to propose optimal solutions in a very short time and an approximately approach is not necessary.

B. The impact of the new structure of OT

In this section we compare two scheduling strategies: in the first, we assume that the induction of operation is performed in the OR. In the second strategy, the induction of operation is performed in the induction bed.

To test the two strategies, we use the problem instance n°3 where there are four ORs, six induction beds, six recovery beds and four nurses. The problem instance includes 13 operations performed by six surgeons over single day. In strategy 1, the Makespan is 525 minutes and in the second the Makespan is 450 minutes. We notice that in the first strategy we have 45 minutes overtime and with the new structure the Makespan is reduced and all operations are scheduled in a regular time of OT. We can see in fig. 1, when the induction is performed in the induction bed, the occupancy of the ORs is reduced. In this case we can add other operations in the daily planning and we can maximize the occupancy rate of ORs. Therefore the economic profit of OR can increase.

V. CONCLUSION

In this study, we present a MILP model for OR scheduling problem. This model takes into account the material (induction beds, ORs and recovery beds) and human (surgeons and nurses) resources. The main contribution of the paper is to solve the allocation and sequenced phases in the same problem and to perform the induction of operation in the induction bed.

To prove the efficiency of MILP model to solve the scheduling problem, we develop a CP model. These two models are evaluated using several problem instances and we push the CP model to find the optimal solution. The results show that the MILP model is more efficient than the CP model in terms of computational times. Thus, for this problem, the exact method is sufficiently efficient to find optimal solutions in a reasonable time.

To analyze the impact of the new structure of the OT, we compare two strategies scheduling: induction of operation is performed in the ORs or in the induction bed. According to the results, we show that with the new structure of the OT, the occupancy of the ORs is reduced which we can increase the number of planned operations in the planning day and maximize the occupancy rate of the ORs.

In this paper, we study the daily scheduling problem in a deterministic context. In the future work, it is necessary to take into accounts the urgent operations and to evaluate the robustness of the MILP model. Other suggestion for future research is to extend the proposed models by including other human resources such as the porters and the anesthetists.

Fig. 1 .

 1 Fig. 1. Charge of ORs in these two strategies

TABLE I .

 I Operation of type tp is operated in the room rA. a MILP modelThis section describes the MILP model for determining the daily surgical scheduling of electives patients. Let [A s , B s ] represents the interval surgeons availability. Each surgeon s expresses her/his availability which can operate on day; such as B s -A s = RATS s . A solution to the schedule problem is given by means of integer and binary variables.

		pbo tr ts Pretp,r	Duration of recovery of operation o OR turnover time between two consecutive operations Surgeon turnover time between two consecutive operations
		NOTATIONS
	O R IB B S NM NR Rs Os RATr RATSs pIbo po pIo	The total number of operation The total number of ORs The total number of induction beds The total number of recovery beds The total number of surgeons The number of nurses available for an operation in OR The total number of nurses nr The set of rooms preferred by the surgeon s The set of operation preferred by the surgeon s Regular Available Time for OR r Regular Available Time for Surgeon s Duration of induction of operation o Duration of operation o Induction time of operation o in the OR

TABLE II .

 II DECISION VARIABLES OF MILP MODEL SI o + pI o -M× (3-z o,p,Ib -IB o,Ib -IB p,Ib ) o,p ϵ {1..O}, o≠p, Ibϵ {1..IB} (1.25) SO p ≥ SO o + pIr o + p o + tr +Δ o -M × (3-θ o,p,r -OR o,r -OR p,r ) o,p ϵ {1..O}, o≠p, rϵ {1.

	w nr,r ≥ 1 -M × (2-OR o,r -NUR o,nr ) o ϵ {1..O}, nr ϵ {1..NR} (1.9) ∑ o=1 O ∑ tp=1 Type ∑ r=1 R OR o,r × pre tp,r =O (1.10)	SI p ≥ .R}	(1.26)
	θ o,p,r + θ p,o,r ≤ OR o,r o,p ϵ {1..O}, o<p, r ϵ {1..R} (1.11) θ o,p,r + θ p,o,r ≤ OR p,r o,p ϵ {1..O}, o<p, r ϵ {1..R} (1.12)	SB p ≥ SB o + pb o -Δ o -M × (3-α o,p,r -RB o,b -RB p,b ) o,p ϵ {1..O}, o≠p, bϵ {1..B} (1.27)
	θ o,p,r + θ p,o,r ≥ OR o,r + OR p,r -1 o,p ϵ {1..O}, o<p, r ϵ {1..R} (1.13) z o,p,Ib + z p,o,Ib ≤ IB o,Ib o,p ϵ {1..O}, o<p, Ib ϵ {1..IB} (1.14)	Integer variables Starting time of operation o SO p ≥ SO o + pIr o + p o + tr +Δ o -M × (3-θ o,p,r -NUR on,r -NUR pn,r ) o,p ϵ {1..O}, o≠p, nrϵ {1..NR} SOo SIo (1.28) Starting time of induction of operation o SBo Starting time of recovery of operation o Δo Duration of recovery of operation o in OR Ss Starting time of surgeon s Binary variables zo,p,Ib 1 if operation o starts before operation p in the induction bed Ib Θo,p,r SO o ≥ S s -M × (1-SUR o,s ) o ϵ {1..O}, s ϵ {1..S}(1.29) SO p + pIr p ≥ SO o + pIr o + p o + ts -M × (3-y o,p,s -SUR o,s -SUR p,s ) o,p ϵ O s , o≠p, s ϵ {1..S} (1.30) 1 if operation o starts before operation p in the OR r α o,p,b 1 if operation o starts before operation p in the recovery bed b yo,p,s 1 if operation o starts before operation p in the operation list of surgeon s IBo,Ib 1 if the operation o assigned to the induction bed Ib RBo,b 1 if the operation o assigned to the recovery bed b ORo,r 1 if the operation o assigned to the OR r NURo,nr 1 if the operation o assigned to the nurse nr SURo,s 1 if the operation o assigned to the surgeon s wnr,r 1 if the nurse nr is assigned to OR r A MILP model is then formulated as follows: obj = min (max (SB o +pb o -Δ o )) (1.1) SO w nr,r , OR o,r , IB o,Ib , RB o,b , NUR o,nr , SUR o,s ϵ {0,1}o ϵ {1..O}, s ϵ {1..S}, r ϵ {1..R}, nr ϵ {1..NR}, Ib ϵ {1..IB}, b ϵ {1..B} (1.33)
			∑ O o=1 p o ×OR o,r ≤ RAT r  r ϵ {1..R} SO o , SI o , SB o , S s ≥ 0 o ϵ {1..O}, s ϵ {1..S}	(1.2) (34)
		S} (1.20)	∑ o=1	Os p o ×SUR o,s ≤ RATS s  s ϵ {1..S}	(1.3)
	y o,p,s + y p,o,s ≤ SUR o,s o,p ϵ {1..O}, o<p, s ϵ {1..S} (1.21) y o,p,s + y p,o,s ≥ SUR o,s + SUR p,s -1 o,p ϵ {1..O}, o<p, s ϵ {1..S} (1.22)		∑ r=1 ∑ Ib=1 R OR o,r = 1  o ϵ {1..O} IB IB o, Ib ≤1 o ϵ {1..O} ∑ b=1 B RB o, b ≤1 o ϵ {1..O}	(1.4) (1.5) (1.6)
	SI o + pI o = SO o  oϵ {1..O}	(1.23)	∑ nr=1	NR NUR o,nr ≥ NM  o ϵ {1..O}	(1.7)
	SO o + pIr o + p o + Δ o = SB o o ϵ {1..O}	(1.24)		∑ r=1 R w nr,r ≤ 1  nr ϵ {1..NR}	(1.8)

z o,p,Ib + z p,o,Ib ≤ IB p,Ib o,p ϵ {1..O}, o<p, Ib ϵ {1..IB} (1.15) z o,p,Ib + z p,o,Ib ≥ IB o,Ib + IB p,Ib -1o,p ϵ {1..O}, o<p, Ib ϵ {1..IB} (1.16) α o,p,b + α p,o,b ≤ RB o,b o,p ϵ {1..O}, o<p, b ϵ {1..B} (1.17) α o,p,b + α p,o,b ≤ RB p,b o,p ϵ {1..O}, o<p, b ϵ {1..B}(1.18) α o,p,b + α p,o,b ≥ RB o,b + RB p,b -1 o,p ϵ {1..O}, o<p, b ϵ {1..B} (1.19) y o,p,s + y p,o,s ≤ SUR o,s o,p ϵ {1..O}, o<p, s ϵ {1..o + pIr o + p o -M× (1-SUR o,s ) ≤ B s o ϵ O s , s ϵ {1..S} (1.31) SO o + pIr o ≥ A s × SUR o,s o ϵ O s , s ϵ {1..S} (1.32)

TABLE III

 III OR o,r,t , IB o,Ib,t , RB o,b,t , NUR o,nr,t , SUR o,s,t ϵ {0,1}  o ϵ {1..O}, r ϵ {1..R}, s ϵ {1..S}, bϵ {1..B}, Ibϵ {1..IB}, t ϵ {1..T} (2.19)

				∑ o=1 O ∑ τ=t {1..T}	min(t+ p o	+ pIr o + Δ o + tr -1, T) OR o,r,τ ≤ 1r ϵ {1..R}, t ϵ (2.4)
				∑ o=1 O s ∑ τ=t	min(t+ p o + ts -1, T) SUR o,s,τ ≤ 1s ϵ {1..S}, t ϵ {1..T} (2.5)
				∑ o=1 O ∑ τ=t	min(t+ pI o	-1, T) IB o,Ib,τ ≤ 1Ib ϵ {1..IB}, t ϵ {1..T} (2.6)
				∑ o=1 O ∑ τ=t	min(t+ pb o -Δ o	-1, T) RB o,b,τ ≤ 1b ϵ {1..B}, t ϵ {1..T} (2.7)
					∑ r=1 R ∑ t=1	T OR o,r,t = 1  o ϵ {1..O}	(2.8)
					∑ Ib=1	IB ∑ t=1 T IB o,Ib,t ≤ 1  o ϵ {1..O}	(2.9)
					∑ b=1 B ∑ t=1	T RB o,b,t ≤ 1  o ϵ {1..O}	(2.10)
				∑ nr=1	NR ∑ t=1 T NUR o,nr,t ≥ NM  o ϵ {1..O} (2.11)
				∑ t=1 OR o,r,t  o ϵ {1..O} min(t+ pI o -1, T) ∑ Ib=1	IB (t+ pIo) × IB o,Ib,t ≤ ∑ t=1 T ∑ r=1 (2.12) R t ×
				∑ t=1 ∑ t=1 T ∑ b=1 min(t+ p o B t × RB o,b,t  o ϵ {1..O} + pIr o + Δ o -1, T) ∑ r=1 R (t+ po+ pIro+ Δo) × OR o,r,t ≤ (2.13)
				∑ o=1 O s ∑ τ=t {1..T}, r ϵ R	min(t+ p o	-1, T) OR o,r,τ ≤ SA(s,t,r) s ϵ {1..S}, t ϵ (2.14)
	. The CP model is then formulated as follows: DECISION VARIABLES OF CP MODEL ORo,r,t 1 if operation o starts in the OR r at time slots t IBo,Ib,t 1 if operation o starts in the induction bed Ib at time slots t RBo,b,t 1 if operation o starts in the recovery bed b at time slots t SURo,s,t 1 if operation o is performed by surgeon s at time slots t NURo,nr,t 1 if operation o is assigned to nurse nr at time slots t	∑ o=1 O s ∑ τ=t s ϵ {1..S}, t ϵ {1..T}, r ϵ R s min(t+ p o -1, T) OR o,r,τ = ∑ o=1 O s ∑ τ=t SUR o,s,t = 0  o ϵ {1..O}\O s , sϵ {1..S}, t ϵ {1..T} (2.16) min(t+ p o -1, T) SUR o,s,τ (2.15) ∑ t=1 T OR o,r,t ≤ pre r,tp  o ϵ {1..O}, r ϵ {1..R}, tp ϵ {1..TYPE} (2.17)
	∑ o=1 O ∑ t=1 T p o × OR o,r,t ≤ RAT r r ϵ {1..R}	(2.2)	∑ o=1 O ∑ t=1	T (t+ pb o ) × RB o,b,t ≤ T  bϵ {1..B} (2.18)
	∑ o=1	O s ∑ t=1 T p o × SUR o,s,t ≤ RATS s s ϵ {1..S} (2.3)

TABLE IV .

 IV

											Inst.7	15	6	9	9	9
				CHARACTERISTICS OF PROBLEM INSTANCES
	Instances N° Inst.1 Inst.2 Inst.3 Inst.4 Inst.5 Inst.6	9 11 13 15 11 13	O	4 4 4 4 6 6	R	6 6 6 6 9 9	S	6 6 6 6 9 9	IB	6 6 6 6 9 9	B

TABLE V .

 V THE COMPUTATIONAL PERFORMANCE OF THE TWO MODELS

	Instances N° Inst.1 Inst.2 Inst.3 Inst.4 Inst.5 Inst.6 Inst.7	variables 1935 2854 3953 5232 4232 5863 7762	MILP model constraints Obi (min) 4436 315 6626 375 9256 450 12318 480 9982 315 13935 330 18548 375	CPU (s) 4.93 125.74 1378.28 10816 variables 7488 9152 975.32 12480 23.51 13728 960.33 16224 1391.25 18720	CP model constraints Obi (time slots) 12160 21 14230 25 16280 30 18340 32 22833 21 25917 22 29001 25	CPU (s) 3202.15 7355.21 11058.7 14961.51 16541.22 22547.1 31047.85