Linda Zhang

Cheng Zheng

Liu Yang

Feng Chengpeng

N I Yuxiang

Xiong Shiyun

etc. X U Xiao

Keywords: Carbon emission reduction, policymaking, production planning, retailer selection, game theory, OR/MS approach, algorithms v Réduction d'émission carbone, définition de politiques, planification de la production, sélection de détaillants, théorie des jeux, recherche opérationnelle, algorithmes

IESEG School of

I am honored to have this opportunity to express my full gratitude to those who helped, supported and accompanied me during the past four years. This thesis was supported by a co-tutelage program between Lanzhou University (China) and Ecole Centrale Paris (France). I would like to thank the School of Management of Lanzhou University and Laboratoire Génie Industriel of Ecole Centrale Paris and their dean/head, Professors BAO Guoxian and Bocquet Jean-Claude, for this wonderful opportunity of undertaking this research and for having provided me with good working conditions. I am also honored by the participation of Professor BAO to the jury. I am grateful to other members of my thesis jury: to Professors KACEM Imed (Université de Lorraine, France) and WANG Zheng (Southeast University, China) for spending their valuable time on reviewing this thesis and producing review reports; to Professors MOUSSEAU Vincent (École Centrale Paris, France) for having accepted to take part in the jury to evaluate this work.

Particularly, I would like to offer my sincerest gratitude to my two supervisors, Prof. CHU Chengbin and Prof. YU Yugang, for giving me the opportunities of Ph.D. study, for teaching me the ethics and skills of academic research, and for helping me to finish this thesis.

Prof. CHU always took time out of his busy schedule to help me whenever I had any questions and ideas in research. He guided me in the combinatorial optimization area hand by hand and gave me insightful ideas when I came up against difficulties. His rigorous and meticulous scholarship impressed me deeply and will continue to positively influence my future research. He read the manuscript carefully and corrected the errors word by word.

Without his help, you could not see this thesis as what it is right now.

Many thanks to Prof. YU for his continuous support throughout my four-year Ph.D. study. I benefited a lot from his profound scientific knowledge and acute perception. He always provided me with different points of view, led me to a higher level of thinking and guided me to leap over obstacles in research. His positive and optimistic attitude, which always showed me the bright side of things, encouraged me to overcome the difficulties I faced in research and life. Table 1.1

List of Figures

List of Tables

Chapter 1

Introduction

. Research Background

Environmental issues become worldwide concerns as the increasing amount of CO 2 and other greenhouse gases (GHG) causes the phenomenon of global warming, which has serious effects on social and economic development around the world [START_REF] Barreto | Emissions trading and technology deployment in an energy-systems "bottom-up" model with technology learning[END_REF]. The international community has been trying to reach a consensus on carbon emission reduction, and some countries committed to international pledges to reduce or limit the growth of emissions by 2020 in the Copenhagen Accord in 2009 (see Table 1.1). These pledges are expected to be followed by multiple efforts to establish and implement domestic emission-reduction policies in these countries. For instance, the Chinese government pointed out, "in the face of global warming, we must develop lowcarbon economy, industry and lifestyle". Some other countries have also realized that lowcarbon economic growth must be integrated into their overall national development strategies [START_REF] Baeumler | Sustainable low-carbon city development in China[END_REF]. Conditional on all major economies joining a "fair and effective international framework with ambitious targets".

New Zealand 10% to 20% below 1990 level, conditional on a global, comprehensive agreement.

South Korea 30% below business as usual level.

United Kingdom 20% to 30% below 1990 level.

Moving above 20% is conditional on a global, comprehensive agreement for the period beyond 2012.

United States 17% below 2005 level.

Source: Productivity-Commission (2011).

On the other hand, population is more and more concerned about environmental issues.

As consumers, people are more and more aware of the environment effects of the products and the service they buy in addition to their prices. For these purposes, more and more retailers are providing carbon emission information on the products.

Governments are playing critical roles in reducing carbon emissions through emissionreduction policies. However, placing the burden of responsibility on the governments to reduce emissions does not preclude industrial or individual responsibility [START_REF] Soete | Escaping the greenhouse gas prisoner's dilemma: a government solution[END_REF]. As

shown in Figure 1.1, carbon emissions are generated over the whole supply chain satisfying customer demands. In more detail, carbon is emitted directly from energy consumption in each stage and indirectly from transportation activities connecting different stages in a supply chain. These stages include various partners involved in the supply chain, such as suppliers, manufacturers, distribution centers and retailers. Driven by governmental emission regulations and customers" green-awareness, all partners who emit carbon in such a supply chain are unavoidably involved in emission reduction. Efforts in carbon emission reduction are expected to slow down the climate change rate, but this requires long term investment and a sacrifice of short term benefits. As a consequence, emission reduction is in fundamental contradiction with economic growth [START_REF] Agf | Questionnaire on environmental problems and the survival of humankind[END_REF]. Governments in different countries are facing a trade-off between their national economic and environmental interests. This explains why some countries refused to sign the Kyoto Protocol and why the Copenhagen Accord failed to be formally adopted Government-imposed emission-reduction policies

Environmental consciousness

Force Incentives by COP15 (The 15th Conference of the Parties). For countries that committed emission reduction, their governments must establish appropriate policies to achieve their reduction targets at reasonable economic expense levels. On this viewpoint, the decision metric of governments should be the maximal social welfare including both economic and environmental utilities.

Given certain governmental emission-reduction policies, manufacturers who emit carbon in production are unavoidably concerned. Since governmental regulations pose significant constraints on manufacturers" production, a credible production and operation strategy that considers the emission limitation in production is essential to business success, especially for heavy-duty industries, such as thermal power, petroleum, steel, and cement industries.

These manufacturers have to consider governmental policies when making their long-term strategic or medium-term operational decisions, since these policies may significantly influence their decisions and further affect their profits or costs. In contrast, manufacturers" decisions bring economic income and consume emissions distinctly, furthermore, affect the social welfare. Therefore, it is important to optimize the government"s and the manufacturers" decisions to ensure social objectives and industrial benefits.

. Problem Description

With regard to the emission-reduction issues, at least two issues should be investigated:

governments" policymaking decision problem and manufacturers" production decision problem. As discussed in Literature Review in the coming chapter, few studies focus on governments" emission-reduction policymaking issues, and almost none of them consider the operational reaction of the policy receptor (e.g., the manufacturers considered in this research). Moreover, most of the literature contributes to the research area of economics.

Different from the existing research, we use model-based Operations

Research/Management Science (OR/MS) approaches to discuss the decision processes and optimize the decisions of every stakeholder. This research focuses on governments" policymaking problems (i.e., how to establish or adjust an emission-reduction policy) and manufacturers" production decision problems (i.e., how to cope with regulations from government and pressure from customers).

More specifically, this research considers the emission-reduction issues involving a local Рovernment and multiple manufacturers (i.e., manufacturinР companies) in a local reРion, in which all manufacturers plan their production under emission-reduction policies imposed by the government. It studies how the government determines her emission-reduction policies with an objective of maximizing the social welfare of the region, and how the manufacturers optimize their production planning under governmental policies with objectives of maximizing (resp. minimizing) their profits (resp. costs).

The decisions of the government and the manufacturers are briefly illustrated in Figure 1.2. The government first sets her emission-reduction policies to limit manufacturers" emissions and then manufacturers optimize their decisions to satisfy both the customer demands and the emission regulations. The government can observe the manufacturers" reactive decisions and assess the economic incomes and environmental impacts of the emissions related to the manufacturers" decisions. The government aims to maximize the social welfare of the region, while the manufacturers pursue their maximal profits or minimal costs. The optimal decisions of both the government and manufacturers can be obtained through this dynamic decision process.

Economic impacts

Environmental impacts

Government:

Policymaking to capture social objectives (social welfare)

Manufacturers:

Business decision making to capture industrial benefits

Emission-reduction policies

Strategic decisions or Operational decisions

Figure 1.2 Decision processes of government and manufacturers

In the decision process, the government"s policies influence manufacturers" decisions significantly. In contrast, the social welfare depends on manufacturers" decisions.

Therefore, it is important to consider the reactive decisions of the manufacturers when establishing an emission-reduction policy. This research focuses on this practical issue and investigates the decision problems for the government to establish emission-reduction polices, and for manufacturers to optimize their production planning under the governmentimposed polices. In what follows, these decision problems are described in more detail Chapter 1 from the viewpoints of the government and the manufacturers, respectively.

Decision problems for the government

This research considers the policymaking decision problem for a local government, who has exclusive decision power over a local region, such as a province and a city. The government determines her emission-reduction policies to regulate the production emissions of all manufacturers located in this region. The government has dual objectives when implementing an emission-reduction regulation: economic growth and environmental improvement. We indicate this dual-objective problem by a concept of social welfare consisting of economic and environmental utilities. In this regard, the decision problem of the government is to establish optimal policies to maximize the social welfare of the region.

The decision problem of the government can be briefly summarized as follows.

TСe Рovernment's decision problem is to optimally establisС emission-reduction policies witС an objective of maximizinР social welfare of tСe local reРion.

In practice, two basic types of policy instruments, including regulatory instruments and economic instruments, are adopted for emission reduction by governments. ReРulatory instruments are specific laws and regulations to limit emissions by force, such as emission caps, generation performance standards and emission standards. Economic instruments are economic incentives that generate voluntary emission reduction, such as emission taxes, subsidy policies and emission-allowance trading schemes.

Regulatory instruments have been widely applied. For example, many local governments in China have set up carbon emission maximums in their region to meet the national goal of adherence with the central Chinese government. In the USA, most states have similar regulatory instruments [START_REF] Stavins | Policy instruments for climate change: how can national governments address a global problem[END_REF][START_REF] Nam | Regulatory policy for manufacturers[END_REF]. European countries also established EU Emissions Trading System (EU ETS) as a basic platform to reduce industrial carbon emissions (European-Commission, 2012). Some countries or regions adopted a combination of these two instruments. In China, some major cities and provinces such as Beijing, Shanghai, and Guangdong initiated emission trading programs in early 2012 [START_REF] Xinhuawang | The meission-trade scheme will be implemented in seven pilot provinces and cities in China Available[END_REF]. In the USA, California has already built an emission trading system in 2012, and other western states have also been planning an emission trading scheme [START_REF] Burtraw | s new gold: a primer on the use of allowance value created under the CO 2 cap-and-trade program[END_REF]. Therefore, it may be expected that governments are now trying to develop more comprehensive policies to address the complexities of carbon emission reduction.

To summarize, this research considers two typical and practical emission-reduction policies for the government to limit or reduce the manufacturers" emissions: emission-cap regulation policy and emission cap-and-trade scheme.

Emission-cap regulation policy: In consideration of environmental bearing capacity, governments tend to limit the total amount of carbon emissions (i.e., an emission cap) in certain duration. An emission-cap regulation policy is favored by governments, since it is simple to establish and easy to handle. When the government sets such mandatory emission caps for the manufacturers, the manufacturers have to adjust their production planning and implement more environment-friendly or greener production technologies, to comply with these caps, since significant legal penalties are imposed otherwise. Note that, in this research, the concept of emission cap is different in long-term and medium-term planning of the manufacturers. For long-term planning, the government uses an emission cap to control the manufacturers" total emissions over the whole planning horizon. For mediumterm planning, the government sets emission caps to limit the manufacturers" emissions in each period, in order to consider the environmental bearability of the region.

An emission-cap regulation policy may bring negative economic utilities since the manufacturers have to adopt more expensive production technologies or simply reduce production to comply with the emission caps. Therefore, besides pursuing positive environmental utilities, the government should also consider the negative economic utilities caused by emission reduction and set emission caps appropriately for the manufacturers to maximize social welfare of the region. In this regard, tСe Рovernment's decision problem on tСe emission-cap reРulation policy is to optimize tСe emission cap for eacС manufacturer witС an objective of maximizinР tСe social welfare of tСe local reРion.

A successful emission-cap regulation policy relies on a strict but feasible emission cap that facilitates the best balance between emission reduction and economic effects. A cap set too high has no effects on environment improvement, but a cap set too low hinders the profitability of manufacturers if they find it too expensive to use green technologies.

Emission cap-and-trade scheme: Emission cap-and-trade scheme is a market-based emission-reduction policy, in which manufacturers are allowed to trade their emission allowances that are initially allocated by the government. Such a scheme is popular and effective in regulating carbon and other emissions in some countries or areas [START_REF] Dowdey | How carbon trading works[END_REF].

Under such an emission cap-and-trade policy, based on total allowances of the region, the government allocates some initial emission allowances (called emission cap in EU ETS) to all manufacturers in the region, and these emission allowances are tradable emission permits (or credits) which authorize emission rights to their holders. Note that, in order to distinguish the concept in the emission-cap regulation policy from that in the emission capand-trade scheme, we use the concept "initial emission allowance" to represent "emission cap", which is commonly used in EU ETS. Manufacturers have to reduce their emissions or purchase carbon credits if they anticipate a shortage of emission allowances, and they can also sell or bank their allowances if they anticipate a surplus. In this research, it is assumed that manufacturers sell out all their spare allowances at the end of a planning horizon. For each year, a manufacturer must surrender enough allowances to cover all of his emissions, otherwise heavy fines are imposed by the government (European-Commission, 2012). This research presents an allowance allocation mechanism to fulfill the initial emission allocation, where the government first sets an emission-reduction target (i.e., a percentage of emission reduction), and then allocates initial emission allowances to each manufacturer based on this target and the reduction baseline. It assumes that the emission trading market is efficient, such that the demand and supply information of emission allowances is available to all manufacturers in the region. All manufacturers plan their production according to the amount of initial and trading emission allowances they hold on hand and the carbon price. In this regard, tСe Рovernment's decision problem on tСe emission capand-trade scСeme is to optimize tСe emission-reduction tarРet witС an objective of maximizinР social welfare of tСe reРion.

A successful emission cap-and-trade scheme requires appropriate emission-allowance allocation to the manufacturers at the beginning of the planning horizon. If the initial allowances are too high, for instance, it will not have any effect on emission reduction. This is exactly what happened on the EU ETS from 2005 to 2007, when the level of initial emission allowances in 2007 increased by 8.3% from those verified emissions level in 2005, and carbon emissions actually went up [START_REF] Rizos | Do we really understand how carbon trading works[END_REF].

Decision problem for manufacturers

From the manufacturers" perspective, the decision problem is to optimize their production planning under a government-imposed emission-reduction policy. It is assumed that the manufacturers are homogenous in the same industry. Each manufacturer is equipped with a green and a regular production technologies and can cope with the emission limitation by choosing different technology for production. A regular technology normally emits carbon dioxide at a relatively high level. In other words, producing one unit product with a regular technology emits more carbon but cost less than with a green technology. Under given governmental policy, manufacturers are encouraged to optimize the combination of both technologies to achieve the best balance between carbon emissions and total production costs.

TСe manufacturer's decision problems are to optimize Сis lonР-term and medium-term

planninР under tСe Рovernment-imposed emission-reduction policies, witС objectives of maximizinР tСeir profits for lonР-term strateРic planninР, and minimizinР tСe production and operation costs for medium-term operational planninР.

Long-term planning:

In a long-term planning, manufacturers focus on decisions such as product designs, equipment and process choices, partner selection, and resource planning [START_REF] Enderle | A balanced concept of the firm and the measurement of its long-term planning and performance[END_REF]. This research considers a manufacturer"s strategic decisions for a 2-4 year long-term planning.

The manufacturer has a variety of retailers, through whom he supplies products to various geographic markets, while each retailer faces customers who are both price-sensitive and green-aware. Under an emission-cap regulation policy, the manufacturer"s production emissions are limited and might not well satisfy all candidate retailers willing to sell his products, but under an emission cap-and-trade scheme the manufacturer might also refuse the retailers that cannot bring profits to him, although he could get over the emission limitation through allowance trade. Thus, it is important to select appropriate retailers for cooperation in a long-term planning.

TСe manufacturer's decision problem for a lonР-term planninР is to optimize tСe carbon footprint, tСe wСolesale price of Сis product, and retailer selection under tСe Рovernmentimposed emission-reduction policy witС an objective of maximizinР Сis profit.

Medium-term planning:

In a medium-term planning, manufacturers focus on operational decisions such as material planning, technology arrangement, production quantities, and lot sizing [START_REF] Enderle | A balanced concept of the firm and the measurement of its long-term planning and performance[END_REF], aiming to satisfy customer demand requirements and government-imposed emission-reduction policies. This research considers a manufacturer"s operational decisions for a one-year medium-term planning.

Under governmental policies, the manufacturer should appropriately plan his production Chapter 1 8. How to optimize the market-based carbon price under an emission cap-and-trade scheme?

.

Contributions

This research aims at developing mathematical approaches and solution methodologies to solve the emission-reduction issues. The findings in this thesis could be applied by governments for establishing emission-reduction policies as well as by manufacturers for determining production planning under these policies.

The decision problems for both the government and the manufacturers are analyzed and formulated by model-based Operation Research/Management Science (OR/MS) approaches. The specific contributions of the thesis are summarized as follows.

Part I studies a manufacturer's decision problems botС in strateРic and operational levels.

On tСe strateРic level, we optimize the manufacturer"s corporate decisions on product design, product pricing and retailer selection. The decision problems are formulated as integrated Stackelberg game models incorporating government-imposed emission-reduction policy.

The price-sensitive and green-aware demand of the product is discussed in this research.

The green feature is considered in product design (i.e., to determine the carbon footprint of the product). The manufacturer"s production is driven by the customer demand that is a function of the retail price and carbon footprint of the product. However, in the literature, the market forces (i.e., the feature of customer driving) are largely ignored on emissionreduction issues [START_REF] Tang | Research advances in environmentally and socially sustainable operations[END_REF].

The retailer selection problem is analyzed under a frame of Stackelberg game, so that the decision process between the manufacturer and the retailers can be well described.

Moreover, with such a game model, maximal profits of both the manufacturer and the selected retailers could be achieved. The existing studies on partner selection focus mostly on the benefits of either the system coordinations or the different power structures among the stakeholders, whereas largely ignoring the benefits of both sides. Nevertheless, little literature on partner selection considers environmental issues in OR/MS research area.

The model formulated in this reserch is proved to be NP-hard. A hybrid algorithm taking the advantages of genetic algorithm, dynamic programming approach and analytical analysis method is developed to deal with this difficulty and solve the model efficiently.

On tСe operational level, the manufacturer"s decisions on production planning and technology selection are optimized, considering two types of emission-reduction policies, respectively. The manufacturer"s production in each period is constrained by a mandatory emission cap either imposed by the government in an emission-cap regulation policy or limited by the environmental bearing capacity in an emission cap-and-trade scheme. Therefore, the manufacturer should balance the production cost and emissions through a technology selection strategy, and optimize his production planning to minimize the overall cost.

Particularly, under an emission cap-and-trade scheme, the allowance trading strategy is optimized for the manufacturer. The equivalent global production cost function of the manufacturer is non-continuous, which makes it difficult to solve our models [START_REF] Keha | A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization[END_REF]. However, we develop a dynamic programming algorithm to solve the proposed models in polynomial time, based on mathematical properties we prove.

The studies closest to this research are the single item lot sizing problem. Although some researchers begin to pay attention to the problem incorporating emission issues, few of them consider either technology selection or production capacity (i.e., emission cap). We fill the gap in the research area and develop a polynomial algorithm to enhance the research on lot sizing problem.

Part II studies a Рovernment's policymakinР problems reРardinР two types of emissionreduction policies, respectively.

The government establishes or adjusts her emission-reduction policies with an objective of maximizing the social welfare consisting of economic and environmental utilities. The policymaking problems are analyzed and formulated as Stackelberg game models. With the models, the government can optimize her decisions by taking advantages of observing the manufacturers" reactive operational decisions, which directly determine the social welfare of the region. The mathematical models are at their advantages for analyzing the decision process between the government and the manufacturers, and for optimizing the decisions of multiple parties.

Under the emission cap-and-trade scheme, particularly, Cournot game competition model is formulated to optimize the market-based carbon price. Since the mathematical models are non-concave and analytically intractable, hybrid algorithms are developed to solve the models efficiently.

In this research, model-based OR/MS approaches are applied to analyze and optimize the government"s emission-reduction policies. The exising studies on emissions reductions mainly focus on the impacts of governmental policies, whereas largely ignoring how to establish or adjust such policies to improve the social welfare. Moreover, none of them considers such practical issues that the manufacturers" reactive operational decisions should be considered when the government establishes her emission-reduction policies.

. Thesis Outline

This thesis is organized as follows.

Chapter 2 provides a literature review of the related research. The gaps between the state of the art and the need of the real world are identified, and the relevance of the research is also pointed out.

Chapter 3 investigates the manufacturer"s long-term strategic decision problems under an emission-cap regulation policy. More precisely, the manufacturer"s decisions on carbon footprint, wholesale price and retailer selection are optimized by a Stackelberg game model. The objective is to maximize the manufacturer"s profit.

Chapter 4 discusses the manufacturer"s medium-term operational decision problems considering two types of government-imposed emission-reduction policies, respectively.

We optimize the manufacturer"s decisions on production planning and technology selection for a finite production planning horizon. In particular, the allowance trading strategy is considered under emission cap-and-trade scheme. The objectives are to minimize overall costs of the planning horizon.

Chapter 5 is devoted to optimize the government"s policymaking decisions on emissionreduction policies to maximize the social welfare of a local region. The emission caps and emission-reduction target are optimized for the emission-cap regulation policy and the emission cap-and-trade scheme, respectively.

Chapter 6 draws some conclusions of this research and discusses some potential future research directions.

Chapter 2

Literature Review

This chapter reviews the literature related to our research. As discussed in the previous chapter, the focus is on governments and manufacturers" decision problems in consideration of emission-reduction issues. As shown in Figure 2.1, studies on environment-related operations management and emission-reduction policies are most relevant to this work.

We first review relevant Operations Research/Management Science (OR/MS) research works incorporating environmental issues (especially carbon emission issues). Then, we go over the literature on emission-reduction policies with regard to our research. This chapter is organized as follows. Section 2.1 classifies the OR/MS research works into strategic and operational levels. On the strategic level, the research regarding partner selection and sustainable product design is reviewed. On the operational level, the research on production planning and technology selection is investigated. Note that technology selection on operational level is most relevant to the production planning problem with multiple production modes. Section 2.2 briefly reviews the literature on emission-reduction policy and points out the research gaps.

Emission-reduction issues

Interactive decision process

Manufacturers'decision problems Environmental operations management

Governments'decision problems

Emission-reduction policies

. Environmental Operations Management

This section reviews relevant literature regarding manufacturers" decision problems. The closest studies are related to sustainable operations management [START_REF] Kleindorfer | Sustainable operations management[END_REF] or sustainable supply chain [START_REF] Linton | Sustainable supply chains: An introduction[END_REF][START_REF] Seuring | From a literature review to a conceptual framework for sustainable supply chain management[END_REF][START_REF] Tang | Research advances in environmentally and socially sustainable operations[END_REF], which contribute to the operations management research on environmental issues with Operations Research/Management Science (OR/MS) methods [START_REF] Bloemhof-Ruwaard | Interactions between operational research and environmental management[END_REF]. Among these works, [START_REF] Seuring | From a literature review to a conceptual framework for sustainable supply chain management[END_REF] and [START_REF] Tang | Research advances in environmentally and socially sustainable operations[END_REF] provide brief research review from different viewpoints and classifications.

We review recent OR/MS research works related to this research in the following way, in which the literature is classified based on whether a strateРic or operational issue is investigated. The strategic (resp., operational) issue is related to the long-term (resp., medium-term) planning decision problems for the manufacturer in this research. More specifically, the strategic issue includes sustainable product design and partner selection, while the operational issue includes production planning and technology (or mode) selection.

In the following subsections, the first part (Subsections 2.1.1 and 2.1.2) deals with various strategic issues including partner selection and sustainable product design. The second part (Subsections 2.1.3) examines the operational issues consisting of production planning as well as technology selection.

. . Partner Selection

Under emission-reduction regulations imposed by the government, manufacturers face retailer selection issues since 1) appropriate retailers who bring profits to them should be selected for cooperation; 2) they may not supply all retailers willing to sell their products because of their limited production capacity caused by emission limitation. The relevant literature is mainly on partner selection issues in supply chain.

. . . Multi-criteria Approaches

The selection process involves the determination of quantitative and qualitative factors so as to select the most appropriate suppliers for cooperation, which ensure business competitiveness and sustainability. Consequently, the partner selection requires the consideration of multiple factors or criteria, and hence multi-criteria decisionmaking approaches are intensively investigated and applied both in academic research and in practice.

A large number of multi-criteria approaches have been proposed for supplier selection since its first discussion by [START_REF] Dickson | An analysis of vendor selection systems and decisions[END_REF], such as Analytic Hierarchy Process (AHP), Data Envelopment Analysis (DEA), Fuzzy Set Theory (FST), Simple Multi-Attribute Rating Technique (MART), etc [START_REF] De Boer | A review of methods supporting supplier selection[END_REF][START_REF] Aissaoui | Supplier selection and order lot sizing modeling: A review[END_REF][START_REF] Lung | An efficient and simple model for multiple criteria supplier selection problem[END_REF][START_REF] Ho | Multi-criteria decision making approaches for supplier evaluation and selection: A literature review[END_REF]. In what follows, we briefly introduce these approaches applied in partner selection.

a. Analytic (ierarchy Process A(P

AHP is one of the most intensively used multi-criteria decision-making approaches, which considers both tangible and intangible factors in a hierarchical manner [START_REF] Saaty | How to make a decision: the analytic hierarchy process[END_REF].

It provides a simple but systemic multi-criteria evaluation method for supplier selection.

The main idea is to rank suppliers by pairwise comparisons based on the score of the candidate alternatives. AHP structures a multi-objective and multi-criteria problem hierarchically, and then each level of the hierarchy separately is investigated [START_REF] Liu | The voting analytic hierarchy process method for selecting supplier[END_REF][START_REF] Vaidya | Analytic hierarchy process: An overview of applications[END_REF].

AHP is widely applied in supplier selection, such as [START_REF] Ghodsypour | A decision support system for supplier selection using an integrated analytic hierarchy process and linear programming[END_REF], [START_REF] Akarte | Web based casting supplier evaluation using analytical hierarchy process[END_REF], [START_REF] Chan | Interactive selection model for supplier selection process: an analytical hierarchy process approach[END_REF], [START_REF] Liu | The voting analytic hierarchy process method for selecting supplier[END_REF] and so on. Some studies integrate AHP with some other approaches to solve the supplier selection problem. [START_REF] Wang | Product-driven supply chain selection using integrated multicriteria decision-making methodology[END_REF] integrate AHP and preemptive goal programming model to investigate a supplier selection problem considering both qualitative and quantitative factors. AHP is also integrated with FST, DEA and some mathematical programming methods for supplier selection [START_REF] Kilic | An integrated approach for supplier selection in multi-item/multi-supplier environment[END_REF][START_REF] Pang | An integrated fuzzy synthetic evaluation approach for supplier selection based on analytic network process[END_REF][START_REF] Shaw | Global supplier selection considering sustainability and carbon footprint issue: AHP multi-objective fuzzy linear programming approach[END_REF].

b. Data Envelopment Analysis DEA

DEA has been proved to be an excellent tool in evaluating the performance of decisionmaking units since its outstanding ability to handle multiple conflicting attributes. The main disadvantages of DEA models are the ignored hierarchy and dependencies among criteria (Wu and Olson, 2010;[START_REF] Falagario | Using a DEA-cross efficiency approach in public procurement tenders[END_REF].

Because of the advantages of DEA, a large number of studies contribute to supplier selection and its related problems, such as [START_REF] Liu | Using data envelopment analysis to compare suppliers for supplier selection and performance improvement[END_REF], [START_REF] Talluri | A methodology for strategic sourcing[END_REF], [START_REF] Saen | A decision model for selecting technology suppliers in the presence of nondiscretionary factors[END_REF], [START_REF] Wu | Supplier selection: A hybrid model using DEA, decision tree and neural network[END_REF], etc. In addition, some literature develops evaluation and selection models based on integrated approaches of DEA [START_REF] Ramanathan | Supplier selection problem: integrating DEA with the approaches of total cost of ownership and AHP[END_REF][START_REF] Saen | A new mathematical approach for suppliers selection: Accounting for non-homogeneity is important[END_REF][START_REF] Ha | A hybrid approach to supplier selection for the maintenance of a competitive supply chain[END_REF].

c. Fuzzy Set Theory FST

Fuzzy set theory was first introduced by Zadeh to solve problems involving the absence of sharply defined criteria [START_REF] Zadeh | Fuzzy sets[END_REF]. FST is widely applied to investigate supplier selection problem, in which linguistic values are used to evaluate the supplier"s performances instead of numerical values [START_REF] Bevilacqua | From traditional purchasing to supplier management: a fuzzy logic-based approach to supplier selection[END_REF]. The disadvantage of FST models are the difficulty of evaluating membership function and the presence of various ways of determining fuzzy rules [START_REF] Ekici | An improved model for supplier selection under capacity constraint and multiple criteria[END_REF].

In addition, as an important variant of fuzzy theory, fuzzy AHP methods are proposed to solve various types of supplier selection problems [START_REF] Kahraman | Multi-criteria supplier selection using fuzzy AHP[END_REF]. Fuzzy AHP apply the concepts of fuzzy set theory and hierarchical structure analysis to present systematic approaches in selecting or justifying alternatives [START_REF] Bozbura | Prioritization of human capital measurement indicators using fuzzy AHP[END_REF]. A lot of research with regards to suppler selection solved by FST methods can be found in the existing literature, such as [START_REF] Lee | A green supplier selection model for high-tech industry[END_REF][START_REF] Ordoobadi | Development of a supplier selection model using fuzzy logic[END_REF], [START_REF] Amid | A weighted max-min model for fuzzy multi-objective supplier selection in a supply chain[END_REF][START_REF] Zeydan | A combined methodology for supplier selection and performance evaluation[END_REF], [START_REF] Chan | Global supplier selection: a fuzzy-AHP approach[END_REF], [START_REF] Chan | Global supplier development considering risk factors using fuzzy extended AHPbased approach[END_REF], [START_REF] Pang | An integrated fuzzy synthetic evaluation approach for supplier selection based on analytic network process[END_REF], etc.

In addition to these methods, some multi-criteria approaches such as Analytic network process (ANP) [START_REF] Jharkharia | Selection of logistics service provider: an analytic network process (ANP) approach[END_REF], Cluster Analysis (CA) [START_REF] Weber | Vendor selection criteria and methods[END_REF], Case-Based Reasoning (CBR) [START_REF] Watson | Case-based reasoning: A review[END_REF], Simple Multi-Attribute Rating Technique (SMART) [START_REF] Ho | Multi-criteria decision making approaches for supplier evaluation and selection: A literature review[END_REF], and Multi-Attribute Utility Theory (MAUT) [START_REF] Min | International supplier selection:: A multi-attribute utility approach[END_REF][START_REF] Sanayei | An integrated group decision-making process for supplier selection and order allocation using multi-attribute utility theory and linear programming[END_REF] are also widely applied for supplier selection.

. . . Mathematical Programming

Given an appropriate decision setting, mathematical programming allows the decisionmaker to formulate the decision problem as a mathematical model in order to maximize or minimize the objective by optimizing the variable(s) (e.g. the selection decision and the order allocation corresponding to each supplier). The mathematical programming approach has the advantages to well describe the real issues and obtain the satisfied solutions due to their ability to find a balance among some different, even conflicting, criteria.

Among such approaches, the following models are most commonly used in supplier selection: linear, mixed integer, multi-objective and goal programming models. In what follows, we investigate these approaches used in the existing literature.

a. Linear Programming LP

Linear programming is applied to solve a large variety of problems after it was first developed by Kantorovich in 1939[START_REF] Kantorovich | A new method of solving some classes of extremal problems[END_REF], especially its most common application on resources allocation. As a variant of resource allocation, supplier selection problem is extensively investigated with LP models in literature. [START_REF] Stanley | Linear programming in bid evaluation[END_REF] develop a mathematical discipline of linear programming to evaluate bids for government procurement. With their mathematical model, the over-all cost of the government is minimized by choosing appropriate contracts. [START_REF] Ghodsypour | A decision support system for supplier selection using an integrated analytic hierarchy process and linear programming[END_REF] integrate analytical hierarchy process and linear programming to discuss tangible and intangible factors in selecting the best suppliers and allocating optimal order quantities to them. Their model is suitable for supplier selection with and without capacity constraints. [START_REF] Talluri | Vendor evaluation with performance variability: A max-min approach[END_REF] consider performance variability measures in evaluating alternative suppliers. They propose a max-min productivity-based approach to identify the supplier groups for effective selection. Their decision model is transformed into two linear programming models, which aim to maximize the performance of a supplier against the best target measures set by the buyer. [START_REF] Ng | An efficient and simple model for multiple criteria supplier selection problem[END_REF] proposes a weighted linear programming model for the supplier selection to maximize the scores of suppliers. Similar to AHP, the decision makers need to determine the weightings of criteria of suppliers.

Most of the earlier models just focus on cost, quality and lead time issues, but not pay enough attention to carbon emission on supplier evaluation. [START_REF] Shaw | Supplier selection using fuzzy AHP and fuzzy multiobjective linear programming for developing low carbon supply chain[END_REF] is the first group of researchers considering environmental sustainability in supplier selection problem.

An integrated approach is proposed for supplier selection, where fuzzy-AHP and fuzzy linear programming is used to formulate their problem.

b. Mix )nteger Programming M)P

In regard to integer programming models, [START_REF] Kasilingam | Selection of vendors: A mixed-integer programming approach[END_REF] propose a mixedinteger programming model for a firm to select vendors by determining order quantities to minimize the costs of purchasing, transportation, receiving poor quality parts. [START_REF] Degraeve | An evaluation of vendor selection models from a total cost of ownership perspective[END_REF] formulate a supplier selection model based on the Total Cost of Ownership (TCO). With the real world data and case study, they point out that the model within inventory management is useful to reduce the costs of the system. [START_REF] Ghodsypour | The total cost of logistics in supplier selection, under conditions of multiple sourcing, multiple criteria and capacity constraint[END_REF] present a mixed-integer nonlinear programming model to solve the multiple sourcing problems in vendor selection focusing on minimizing the total cost. They transform the model into a pure non-linear programming by branching the integer variables, and substituting their values in the programming, and then solve the problem by Excel Solver. [START_REF] Talluri | A buyer-seller game model for selection and negotiation of purchasing bids[END_REF] proposes a 0-1 integer linear programming model to evaluate alternative supplier bids based on ideal targets set by the buyer, and to select the best bid aiming to achieve lowest cost. Except for focusing on the benefit of the buyer, the model also provides effective negotiation strategies for unselected supplier bids to make them competitive. [START_REF] Murthy | A framework for facilitating sourcing and allocation decisions for maketo-order items[END_REF] consider the vendor selection problem in a make-to-order supply chain. In their approach, a 0-1 integer linear programming model is formulated to minimize sourcing and purchasing costs under the capacity constraint. To solve the problem, they develop a heuristic procedure based on Lagrangian relaxation. [START_REF] Hong | An effective supplier selection method for constructing a competitive supply-relationship[END_REF] consider a multi-period procurement problem and present a mixedinteger programming model for the supplier selection problem. The model is to determine the optimal number of suppliers in a planning horizon and the optimal order quantity in each period, aiming to maximize the revenue of the buyer. In their model, suppliers" supply capacity and customer demands over a period are considered as varying features. [START_REF] Cao | Optimizing vendor selection in a two-stage outsourcing process[END_REF] propose a two-stage combinatorial optimization model for vendor selection issues. They develop a solution procedure to find the exact optimal solution of their model based on some properties of optimal solutions. [START_REF] Che | Cooperator selection and industry assignment in supply chain network with line balancing technology[END_REF] discuss a cooperator selection and industry assignment problem in supply chain networks. Based on the line balancing technology, they formulate a mathematical model, and a genetic algorithm is adopted with an objective of minimizing the total delivery delay loss. [START_REF] Li | Selection of contract suppliers under price and demand uncertainty in a dynamic market[END_REF] study a supplier selection problem considering the supply contract within non-stationary stochastic price and demand. They show that the duration of the contract is an import factor for the replenishment policy and selection decision. [START_REF] Mendoza | A serial inventory system with supplier selection and order quantity allocation[END_REF] develop a mathematical model for supplier selection and inventory control problems in a serial system. Their model is used to select the suppliers for the manufacturer and allocate orders to the selected suppliers. Recently, [START_REF] Zhang | Supplier selection and purchase problem with fixed cost and constrained order quantities under stochastic demand[END_REF] and [START_REF] Mansini | The supplier selection problem with quantity discounts and truckload shipping[END_REF] consider the quantity discounts and constrained order quantities in the supplier selection problem.

c. Multi-objective Programming MOP

Multi-objective programming allows the decision makers to have a heap of objective functions. MOP is widely used in supplier selection because a MOP model is effective in dealing with multiple and conflicting objectives. [START_REF] Weber | A multiobjective approach to vendor selection[END_REF] focus on a procurement issue and optimize the decisions of supplier selection and order quantities for the selected suppliers. A multi-objective programming model is formulated to analyze the tradeoffs among multiple criteria involved in the supplier selection problem. [START_REF] Hammami | Evaluating orders allocation within networks of firms[END_REF] propose a MOP model to select partners for an engineering project. In their model the submitted bids are evaluated with on quality, cost and delivery time considerations. In the model, multiple activities in the same bid and indirectcoordination cost of the buyer are not allowed. [START_REF] Liao | Integration of supplier selection, procurement lot sizing and carrier selection under dynamic demand conditions[END_REF] develop a MOP model considering supplier selection, procurement lot sizing and carrier selection decisions over a multi-period planning horizon, with an objective of minimizing the total logistic cost including the purchasing cost, the ordering cost, the inventory holding cost and the transportation cost and the late deliveries. In their model, capacity is considered over a whole planning horizon.

By considering multiple items, [START_REF] Narasimhan | multicriteria model for supplier selection with product life-cycle considerations[END_REF] discuss a procurement problem where a buyer purchases multiple products from the multiple suppliers, considering the products" different stages of the product life cycles (PLCs). They propose a MOP model to optimize supplier selection based on the relative importance of the criteria across multiple products over their PLC. [START_REF] Wadhwa | Vendor selection in outsourcing[END_REF] formulate the supplier selection problem as MOP models. A sourcing network is considered, in which one or more buyers procure multiple items from different suppliers. Three objectives, including price, lead-time and rejects, are considered in the model. They apply their models in a realistic example to compare and illustrate the results of different models.

Some studies integrate MOP with some other approaches to investigate supplier selection problem. [START_REF] Wu | An analytic network process-mixed integer multi-objective programming model for partner selection in agile supply chains[END_REF] integrate an analytic network process (ANP) approach and mix-integer multi-objective programming (MIMOP) method and formulate their problem as a two-stage approach, called ANP-MIMOP model. ANP is used to calculate the priorities of different criteria for supplier selection, while a MIMOP method is applied to determine the supply chain structure and the optimal allocation of order quantities based on the priorities obtained in the first stage. Wu et al. (2010) consider the risk factors in the supplier selection problem and propose a fuzzy multi-objective programming model to solve their problem. [START_REF] Jolai | Multi-objective model for multi-period, multi-products, supplier order allocation under linear discount[END_REF] propose a multi-objective mixed integer nonlinear programming model to investigate a supplier selection and order allocation problem, where a buyer orders multiple products from several suppliers in multi-period planning horizon. Dual objectives, consisting of maximizing the total quantities of purchase from suppliers and minimizing the total cost of purchase, are required by the buyer.

d. Goal Programming GP

As a branch of multi-objective programming optimization, goal programming (GP) is widely applied in partner selection. [START_REF] Karpak | An application of visual interactive goal programming: a case in vendor selection decisions[END_REF] discuss a supplier selection problem of a US original equipment manufacturing company. They formulate the problem as a goal programming model considering multi-criteria decisions. The objective is to select appropriate suppliers and allocate purchase orders among them with objectives of minimizing product acquisition costs and maximizing total product quality and delivery reliability. [START_REF] Wang | Product-driven supply chain selection using integrated multicriteria decision-making methodology[END_REF] integrate applied AHP method and GP model to study a supplier selection and order allocation problem, where AHP is used to choose a supplier selection strategy and then a pre-emptive goal programming (PGP) model is applied to optimize the purchase orders of the selected suppliers. [START_REF] Pati | A goal programming model for paper recycling system[END_REF] formulate a mixed-integer goal programming model to determine the facility location selection strategy considering a decision making framework of the multiitem, multi-echelon and multi-facility. [START_REF] Chang | Integrated multi-choice goal programming and multi-segment goal programming for supplier selection considering imperfect-quality and price-quantity discounts in a multiple sourcing environment[END_REF] integrate multi-choice and multisegment goal programming to solve a supplier selection problem considering imperfectquality and price-quantity discounts.

A great group of studies that integrate GP models with multi-criteria approaches (e.g., AHP, ANP, FST, etc.) can be found in the existing literature [START_REF] Büyüközkan | A novel fuzzy multi-criteria decision framework for sustainable supplier selection with incomplete information[END_REF][START_REF] Azadi | A new fuzzy goal directed benchmarking for supplier selection[END_REF][START_REF] Ho | On the location selection problem using analytic hierarchy process and multi-choice goal programming[END_REF][START_REF] Wang | Fuzzy multiple-goal programming for analysing outsourcing cost-effectiveness in hi-tech manufacturing[END_REF]. In these works, the multi-criteria approaches are commonly applied to score and identify the appropriate partner(s), while GP models are in charge of other decisions, such as order quantity allocation.

. . . Game Theory in Supply Chain

Game theories are useful to analyze the decision process when multiple players are involved in partner selection issues. However, few mathematical models within game theory that deal with the partner selection issues are formulated in the previous literature, although game theory has been widely used to analyze the interactive decision processes among firms in a supply chain [START_REF] Wang | A three-person game theory model arising in stochastic inventory control theory[END_REF][START_REF] Wang | Supply chain coordination when demand is shelf-space dependent[END_REF][START_REF] Granot | A three-stage model for a decentralized distribution system of retailers[END_REF][START_REF] Cachon | Handbook of Quantitative Supply CСain Analysis: εodelinР in tСe eBusiness Era[END_REF][START_REF] Slikker | Cooperation between multiple news-vendors with transshipments[END_REF][START_REF] Cai | An evolutionary game theoretic perspective on e-collaboration: The collaboration effort and media relativeness[END_REF]. [START_REF] Wu | Coordinating a supply chain with a vendor-managed inventory contract[END_REF] study the coordination in a one-vendor and one-retailer supply chain under a VMI (vendor managed inventory) contract. According to the contract, the vendor, as a Stackelberg leader, manages the retailer"s inventory and bears inventory holding cost; the retailer sells goods and determines the retail prices. Their results suggest that such a contract achieve optimal profit coordination between the vendor and the retailer, where the vendor and retailer freely interact between the vendor and its retailer. [START_REF] Bichescu | Vendor-managed inventory and the effect of channel power[END_REF] analyze a decentralized supply chain operating with a VMI agreement and a continuous review inventory policy. Among different channel power relationships, they find that when the vendor acts as the Stackelberg leader, the system incurs the lowest costs. Their findings also indicate that power concentration at the retailer leads to a higher cost than a system where the vendor is the leader. However, such a system is more efficient than those where power is equally distributed between the vendor and the retailer. [START_REF] Yu | A Stackelberg game and its improvement in a VMI system with a manufacturing vendor[END_REF] study a pricing problem in an inventory system where one manufacturer serves multiple retailers. In the system, the manufacturer purchases materials to produce products, and distributes them to the retailers. The retailers buy the products from the manufacturer at a wholesale price, and sells them at retail prices. Under the Stackelberg game frame, the manufacturer knows the retailers" complete information. The manufacturer also knows how to utilize the information to maximize his profit. Their analyses also show that both the manufacturer and the retailer can improve their profits using a cooperative contract. [START_REF] Viswanathan | Coordination in vendor-buyer inventory systems: on price discounts, Stackelberg game and joint optimisation[END_REF] models discount pricing decisions in a vendor-buyer supply chain using Stackelberg game. The results show that the leader"s optimal conditional strategy leads to a perfect coordination for the whole system. [START_REF] Chen | Channel coordination under consignment and vendor-managed inventory in a distribution system[END_REF] deal with coordination problems in a separated distribution system. By modeling decision -making with a Stackelberg game in cooperative and non-cooperative settings, they find that the non-cooperative decentralization leads to a higher retail price, less inventory and channel-wide profit.

By considering supplier selection issues, [START_REF] Talluri | A buyer-seller game model for selection and negotiation of purchasing bids[END_REF] use game theory to analyze the negotiation of bid selection and proposes an integer programming model to help the buyer to select optimal set of bids that satisfy its demand requirements. Their results

show that the model also assists in proposing effective negotiation strategies for unselected sellers enhancing their competitiveness. [START_REF] Laaksonen | Cooperative strategies in customer-supplier relationships: The role of interfirm trust[END_REF]

. . . Summary of Literature Review on Partner Selection

A summary of studies reviewed in this sebsection regarding supplier seclection is given in Table 2.1, in which the literature is classified according to the detailed reivews in the previous subsections. Among these studies, multi-criteria appoaches and mathematical programing methods are extensively applied to investigate the supplier selection problem.

However, little literature focuses on retailer selection.

Nevertheless, even for the supplier selection issues, most of the studies only consider the optimal objective of the buyer. Few papers like Gheidar [START_REF] Gheidar Kheljani | Optimizing whole supply chain benefit versus buyer's benefit through supplier selection[END_REF] consider the costs of both the suppliers and the buyer with an objective of minimizing the overall costs of the supply chain. The literature considering game theory focuses on either supply chain coordinations or different power structures between the vendor and retailers. There is an implicit assumption underlying these studies: supply chain partners (i.e., vendors and retailers) are pre-determined. In this regard, partner selection is rarely combined with game theory.

This research is different from the existing studies, it considers a retailer selection problem for a manufacturer, where retailers can optimize their decisions via reacting to the vendor"s decisions and the manufacturer can observe the reactions of the retailers under a frame of Stackelberg game. Both the manufacturer and selected retailers can maximize their individual profits through retailer selection.

In addition, although researchers are paying more and more attention on sustainble supply chain and green supplier selection, most of them apply multi-criteria approaches, such as AHP and FST [START_REF] Lee | A green supplier selection model for high-tech industry[END_REF][START_REF] Büyüközkan | A novel fuzzy multi-criteria decision framework for sustainable supplier selection with incomplete information[END_REF][START_REF] Shaw | Global supplier selection considering sustainability and carbon footprint issue: AHP multi-objective fuzzy linear programming approach[END_REF].

To the best of our knowledge, few studies on partner selection discuss environmental issues with mathematical programmig methods. Thus, this research tries to fill up these gaps.

Chapter 2

. . Sustainable Product Design

Sustainable product design in terms of carbon footprint is a necessary and important instrument to satisfy environmentally conscious customer demands and government regulation policies. Plenty of literature can be found in this topic, most of which focus on the functional design, manufacturing process design, material selection and so on. But, few OR/MS related works can be found on sustainable product design [START_REF] Tang | Research advances in environmentally and socially sustainable operations[END_REF].

However, we can find some model-based studies regarding product design. In the context of environmentally-aware market and emission-reduction policies, a good sustainable product design requires full trade-offs among functional performance, environmental impact [START_REF] Linton | Sustainable supply chains: An introduction[END_REF] and economic success [START_REF] Bloch | Seeking the ideal form: Product design and consumer response[END_REF]. [START_REF] Park | A knowledge-based approximate life cycle assessment system for evaluating environmental impacts of product design alternatives in a collaborative design environment[END_REF] develop a knowledge-based approximate life cycle assessment system (KALCAS) to evaluate the environmental impacts of product design alternatives. They try to seek an approximate life cycle assessment of product design alternatives with solid models in a collaborative design environment. [START_REF] Eichner | Product design and efficient management of recycling and waste treatment[END_REF] develop a general equilibrium model to analyze green design process and aim to investigate the impacts of policy instruments on the product design. Similar to [START_REF] Park | A knowledge-based approximate life cycle assessment system for evaluating environmental impacts of product design alternatives in a collaborative design environment[END_REF], the environmental factor is considered in their research.

With regard to the product design for manufacturing, [START_REF] Gupta | Priority evaluation of product metrics for sustainable manufacturing[END_REF] focus on the product design and present a framework to develop comprehensive product metrics for sustainable manufacturing and perform a priority evaluation of these metrics. A case study is provided to illustrate influencing factors for electronic products with an analytic hierarchy method. [START_REF] Wang | Design for sustainable manufacturing: applying modular design methodology to manage product end-of-life strategy[END_REF] present a methodological framework that applies modular design methodology to manage product end-of-life strategy systematically. Their objective is to maximize manufacturers" total value recovered from various product end-oflife strategies. They provide examples to demonstrate the applicability and effectiveness of the developed methodology.

Different from [START_REF] Gupta | Priority evaluation of product metrics for sustainable manufacturing[END_REF] and [START_REF] Wang | Design for sustainable manufacturing: applying modular design methodology to manage product end-of-life strategy[END_REF], [START_REF] Cachon | The value of fast fashion: Quick response, enhanced design, and strategic consumer behavior[END_REF] consider the customer response and investigate the issue of whether quick response and enhanced design are complements or substitutes in fast fashion product design. They develop a model of such issue and compare its performance among three alternative systems (i.e., quick-response-only alternative, enhanced-design-only and traditional systems). Their results show that it is important to consider the force of the market for product design. [START_REF] Kim | Product design with multiple quality-type attributes[END_REF] also consider customer reaction or market force for product design. They derive a measure of multi-dimensional customer preference and offer insights into the optimal product design considering multiple attributes. A mathematical model is formulated to optimize producer"s decisions on product pricing and product attributes for deferent segment markets, with an objective of maximizing producer"s profit. However, a horizontal product line is based on different ranking of quality dimensions for different types of customers, which needs not to be considered in our research.

With regard to the multiple attributes for product design, [START_REF] Krishnan | Designing a family of development-intensive products[END_REF] study development intensive products (designing a special class of products) for which the fixed costs of development far outweigh the unit-variable costs. Their results show that the traditional approach to product-line design developed for variable cost-intensive products does not carry over to development intensive products. For example, additional quality dimensions such as a product"s usability that the low-end customer segment cares about should be identified to win a low-end emerging market. After the research, [START_REF] Krishnan | Integrated product architecture and pricing for managing sequential innovation[END_REF] consider customers" utility in product design. They develop an integrated pricing and design approach to improve both firm profitability and consumer welfare through a modular upgradable architecture.

In the consideration of market force, [START_REF] Williams | Retail channel structure impact on strategic engineering product design[END_REF] investigate the impacts of retail channel structures on product design. They present a strategic framework that enables manufacturers to anticipate retailers" reactions to manufacturers" new designs in terms of retail and wholesale prices. Such a strategy helps manufacturers to understand how different channel structures impact the engineering design. In our research, a similar process is achieved by Stackelberg game analysis frame, in which the manufacturer observes costumers" reaction to his product design (i.e., carbon footprint) though retailers" demand function. However, [START_REF] Williams | Retail channel structure impact on strategic engineering product design[END_REF] do not consider the environmental factors in the product design.

Considering the green feature (i.e., production emissions) of a product as one quality attribute, [START_REF] Chen | Design for the environment: A quality-based model for green product development[END_REF] studies the green product design under the consideration of the interactions among the customers" preferences, the producer"s product strategies, and the governments-imposed environmental standards. They develop a quality-based model to analyze the strategic policy of product design with conflicting traditional and environmental attributes. Customers" preferences regarding ordinary and green product and producer"s strategic decisions regarding products" quantity, quality and price are considered in their model. To the best of our knowledge, Chen ( 2001) is one of the few works considering green feature of a product as one quality attribute for the product design in the OR/MS research.

In summary, a large stream of literature investigates the impacts of the environmental policies on the sustainable product design [START_REF] Eichner | Product design and efficient management of recycling and waste treatment[END_REF][START_REF] Park | A knowledge-based approximate life cycle assessment system for evaluating environmental impacts of product design alternatives in a collaborative design environment[END_REF][START_REF] Linton | Sustainable supply chains: An introduction[END_REF], but the force of market is not considered. Another important stream of studies consider customer reaction and market force in product design [START_REF] Kim | Product design with multiple quality-type attributes[END_REF][START_REF] Cachon | The value of fast fashion: Quick response, enhanced design, and strategic consumer behavior[END_REF]. However, the environmental factors are not involved in their works. In these studies, to the best of our knowledge, very few of them investigate the product design in consideration of both the environmental policies and the market force.

It should also be pointed out that our research is different from the existing literature. The major difference is that the government-imposed emission regulations are considered. Due to such regulations, the production of the manufacturer is limited by a capacity, which makes the problem more challenging (an NP-hard problem) but provides some interesting managerial insights.

In addition, this research assumes that the customer demands are both price-sensitive and green-aware, i.e., a trade-off between price and carbon footprint of the product should be made for product design. In other words, market force identified by the price and carbon footprint is considered in this research.

. . Production Planning

Production planning is commonly identified by the length of the planning horizon taken into account: long-term, medium-term and short-term production planning. Long-term planning usually focuses on the strategic decisions such as process and supply chain design, and equipment, resource facility choice, pursuing long-term benefits. Medium-term planning often determines production quantities and timing over a finite planning horizon, in order to minimize (resp. maximize) overall costs (resp. profits) while satisfying customer demands and capacity constraints. In short-term planning, day-to-day operational planning decisions are involved, such as job sequencing and material control.

This research mainly focuses on medium-term production planning considering manufacturing planning and inventory management [START_REF] Gelders | Production planning: a review[END_REF][START_REF] Mula | Models for production planning under uncertainty: A review[END_REF]. More specifically, the most relevant literature to ours is the lot sizing problem (LSP). The problem starts with the demand which is time-varying (also called dynamic demand). This demand is obtained from forecasting, or computed under MRP (material requirement planning) framework, and assumed to be deterministic. Lot sizing decisions consist of determining the production quantity of each type of products, so as to minimize production and inventory costs. It is important for a manufacturer to make appropriate lot sizing decisions to improve his performance and enhance his competitiveness. In what follows, we mainly review the literature regarding the lot sizing problem.

The research on lot sizing problem had been widely extended after it was first discussed by [START_REF] Wagner | Dynamic version of the economic lot size model[END_REF]. The existing works can be classified into several groups according to the following features, which distinctly affect the modeling and complexity of the problem.

 Planning horizon : finite or infinite

. Single-item Lot Sizing Problem

This subsection investigates the single-item lot sizing problem (SI-LSP). We first briefly review the uncapacitated single-item lot sizing problem (USI-LSP), and then go over the capacitated single-item lot sizing problem (CSI-LSP).

a. Uncapacitated Single-item Lot Sizing Problem a. Mathematical Model

The classical uncapacitated single-item lot sizing problem (USI-LSP) aims to determine single-item production planning, including the quantity and the timing for production, to satisfy deterministic but dynamic demand with an objective of minimizing the total costs, consisting of production and inventory costs, over a multi-period planning horizon.

Different from USI-LSP model, the well-known economic order quantity (EOQ) model [START_REF] Harris | How many parts to make at once[END_REF] requires that demand is at a stationary rate and the planning horizon is infinite, although EOQ is also used to balance the fixed order and the inventory costs.

a. Algorithms [START_REF] Wagner | Dynamic version of the economic lot size model[END_REF] first present an O(T 2 ) dynamic programming algorithm (W-W algorithm) to find an optimal solution for an uncapacitated lot sizing problem, where T is the number of periods in a planning horizon. After their work, researchers develop plenty of algorithms for solving problem and its variants, most of which are running in polynomial time.

Some works lower the computation burden of the W-W algorithm, such as [START_REF] Zabel | Some generalizations of an inventory planning horizon theorem[END_REF] and [START_REF] Eppen | Extensions of the planning horizon theorem in the dynamic lot size model[END_REF], but their improvements do not affect the worst-case computational complexity. However, researchers reduce the complexity to O(TlogT), which is independently obtained by [START_REF] Federgruen | A simple forward algorithm to solve general dynamic lot sizing models with n periods in O(n log n) or O(n) time[END_REF] and [START_REF] Wagelmans | Economic lot sizing: an O (n log n) algorithm that runs in linear time in the Wagner-Whitin case[END_REF]. [START_REF] Aggarwal | Improved algorithms for economic lot size problems[END_REF] further improve it to O(T) by a Monge matrix-search algorithm.

The variants of USI-LSP are extensively studied. [START_REF] Zangwill | A deterministic multi-period production scheduling model with backlogging[END_REF] consider a USI-LSP model with backlogging and production series and present O(T 2 ) and O(T 4 ) dynamic programming algorithms to solve the models respectively. [START_REF] Loparic | The uncapacitated lot-sizing problem with sales and safety stocks[END_REF] discuss a variant of the W-W model involving lost sales instead of fixed demands, and lower bounds on stocks. They develop as a dynamic programming algorithm to solve the model and give a complete description of the convex hull of solutions. Different from [START_REF] Loparic | The uncapacitated lot-sizing problem with sales and safety stocks[END_REF], [START_REF] Aksen | The single-item lot-sizing problem with immediate lost sales[END_REF] present an uncapacitated single-item lot-sizing model with lost sales, in which production cost and selling price are assumed to be time-varying. An O(T 2 ) dynamic programming algorithm is developed to find optimal solutions. Note that lost sales can be conceptually considered as quantity subcontracted or outsourced, while the latter practice is a common place in today"s globalized economy. Models considering outsourcing are studied in [START_REF] Chu | Polynomial algorithms for single-item lot-sizing models with bounded inventory and backlogging or outsourcing[END_REF].

Another stream of variants considers the time windows in lot sizing problem. [START_REF] Lee | A dynamic lot-sizing model with demand time windows[END_REF] study a dynamic lot-sizing problem considering demand time windows and backlogging. The O(T 2 ) and O(T 3 ) polynomial algorithms are developed to solve the problems without and with backlogging respectively. Similar to [START_REF] Lee | A dynamic lot-sizing model with demand time windows[END_REF], [START_REF] Hwang | Dynamic lot-sizing model with demand time windows and speculative cost structure[END_REF] also discuss a time-window lot-sizing problem, but speculative motive cost is considered in their model: the sum of the unit production and the inventory holding costs of a period is lower than the unit production cost of the next period. An O(nT 3 ) algorithm is provided to find optimal solutions, where n is the number of demands. Some other variants of USI-LSP like bounded inventory [START_REF] Gutiérrez | A new characterization for the dynamic lot size problem with bounded inventory[END_REF][START_REF] Chu | Polynomial algorithms for single-item lot-sizing models with bounded inventory and backlogging or outsourcing[END_REF][START_REF] Chu | A polynomial algorithm for a lot-sizing problem with backlogging, outsourcing and limited inventory[END_REF], perishable inventory [START_REF] Hsu | Dynamic economic lot size model with perishable inventory[END_REF] and bounded order (Okhrin and Richter, 2011a) are also intensively investigated in the recent literature.

b. Capacitated Single-item Lot Sizing Problem b. Mathematical Model

Different from its uncapacitated counterparts, capacitated single-item lot sizing problems (CSI-LSP) are characterized by the fact that the production quantity is limited in each period. In most production facilities, it is not realistic to assume that production capacity is infinite (or large enough to satisfy all the demands). Thus, it is important to consider the production capacity when determining the production plan.

b. Complexity

The complexity of CSI-LSP is investigated by [START_REF] Florian | Deterministic production planning: algorithms and complexity[END_REF] and [START_REF] Bitran | Computational complexity of the capacitated lot size problem[END_REF]. According to Bitran and Yanasse, the complexity of the CSI-LSP depends mainly on the parameter structure α/ / / , where α, , , and specify the structures of the setup cost, holding cost, production cost and capacity, respectively. The values of α, , and are identified by G, C, ND, NI and Z that represent general structure, constant, nondecreasing (over time), non-increasing (over time) and zero, respectively. For example, the notation NI/ND/C/G indicates a family of problem where the setup cost sequence is nonincreasing over time, the unit holding cost is non-decreasing over time, the unit production cost is constant and the set of capacities are not restricted to any pre-specified pattern.

Generally, the problem is NP-hard [START_REF] Florian | Deterministic production planning: algorithms and complexity[END_REF][START_REF] Bitran | Computational complexity of the capacitated lot size problem[END_REF], although some special cases can be solved polynomially, such as G/G/G/C, NI/G/NI/ND, NI/G/NI/C, C/Z/C/G, and ND/Z/ND/NI. However, it is not NP-hard in strong sense and pseudo-polynomial algorithm is developed for general case by Chen et al. (1994b).

b. Algorithms

Plenty of algorithms can be found in literature for solving CSI-LSPs. Exact algorithms are developed for polynomial and NP-hard cases. For the latter, the best algorithm that we can seek for are pseudo-polynomial since its NP-hardness. In addition, some heuristics also can be found in literature.

For special cases, dynamic programming is the most common approach to solve problem in polynomial time. For the G/G/G/C case, the general problem was solved by [START_REF] Klein | Deterministic production planning with concave costs and capacity constraints[END_REF] using an O(T 4 ) algorithm. [START_REF] Hoesel | An O(T 3 ) algorithm for the economic lot-sizing problem with constant capacities[END_REF] improve the result to O(T 3 ) when the production costs are concave and the holding costs are concave linear piecewise instead of linear. [START_REF] Bitran | Computational complexity of the capacitated lot size problem[END_REF] algorithms. [START_REF] Chung | An O(T 2 ) algorithm for the NI/G/NI/ND capacitated lot size problem[END_REF] and [START_REF] Heuvel | An efficient dynamic programming algorithm for a special case of the capacitated lot-sizing problem[END_REF] independently improve the complexity of the NI/G/NI/ND case to O(T 2 ). In particular, a geometric algorithm based on dynamic programming is developed by Heuvel and Wagelmans. Baker et al. (1978) and [START_REF] Lotfi | An algorithm for the single-item capacitated lot-sizing problem with concave production and holding costs[END_REF] consider CSI-LSP models with concave cost functions. Branch and Bound algorithms are proposed to solve their problems.

Besides special cases cited above, plenty of polynomial algorithms are developed for the variants of the standard CSI-LSP.

Bounded inventory: Inventory limitation occurs in many real life lot sizing problems. [START_REF] Love | Bounded production and inventory models with piecewise concave costs[END_REF] considers the upper bounds of inventory and develop an O(T 3 ) dynamic programming algorithm for solving the model. The similar problem is also discussed by [START_REF] Pochet | Lot-sizing with constant batches: formulation and valid inequalities[END_REF]. They consider that multiple batches of constant production capacity are available, while requiring a set-up cost. An O(T 3 ) algorithm is presented to find the optimal solutions. [START_REF] Sandbothe | Decision horizons for the capacitated lot size model with inventory bounds and stockouts[END_REF] Bounded order quantity. Okhrin and Richter (2011b) explore a capacitated single-item lot sizing problem considering minimum order quantity (i.e., the produced quantity must be greater than a minimum order quantity and less than the production capacity). The production and inventory costs are linear. An O(T 3 ) dynamic programming algorithm is developed to find optimal solutions. Different from Okhrin and Richter, Hellion et al. (2012) consider a similar problem but the production and inventory costs are concave. They propose an O(T 3 ) algorithm to solve the problem optimally. Gavish andJohnson (1990), Trigeiro et al. (1989), [START_REF] Roundy | Rounding off to powers of two in continuous relaxations of capacitated lot sizing problems[END_REF]Roundy ( ), (1986)), [START_REF] Zhang | A Lagrangian relaxation based approach for the capacitated lot sizing problem in closed-loop supply chain[END_REF][START_REF] Trigeiro | Capacitated lot sizing with setup times[END_REF], [START_REF] Chubanov | An FPTAS for the single-item capacitated economic lot-sizing problem with supply and demand[END_REF].

Note: *n is type of demand involved in production. c̄, d ̄ and q̄ are the average capacity, demand and number of pieces required to represent the production cost functions, respectively.

In the literature, pseudo-polynomial algorithms also play important roles in pursuing exact solutions for the NP-hard cases. [START_REF] Florian | Deterministic production planning: algorithms and complexity[END_REF] discuss a CSI-LSP model with general (not necessarily linear) cost function. The problem is NP-hard and they suggest a pseudo-polynomial algorithm with time complexity O(T 2 c̄d ̄), where c̄ and d ̄ are the average capacity and demand, respectively. More specifically, Shaw and Wagelmans (1998) consider a problem with piecewise linear production costs and general holding costs. They present a dynamic programming procedure with complexity O(T 2 q̄d ̄), where q̄ is the average number of pieces required to represent the production cost functions. Chen et al. (1994b) propose a dynamic programming algorithm that can deal with the most general problem (i.e., G/G/G/G case). Recently, [START_REF] Akbalik | Exact methods for single-item capacitated lot sizing problem with alternative machines and piece-wise linear production costs[END_REF] propose an exact pseudo-polynomial algorithm to solve a capacitated single-item lot sizing problem considering alternative machines and piecewise linear production costs.

Except for the exact algorithms, some heuristics also contribute much solving capacitated single item lot sizing problem efficiently, such as [START_REF] Gavish | A fully polynomial approximation scheme for single-product scheduling in a finite capacity facility[END_REF], [START_REF] Trigeiro | Capacitated lot sizing with setup times[END_REF], [START_REF] Roundy | Rounding off to powers of two in continuous relaxations of capacitated lot sizing problems[END_REF]Roundy ( ), (1986)), [START_REF] Zhang | A Lagrangian relaxation based approach for the capacitated lot sizing problem in closed-loop supply chain[END_REF][START_REF] Trigeiro | Capacitated lot sizing with setup times[END_REF] and [START_REF] Chubanov | An FPTAS for the single-item capacitated economic lot-sizing problem with supply and demand[END_REF]. A summary of algorithms for capacitated single-item lot sizing problem is given by Table 2.2.

. . . Multi-item Lot Sizing Problem

This subsection addresses the multi-item lot sizing problem (MI-LSP). Similar to single-item lot sizing problem, MI-LSP can be classified into two groups based on whether or not the production capacity is considered. In this section, we mainly focus on the capacitated multi-item lot sizing problem and provide a brief review.

a. Mathematical Model

Different from CSI-LSP, capacitated multi-item lot sizing problem (CMI-LSP) is characterized by the fact that multiple items need to be produced but a limited production capacity is imposed in each period should be considered. The problem is to determine the production quantity and timing for each item with minimal cost.

b. Algorithms

As referred in the previous subsection, general CSI-LSP has been proven to be NPhard. CMI-LSP is NP-hard in the strong sense [START_REF] Chen | Analysis of relaxations for the multi-item capacitated lot-sizing problem[END_REF]). That"s to say, it is unlikely to be able to develop any effective algorithms to find optimal solution for this problem. As a consequence, most algorithms are heuristics in the existing literature, except for a spot of well-known exact methods such as [START_REF] Barany | Strong formulations for multi-item capacitated lot sizing[END_REF] and [START_REF] Eppen | Solving multi-item capacitated lot-sizing problems using variable redefinition[END_REF]. These heuristic algorithms can be classified into three categories: common-sense or special-purpose heuristics, mathematical programming-based heuristics [START_REF] Maes | Multi-item single-level capacitated dynamic lot-sizing heuristics: a general review[END_REF][START_REF] Karimi | The capacitated lot sizing problem: a review of models and algorithms[END_REF] and metaheuristics (Jans and Degraeve, 2007a).

Common-sense or special-purpose Сeuristics: This category can be further classified into two groups, i.e., period-by-period Сeuristics and improvement Сeuristics. The first group of heuristics works from period 1 to T and is a single-pass constructive algorithm, in which a feedback scheme is dynamically adopted to make the constructed solution feasible; while the second group of heuristics starts with an initial solution (generated randomly) for the overall planning horizon, and then generate a better feasible solution in a greedy way [START_REF] Maes | Multi-item single-level capacitated dynamic lot-sizing heuristics: a general review[END_REF]. The period-by-period heuristics are simple and effective, therefore, are extensively investigated and used in academic research and practice. Some algorithms can be found in literature, such as [START_REF] Dogramaci | The dynamic lot-sizing problem for multiple items under limited capacity[END_REF], [START_REF] Maes | A simple heuristic for the multi item single level capacitated lotsizing problem[END_REF], [START_REF] Quadt | Capacitated lot-sizing and scheduling with parallel machines, back-orders, and setup carry-over[END_REF] and [START_REF] Li | An effective approach to multi-item capacitated dynamic lot-sizing problems[END_REF]. The improvement heuristics are widely studied in literature CMI-LSP and its variants, such as [START_REF] Park | An integrated approach for production and distribution planning in supply chain management[END_REF], [START_REF] Boctor | Heuristics for the N-product, M-stage, economic lot sizing and scheduling problem with dynamic demand[END_REF] and [START_REF] Wu | Mixed integer programming in production planning with backlogging and setup carryover: modeling and algorithms[END_REF].

εatСematical proРramminР-based Сeuristics: This category of heuristics commonly applies mathematically programming procedure to generate a feasible solution and improve it for obtaining an approximate solution. The mathematical programming-based heuristics most commonly used in literature include B&B-based heuristics [START_REF] Gelders | A branch and bound algorithm for the multi item single level capacitated dynamic lotsizing problem[END_REF]Hindi, 1995b;[START_REF] Absi | The multi-item capacitated lot-sizing problem with setup times and shortage costs[END_REF], relaxation heuristics (mainly including LP relaxation [START_REF] Almada-Lobo | Single machine multi-product capacitated lot sizing with sequence-dependent setups[END_REF] and Lagrangean relaxation [START_REF] Caserta | A cross entropy-Lagrangean hybrid algorithm for the multi-item capacitated lotsizing problem with setup times[END_REF][START_REF] Zhang | A Lagrangian relaxation based approach for the capacitated lot sizing problem in closed-loop supply chain[END_REF]) and some other heuristics [START_REF] Özdamar | An integrated Lagrangean relaxation-simulated annealing approach to the multi-level multi-item capacitated lot sizing problem[END_REF][START_REF] Hindi | An effective heuristic for the CLSP with set-up times[END_REF][START_REF] Federgruen | Progressive interval heuristics for multi-item capacitated lot-sizing problems[END_REF]Absi et al., 2013b). εetaСeuristics : Researchers paid much attention on meta heuristics in the past decades since these heuristics are commonly effective to solve optimization. For the lot sizing problem, especially for CMI-LSP, metaheuristics are intensively applied to deal with the NP-hardness of the problems. Some meta heuristics such as Genetic Algorithm [START_REF] Özdamar | Hybrid heuristics for the capacitated lot sizing and loading problem with setup times and overtime decisions[END_REF][START_REF] Kämpf | Simulation-based sequencing and lot size optimisation for a production-andinventory system with multiple items[END_REF][START_REF] Li | Heuristic genetic algorithm for capacitated production planning problems with batch processing and remanufacturing[END_REF], Simulated Annealing [START_REF] Barbarosoğlu | Analysis of solution space-dependent performance of simulated annealing: the case of the multi-level capacitated lot sizing problem[END_REF], Tabu Search (Hindi, 1995a[START_REF] Hindi | Solving the CLSP by a tabu search heuristic[END_REF][START_REF] Karimi | A tabu search heuristic for solving the CLSP with backlogging and setup carry-over[END_REF][START_REF] Toledo | Tabu search to solve the synchronized and integrated twolevel lot sizing and scheduling problem[END_REF], and their integrated/hybrid algorithms [START_REF] Özdamar | Hybrid heuristics for the multi-stage capacitated lot sizing and loading problem[END_REF][START_REF] Özdamar | An integrated Lagrangean relaxation-simulated annealing approach to the multi-level multi-item capacitated lot sizing problem[END_REF][START_REF] Xie | Heuristic genetic algorithms for general capacitated lot-sizing problems[END_REF] are widely used for finding approximate solutions for CMI-LSP.

. . . Variants of Lot Sizing Problem

To support our research, some other related variants of lot sizing problem need to be covered in literature review. In what follows, we investigate the lot sizing problems with piecewise cost structure, multiple production modes and emission constraints, respectively.

a. Piecewise Cost Structure

The cost structure is an important distinguishing feature for lot sizing problem, and has a significant influence on the solution methodology. In our research, the cost function is noncontinuous but piecewise linear in each continuous portion. Thus, this subsection investigates the studies where piecewise cost structure is considered.

To the best of our knowledge, [START_REF] Love | Bounded production and inventory models with piecewise concave costs[END_REF] first discuses a lot sizing model with piecewise cost structure. A single item production planning problem is discussed with deterministic demands and separable piecewise concave production cost. An efficient algorithm based on network flow is developed to find the optimal solution. Swoveland (1975a) considers a multi-period production planning model with piecewise concave production and holding cost. A property extended from [START_REF] Klein | Deterministic production planning with concave costs and capacity constraints[END_REF] is presented to solve the model. Chen et al. (1994a) propose a continuous dynamic programming approach for lot size models, in which production and inventory cost functions are assumed to be piecewise linear. Their approach can deal with cost functions such that convexity, concavity or monotonicity is not necessary. But their algorithm is pseudo-polynomial. [START_REF] Diaby | Dynamic lot sizing for multi-echelon distribution systems with purchasing and transportation price discounts[END_REF] study a lot sizing model for multi-echelon distribution system, in which general piecewise linear procurement cost is considered. A mixed integer linear programming model is formulated and solved by Lagrangian relaxation-based procedure. [START_REF] Chan | On the effectiveness of zero-inventory-ordering policies for the economic lot-sizing model with a class of piecewise linear cost structures[END_REF] consider a lot-sizing problem with a special class of piecewise linear ordering costs so-called all-unit discount cost function, which is a non-decreasing function of the amount shipped and the marginal cost is non-increasing. They prove this problem to be NP-hard. [START_REF] Akbalik | Exact methods for single-item capacitated lot sizing problem with alternative machines and piece-wise linear production costs[END_REF] study a capacitated single item lot sizing problem, in which alternative machines are used for the production and the production cost on each machine is piecewise linear. They prove that the problem is NP-hard and propose a pseudopolynomial dynamic programming algorithm to solve it. Akbalik and Rapine (2012) study a capacitated lot sizing problem with constant capacity constraint and stepwise cost structure.

They present several properties for the general problem and develop polynomial algorithms to solve their problem.

In summary, most of polynomial algorithms developed for the lot sizing models with piecewise cost structure are based on the assumption that the cost function is piecewise concave. Without this assumption, some pseudo-polynomial and heuristic algorithms are provided for finding exact or approximate solutions. Different from the existing literature, due to the emission constraint considered in our research, the production cost function is non-continuous piecewise linear function, which makes the models difficult to solve [START_REF] Keha | A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization[END_REF]. However, we develop a dynamic programming algorithm to solve the model in polynomial time, thanks to the mathematical property we prove.

b. Multiple modes

The technology selection problem in this research corresponds to lot sizing problem with multiple modes. From the viewpoint of operational issues, technology selection is to determine which equipped technology should be used for production, i.e., choose production mode/modes for each production period over a planning horizon. Under emission-reduction policies, technology selection is a consideration of the balance between carbon emissions and production cost.

A lot of works have been done in technology selection for strategic investment incorporating environmental policies [START_REF] Carraro | Environmental policy and the choice of production technology[END_REF][START_REF] Goyal | Strategic technology choice and capacity investment under demand uncertainty[END_REF][START_REF] Fischer | Environmental and technology policies for climate mitigation[END_REF]Boyabatli and Toktay, 2011a;Boyabatli and Toktay, 2011b). However, only little literature focuses on the operational issues that how to arrange these equipped technologies in production. [START_REF] Gong | Optimal production planning with emissions trading[END_REF] study a multi-period production planning problem with emission trading scheme. The emissions trading, technology choice, and production strategies are optimized to minimize the overall costs. In summary, only few studies [START_REF] Jaruphongsa | A dynamic lot-sizing model with multi-mode replenishments: polynomial algorithms for special cases with dual and multiple modes[END_REF] and Sandra Duni ( 2009))

consider the a lot sizing problem with multiple modes. Although some relevant studies regarding technology selection on operational level can be found in the existing literature, few works consider the environmental issues.

c. Emission Constraints

As investigated in existing literature, few studies (almost none) consider environmental issues when studying multi-period production planning problem (or lot sizing problem).

However, some related brief reports can be found in the recent academic conference.

. . . Summary of Literature Review on Production Planning

With regard to lot sizing problems with piecewise cost structure, concavity is required by most studies when developing polynomial algorithms for the related models. In this research, the production cost is even non-continuous due to the emission constraint in production, thus a new algorithm is needed to develop for the proposed problem.

Regarding the production planning problem with multiple modes, only few studies, like [START_REF] Jaruphongsa | A dynamic lot-sizing model with multi-mode replenishments: polynomial algorithms for special cases with dual and multiple modes[END_REF] and [START_REF] Akbalik | Polynomial time algorithms for the constant capacitated single-item lot sizing problem with stepwise production cost[END_REF], consider that multiple (or two) production/replenishment modes may be used in production. Nevertheless, the former does not consider setup costs and replenishment (i.e., production) capacity in model; the latter proposes a pseudo-polynomial algorithm.

In addition, to the best of our knowledge, few works consider the environmental issues in operational decisions of production planning. Only brief reports can be found in the recent academic conference [START_REF] Absi | Lot-sizing with carbon emission constraints[END_REF][START_REF] Absi | Analysis of green lot-sizing problems[END_REF][START_REF] Heuvel | Finding pareto optimal solutions for the multi-objective economic lot-sizing problem[END_REF][START_REF] Montréal | The economic lot-sizing problem with an emission constraint[END_REF]. After these groundbreaking discusses, some related studies can be found in the recent literature, like [START_REF] Benjaafar | Carbon footprint and the management of supply chains: insights from simple models[END_REF] and Absi et al. (2013a). The former proposes a series of traditional lot sizing models and solve them by CPLEX; the latter develops a polynomial algorithm to solve their model but production capacity is unlimited. Table 2.3 provides a brief summary of the literature most relevant with our research.

Our contribution

This research studies the production planning problem in consideration of the emission constraint and can be formulated as a capacitated model with multiple modes, in which the production cost function is non-continuous. Although the emission constraint makes the model difficult to solve, we try to develop a polynomial dynamic programming algorithm to find the optimal solutions.

. Emission-Reduction Policies

In this section, we review relevant research regarding governments" decision problem that how to establish or adjust the emission-reduction policies. By examining the literature on environmental issues and their related policies in OR/MS research, little research focuses on adjusting or optimizing the existing policies for governments, especially local governments, although there is massive literature incorporating environmental concerns in economics, dating back to at least the 1970s.

An important stream of literature is to investigate the differences and the impacts of different policy instruments [START_REF] Wu | The relative efficiency of voluntary vs mandatory environmental regulations[END_REF][START_REF] Löschel | Technological change in economic models of environmental policy: a survey[END_REF][START_REF] Hepburn | Regulation by prices, quantities, or both: a review of instrument choice[END_REF][START_REF] Sambodo | Investigating the impact of carbon tax to power generation in java-bali system by applying optimization technique[END_REF][START_REF] Parag | Policy attribute framing: A comparison between three policy instruments for personal emissions reduction[END_REF]. There is a large number and diverse range of emissions-reduction policies in place or in the process of being implemented (Productivity-Commission, 2011). These policies could be classified as being either reРulatory or economic, i.e., direct reРulatory and incentive-based instruments, respectively. Some most common policies are given in Table 2.4. 2011) and [START_REF] Goulder | Instrument choice in environmental policy[END_REF].

These studies provide plenty of valuable findings such as the social costs of carbon and its reduction [START_REF] Pearce | The social cost of carbon and its policy implications[END_REF], social welfare related to emission reduction [START_REF] Malueg | Welfare consequences of emission credit trading programs[END_REF][START_REF] Hediger | Sustainable development and social welfare[END_REF][START_REF] Moledina | Dynamic environmental policy with strategic firms: prices versus quantities[END_REF], efficiency of these policies on emission reduction [START_REF] Wu | The relative efficiency of voluntary vs mandatory environmental regulations[END_REF][START_REF] Böhringer | Unilateral climate policy design: Efficiency and equity implications of alternative instruments to reduce carbon leakage[END_REF], policy instrument choice [START_REF] Goulder | Instrument choice in environmental policy[END_REF][START_REF] He | Simulated annealing and tabu search for multi-mode project payment scheduling[END_REF], etc.

Another important stream of literature focuses on allowance/carbon credit trading issues. This is due to the fact that cap-and-trade schemes are the most popular way to regulate emissions [START_REF] Dowdey | How carbon trading works[END_REF]. A lot of work emerges in this research area, especially related to allowance allocation [START_REF] Burtraw | Allocation of CO 2 emission allowances in the regional greenhouse gas cap-and-trade program[END_REF][START_REF] Hahn | The effect of allowance allocations on cap-and-trade system performance[END_REF][START_REF] Zhao | Long-run equilibrium modeling of emissions allowance allocation systems in electric power markets[END_REF] and carbon price [START_REF] Keeler | Sequestration rental policies and price path of carbon[END_REF][START_REF] Ho | Impact of carbon price policies on US industry[END_REF][START_REF] Feng | Carbon price volatility: Evidence from EU ETS[END_REF]. Some other literature related to economics and politics of carbon emissions/climate change also has an important position in the research regarding emission-reduction policies [START_REF] Hausker | The politics and economics of auction design in the market for sulfur dioxide pollution[END_REF][START_REF] Baron | The economics and politics of regulation: perspectives, agenda, and approaches. εodern political economy: old topics[END_REF][START_REF] Griffin | Global climatechange: The science, economics and politics[END_REF][START_REF] Mackenzie | Making things the same: Gases, emission rights and the politics of carbon markets[END_REF].

Government policies can provide regulations or incentives into the market, but the problem of quantifying the impact of specific government policies on business decisions is not yet well-studied [START_REF] Skerlos | Sustainable design engineering and science: Selected challenges and case studies[END_REF], especially on operational decisions [START_REF] Benjaafar | Carbon footprint and the management of supply chains: insights from simple models[END_REF]. Nevertheless, there are few quantitative models that deal with the policy adjustment/optimization issues under the consideration of firms" operational reaction to these policies. This research tries to fill this gap. We analyze a local government"s decisions on optimizing emission-reduction policies appropriately and manufacturers" operational decisions by a Stackelberg game frame, with which the government can adjust her policies dynamically by observing the optimal reaction of manufacturers. The problem is formulated as an integrated mathematical model with OR/MS approach.

Chapter 3 Carbon Footprint, Wholesale Price and Retailer Selection for Manufacturer under Carbon Emission-Reduction Policy

This chapter focuses on long-term strategic decision problems for a manufacturer under the emission-cap regulation policy imposed by the government. More specifically, the decisions on carbon footprint, wholesale price and retailer selection are optimized with the objective of maximizing the profit under an emission-reduction policy.

. Problem Description and Notation . . Problem Description

This chapter seeks to optimize a manufacturer"s long-term (e.g., 2-4 years) decisions including carbon footprint, retailer selection as well as wholesale price under a government-imposed emission-cap regulation policy. The overall objective is to maximize the manufacturer"s profit.

The manufacturer produces a single type of product and distributes these products to multiple retailers at the same wholesale price. The manufacturer charges transportation costs to the retailers which are determined according to the retailers" geographic distance from the manufacturer, and might provide retailers with market promotion fees. The manufacturer also has complete information on the demand of his potential retailers when deciding the wholesale price. Retailers are able to set retail prices when serving their customers that are both price-sensitive and green-aware. The demand is function of the retail price and carbon footprint. Thus, price and carbon footprint are the only two distinguishing features of this functionally homogenous product. In this research, the carbon footprint of a product is measured by the emissions from producinР one unit product.

It is assumed that the manufacturer is equipped with two production technologies: reРular tecСnoloРy and Рreen tecСnoloРy noted as tecСnoloРy-r and tecСnoloРy-Р, respectively. Green technology reduces the manufacturer"s carbon emissions but creates higher costs per product. Therefore, the manufacturer has an incentive to use a combination of both technologies to achieve the optimal balance between carbon emissions and total production costs. To serve customers" needs, the manufacturer has to switch to green production from regular production if he is incurring a shortage of carbon emission permits due to government-imposed emission-reduction policy. Let m denote the percentaРe of products produced witС tСe Рreen tecСnoloРy in a long-term planning, e r and e Р the emissions from producinР one unit product witС tСe reРular and Рreen tecСnoloРies, respectively Then, the carbon footprint of unit production can be measured by The manufacturer"s production capacity is restricted by a mandatory emission cap imposed by the government, and therefore he has to choose retailers from those who are willing to cooperate. For the sake of convenience, such cooperation between the manufacturer and his retailers is denoted as a buy-sell system. It is assumed that there are sufficient retailers willing to join the system. In this case, the manufacturer has to make a selection decision on the potential retailers. In brief, during long-term planning, the major decisions for the manufacturer include the percentage of products produced by the green technology (i.e., carbon footprint), the wholesale price, and retailer selection.

The decision problem is formulated as a two-stage Stackelberg game model, where the manufacturer and retailers pursue their respective maximal profit. In the Stackelberg game, the manufacturer, as a leader, selects retailers who bring profit, while the retailers, as followers, are willing to join the system only when retailing is profitable.

The manufacturer tries all of his possible alternative decisions and receives responses from his candidate retailers. And then he chooses the one that generates maxima profit as the optimal solution where all selected retailers bring profits to him. The buy-sell system can be built with two-stage dynamic interactions between the manufacturer and the candidate retailers. The decision processes are presented briefly as follows.

The manufacturer first assigns a set of values to the carbon footprint and the wholesale price, and then he receives all retailers" reactions. Each retailer determines whether to cooperate or not, and determines her prospective retail price if she does. The manufacturer then is able to know the retail prices for all cooperating retailers, and can calculate the total profit from this set of values. Then the manufacturer can repeat this process by assigning a different set of values until it reaches an optimal decision when any deviation fails to his profit. The system reaches a so-called Stackelberg equilibrium when it reaches the optimal situation. At this point, neither the manufacturer nor the retailers are willing to deviate from the equilibrium as this equilibrium is optimal for both parties in the system.

A mathematical model is formulated for this problem, but it is necessary to explain the notation before being described.

. . Notation

The notation used throughout this chapter is as follows:

Parameters

. Problem Formulation and Solution Methodology

This section studies the manufacturer"s decision problem for a long-term planning under the emission-cap regulation policy. The problem is first formulated as a Stackelberg game model, and then a hybrid algorithm is developed to solve the model based on the decision analysis of the manufacturer and retailers.

. . Mathematical Model

. . . Mathematical Formulation

The problem described above suggests the manufacturer can achieve optimal decisions by a Stackelberg game, in which he is able to observe the optimal responses of the potential retailers. In this game, the manufacturer makes decisions first and then retailers follow by optimal reactions. To formulate such a mathematical model, we first derive the objective function of the manufacturer and some constraints of his decisions.

Since carbon emissions result from productions by the manufacturer, ""emissions per unit of production"" is a normal indicator of environmental quality in many industries [START_REF] Sundarakani | Modeling carbon footprints across the supply chain[END_REF]. In lieu with [START_REF] Yalabik | Customer, regulatory, and competitive pressure as drivers of environmental innovation[END_REF], we similarly assume there is a negative relationship between the carbon footprint and customer demand when all things else are equal. Without loss of generality, we also assume consumers are pricesensitive. We, thus, define the demand function of retailer i by the following linear form

  , ( 1
) i i m i i i i m r m g D p K a p b e e             . (3.2.2)
where K i is a constant representing retailer i"s market scale. a i and b i represent the price elasticity and carbon-footprint elasticity of the product on customer demand, respectively.

The price elasticity gives the percentage change in quantity demanded in response to a one percent change in price. The price elasticity implies the sensitivity to the product price, and has a negative relationship with the customer demand. The carbon-footprint elasticity implies the preference of the customers on green products. The higher the carbon-footprint elasticity, the greener product the customers prefer to select.

(1 )

m r m g e e e
    is the carbon footprint of the product, which implies that a higher the percentage of products produced by the green technology is required for a greener product. Note that we use e in our research to represent the carbon footprint of product. As stated in the problem description, a green technology has to be involved in production. m is, therefore, set to be 0 < m ≤ 1, i.e., the production turns to be infeasible if m = 0.

The production cost of the manufacturer is a function of m . Then, the production cost function is given by

  , (1 )
m m m m r m g m g Q p p Q         , (3.2.3) where   1 , n m i i i m i Q x D p    
is the total demand from selected retailers and is equal to the total production quantity. With the production cost function, the manufacturer has to tradeoff between his production cost and the carbon footprint by m .

The net profit of the manufacturer equals revenue minus total costs. The revenue comes from the payment from the retailers purchasing the product at a wholesale price c p , which is calculated by

  1 , n m i i i m p i R x D p c     . (3.2.4)
The total cost includes production cost, transportation cost, and market promotion investments as illustrated by

1 1 1 ( , ) (1 ) ( , ) n n n m i i i m m r m g i i i m i i i i i i TC x D p p p x D p x                      1 1 ( , ) (1 )
n n i i i m m r m g i i i i i x D p p p x                   (3.2.5)
According to above analysis, we obtain the objective function of the manufacturer:

  1 1 1 ( , ) ( , ) (1 ) n n n m i i i m p i i i m m r m g i i i i i i x D p c x D p p p x                          1 1 ( , ) (1 )
.

n n i i i m p m r m g i i i i i x D p c p p x                    (3.2.6)
We then formulate the Stackelberg game model, consisting of mixed-integer linear programming models at two levels (i.e., two Sub-models). The mathematical model, called

Model MR-3-I, is stated as follows.

TСe upper level for the manufacturer to make decisions can be achieved by the first Submodel (named Sub-model M), including Eqs.(3.2.7)-(3.2.10). In this Sub-model, the manufacturer maximizes his net profit by optimal decisions on c p , m and x, from observing the optimal reactive decisions of the retailers.

Sub-model M:

Maximize   11 , , ( , ) (1 )
, 1)

x nn m p m i i i m p m r m g i i i ii c x D p c p p x                  (3.2.7) Subject to 1 ( , ) (
n i i i m m r m g i x D p e e E           , (3.2.8) , {0,1}, 1, , i i i x y x i n     , (3.2.9) 0, 0 1 p m c     , (3.2.10)
where the objective function (3.2.7) maximizes the profit for the manufacturer. Constraint (3.2.8) implies that production is strictly limited by the government-imposed emission cap.

Constraint (3.2.9) suggests that the manufacturer can accept/decline a retailer only when the retailer is willing to join in the system. Constraint (3.2.10) gives the bounds of the wholesale price and the percentage of products produced by the green technology.

TСe lower level for each retailer to make decisions can be achieved by the second Sub-

. . . Problem Complexity

In this subsection, the following theorem is first given to show the NP-hardness of the problem, and then the difficulties to solve the proposed model are pointed out.

Theorem 3.2.1 Optimally solvinР x is already NP-Сard, even wСen tСe variables of all otСer variables are known. In otСer words, solvinР εodel εR-γ-I is NP-Сard.

Proof. Let us omit the decisions variables c p and m , and just consider the retailer selection problem. That"s to say, the decision variables y, p, c p and m are fixed.

Then, the decision for the manufacturer is reduced to solely selecting the candidate retailers into the system under the emission allowance limitation. Simultaneously, the problem is simplified into a 0-1 Knapsack Problem, which has been proven to be NP-Сard [START_REF] Gary | Computers and intractability: A guide to the theory of NP-completeness[END_REF]. The proof is complete. ■

The theorem above implies that the proposed Stackelberg model is difficult to solve.

Even worse, in the model, solving x should be repeated many times. Because the reaction of the retailers changes with a change in the manufacturer"s decision on c p and m in order to obtain the Stackelberg equilibrium. The objective function (3.2.7) is not concave in c p and m since the function value may increase or decrease with y and x as shown in our numerical examples. The reason embedded is that y and x are not continuous, which makes

1 n i i i i x y D   discontinuous.
In the following sections, we analyze properties of optimal solutions and develop a hybrid algorithm to cope with the NP-hardness and the non-concavity of the considered model.

. . Solution Methodology

This section analyzes optimal decisions for both the manufacturer and each retailer, respectively. Based on the these analyses, the retailers" decision variables p and y can be obtained analytically, while the manufacturers" decision variables c p and m can be computed numerically by genetic algorithm (GA) since x can be optimally solved by dynamic programming (DP) for any given values of c p and m . Finally, all variables are obtained by a hybrid algorithm integrated these methods.

. . . Optimal Decisions of Retailers

Retailers" decisions are presented by Sub-model R. The decisions of retailers depend upon the decisions of the manufacturer, thus the following analysis for optimal y * and p * is based on any given c p or m .

For a retailer to enter the system, i.e. y i =1, the necessary and sufficient condition is that

(p i -c p )D i (p i , m
) is maximized and furthermore both (p i -c p ) and D i (p i , m ) should be strictly positive.

To maximize (p

i -c p )D i (p i , m ) =   ( ) (1 )
i p i i i i m r m g p c K a p b e e         
 , a concave function of p i , the unique optimal retail price in reaction to the wholesale price c p and the carbon footprint m , is given by

    * ( , ) (1 )
p i i m r m g i i p m c K b e e a yc                
(3.2.17)

. . . Optimal Decisions of the Manufacturer

Given that the manufacturer can dynamically optimize his decisions from observing the optimal responses of retailers, we analyze manufacturer decisions by taking advantage of those analytical decisions of retailers.

Substituting Eqs. (3.2.15)-(3.2.17) into Eq. (3.2.6), we obtain the manufacturer"s actual objective function:

'* 1 1 ( , ) (1 )
.

n n m i i p m p m r m g i i i i i x D c c p p x                   (3.2.18)
where * ( , )

i p m
Dc  given by (3.2.16) is the optimal decision of retailer i, which can be observed by the manufacturer and is constant for any given c p and m .

Then, the decision model of the manufacturer Sub-model M can be reformulated into Sub-model M-I as follows.

Sub-model M-I

Maximize

  '* 11 , , ( , ) (1 )
,

x nn m p m i i p m p m r m g i i i ii c x D c c p p x                  (3.2.19) Subject to   * ( , ), 0,1 , 1, , i i p m i x y c x i n      , (3.2.20) * 1 ( , ) (1 )
,

n i i p m m r m g i x D c e e E             (3.2.21) 0, 0 1 p m c     , ( 3

Sub-model M-II

Maximize

  * ' 1 ( , ) 1 ,, i p m m p m i i in yc c A x       x (3.2.23) Subject to * * 1 ( , ) 1 ( , ) (1 )
i p m i i p m m r m g in yc x D c E e e               , (3.2.24)
where

* (1 ) ( , ) i p m r m g i i p m i A c p p D c                is constant.
The remaining problem is a classical knapsack problem: the candidate retailers for selection in the buy-sell system correspond to the candidate items for selection in a knapsack problem. Their optimal demand rates (i.e., * ( , )

i p m
Dc  ) correspond to the volumes of items while the production capacity (i.e.,

m r m g E e e        (1 )
) of the manufacturer corresponds to the capacity of the knapsack. The value of each item (retailer) i is given by A i . Thus, Sub-model M-II is a 0-1 Knapsack Problem which is NP-Сard [START_REF] Gary | Computers and intractability: A guide to the theory of NP-completeness[END_REF].

Fortunately, the NP-hardness caused by the variable x is not in the stronР sense. Thus, we have an opportunity to solve x * (c p , m ) in pseudo-polynomial time by using a dynamic programming (DP) algorithm [START_REF] Martello | Dynamic programming and strong bounds for the 0-1 knapsack problem[END_REF], which is discussed in detail in the next section.

. . . Hybrid Algorithm

In light of the complexity of our problem, a hybrid algorithm is developed to solve the proposed model, coping with the NP-hardness, non-concavity, and analytical intractability of the model. In the hybrid algorithm, an intelligent algorithm, genetic algorithm (GA), is introduced to solve c p and m numerically. The retailer-related decision variables are solved analytically, and the manufacturer-related decision variables x are optimally solved by a dynamic programming algorithm.

Genetic Algorithm for Computing c p and β m

Observing that only two decision variables, c p and m , need to be solved numerically, we are encouraged to introduce an intelligent algorithm GA to solve these two variables c p and m . GA can search optimal or near-optimal values c p and m in a numerical way, which helps us get rid of the difficulty of nonconcavity; GA is very powerful for finding a global near optimum efficiently [START_REF] Liu | Stackelberg-Nash equilibrium for multilevel programming with multiple followers using genetic algorithms[END_REF][START_REF] Akyol | A review on evolution of production scheduling with neural networks[END_REF][START_REF] Solnon | The car sequencing problem: Overview of state-of-theart methods and industrial case-study of the ROADEF'2005 challenge problem[END_REF] and can escape from local optima by feeding new inputting values of c p and m , which can overcome the multimodality of the objective function.

In GA, a population of chromosomes is generated and evolves toward optimal solutions.

A chromosome corresponds to a solution of Model GM-I. The initial population is commonly generated randomly [START_REF] Joines | A genetic algorithm for function optimization: A Matlab implementation[END_REF]. The chromosomes in subsequent generations are produced by using selections, mutations, and crossovers. The quality of a chromosome is evaluated by a fitness function. The fitness function is defined by the objective function Eq. (3.2.7). By using the fitness function, the chromosomes can be ranked from good to bad ones. The random generation of chromosomes for the initial population is the first step to avoid local optima. In this research, we use the well-known GA Toolbox of Matlab 2012b to code and solve the two variables c p and m .

A chromosome in GA is characterized by the decision variables (c p , m ), which are the wholesale price and the percentage of the green technology applied in production, respectively. The initial chromosomes are randomly generated with a population size of 80.

The chromosomes in the subsequent generations are generated by three genetic operators: operations of selection, crossover, and mutation.

Firstly, GA elitist selection is used to generate chromosomes for next generations. An elitist strategy [START_REF] Onwubolu | Optimizing the multiple constrained resources product mix problem using genetic algorithms[END_REF] is used for selection operator to ensure that the best chromosomes (with a ratio of 2%) can survive in the evolution. Some elite solutions that give good fitness function values in the current generation are selected and directly included in the next generation.

Next, GA crossovers are used to produce some chromosomes for the next generation. In a GA crossover, a pair of chromosomes is selected as parents with probability 0.2 to generate two offspring (i.e., two chromosomes) for the next generation. In the crossover operator, once a pair is selected, some chromosome genes of one parent are randomly selected as crossover points [START_REF] Poon | Genetic algorithm crossover operators for ordering applications[END_REF], and are used to swap genes with the corresponding ones of the other parent. The better the fitness value a chromosome has, the larger the chance that the chromosome will be selected as a parent. The crossover operation is often considered to find local optima.

Thirdly, an offspring will be also generated by a mutation operation to jump out the current local optima. We set the probability of mutation by 0.5. The mutated gene is randomly reset within the initial bounds. When the next generation population of chromosomes is produced, they will be evaluated by the fitness function. Mutation operations aim at producing new offspring chromosomes to diversify the populations to avoid falling into local optima.

In the last generation, the chromosome, giving the maximum value of objective function Eq. (3.2.7), is selected as the final solution of Model MR-3-I. The criterion used for terminating the algorithm is a convergence accuracy of 1.0×10 -6 for the fitness function.

Dynamic Programming Algorithm for Solving x

As referred in Section 3.2.2.2, with given c p and m , we can solve the decision variables x with a dynamic programming algorithm. An algorithm developed by [START_REF] Dasgupta | [END_REF] to solve the 0-1 knapsack problem is adopted in our algorithm. As suggested by [START_REF] Dasgupta | [END_REF], the results recorded in a two-dimensional table mapping all candidate retailers and emission-cap limitation. In this case, if the emission cap is given, we can look up to determine which retailers should be selected in one column of the table. The algorithm is introduced in detail as follows.

Let k (k=0,…,n) denote the stage which corresponds to the k th (k≠0) retailer and 0 is used for initialization, and * [] k w  denote the evaluation function representing the maximal profit of the manufacturer with given emission limitation w at stage k. For the sake of convenience, we let

(1 )

m r m g W E e e           
 be the total production capacity. Based on the objective function (3.2.23) (omitting m S ), we then get the following recursive function:

* * * 1 {0,1} ( ) max { + ( ( , ) )}, 1,..., , k k k k k k p m k x w A x w D c x k n         (3.2.25) with * 0 () w  =0 for any [0, ] wW  , and * 1 ( ( , ) ) = 0 k k p m k w D c x     whenever * ( , ) 0 k p m k w D c x    .
The optimization at stage

k k k k p m k A w D c w        , we have * () k w  = * * 1 + ( ( , )) k k k p m A w D c    with * k x =1. (3.2.26) Otherwise, * () k w  = * 1 () k w   with * k x =0. (3.2.27)
The optimal solution x * and the related * () n W  can be realized by the DP algorithm, named Algorithm-3-DP, as introduced above. The pseudo-codes of Algorithm-3-DP are given in Figure 3.1.

In the dynamic programming algorithm presented above, the time complexity is

  * 1 ( , ) (1 )

End For End For

Step 3 Outputting optimal solutions and results Note that because our problem uses GA to calculate the decision variables of c p and m , the optimality of the final solution cannot be guaranteed in a finite number of iterations.

Output

However, our hybrid algorithm obtains near-optimal solutions efficiently in a finite number of iterations.

Step 6: Update c p and m by GA

Step 7: Output the best solutions c * p and * m , x * , y * and p * , and the maximal profit π m

No

Yes

Step 5: Is GA termination condition satisfied?

Step 1: Initialize c p and m by GA

Step 2: Compute optimal y * and p * analytically

Step 3: Compute optimal x * by Algorithm-3-DP

Step 4: Compute the maximal π m

. Numerical Examples

This section conducts some numerical experiments to evaluate our models developed under emission-cap regulation policy. For long-term planning decisions of the manufacturer, it is intuitive that retailer selection and the carbon footprint play important roles in the performance. Generally, retailer selection strategy leads to higher performance than non-selection strategy does. We thus try to analyze our problem through retailer selection strategy, carbon footprint of the product, and some other parameters. All

the following examples are solved with the same computational parameters in the DP and GA.

We consider an example of a manufacturing company, whose production is constrained by a government-imposed emission-cap regulation policy. There are ten candidate retailers located in geographically separate costumer markets, for the manufacturer to select and build his buy-sell system. The emission cap is E = 8 thousand tons. The parameter values for the manufacturer are given as follows.

The unit production costs: The values for retailer-related parameters are given in Table 3.1.

. . . Computational Results

The numerical tests are conducted 10 times and the relevant results are provided as follows. The average profit of the manufacturer in the 10 tests is 1.8732×10 5 dollars as shown in Table 3.2. Our hybrid algorithm converges with a high robustness.

As seen from Table 3.2, the maximal gap of the objective value is only 0.007%. Thus, we just give the solutions of the "best" test, in which the profit of the manufacturer is 1.8733×10 5 dollars. His optimal decisions are: x = (0, 1, 0, 1, 0, 1, 0, 0, 0, 1), c p * = 122.18 dollars, m * = 40.53%. Four retailers, including 2, 4, 6 and 10, are selected by the manufacturer into his system. The retailers" decisions are: y * = (1, 1, 1, 1, 0, 1, 1, 0, 1, 1) and p * = (-, 135.30, -, 139.33, -, 130.22, -, -, -, -, 146.64). The profits of the retailers are shown in the 2 nd row of Table 3.3.

Resulting from the non-selection strategy, the manufacturer"s maximum profit is 1.61×10 5 dollars at c p * = 137.53 dollars and m * = 92.50%. Note that non-selection strategy implies that all retailers willing to join in the system are selected by the manufacturer, i.e.,

x i "s are omitted for consideration. The ten retailers" profits are given in the 3 rd row of Table 3.3. The values in the last row of Table 3.3 are the selected retailers" profit increase due to retailer selection. The values in "( )" are the retailers" profits at the optimal wholesale price (c p *): $1615.65if selected. Note. In the both cases, the manufacturer has used up his capacity.

With the computational results, we draw some conclusions as follows.

(1) The manufacturer can benefit from retailer selection. As seen from the results, the manufacturer"s profit increases significantly from 1.61×10 5 to 1.87×10 5 dollars, an increase of more than 15%, as a result of retailer selection such that the retailer most profitable to him is selected into the system.

(2) The profits of the selected retailers may significantly change due to retailer selection of the manufacturer. For example, as shown in Table 3.3, the profits of some retailers (retailers 2, 4 and 6) increase by more than 60%, but retailer 10 incurs a decrease by more than 80%. The manufacturer only cares about his profit and determines the wholesale price and carbon footprint to maximize his profit, but these decisions does not always benefits the retailers as shown in Eq.

(3.2.18).

(3) The carbon footprint of the product may be significantly influenced by the retailer selection strategy. When the retailer selection strategy is considered, the optimal percentage of products produced by the green technology drastically decreases from 92.50% to 40.53%. This decrease results from eliminating the retailers bringing negative or few profits to the manufacturer. Furthermore, this decrease will be more remarkable under a severe emission regulation policy.

(4) The most profitable retailers may not be selected. This is because the manufacturer cares about his profitability instead of the retailers". For example, retailer 9 is refused by the manufacturer even though it brings the most profit overall.

(5) As production is constrained by emission cap, the manufacturer excludes the retailers who are less profitable to him than those selected. To realize this, the manufacturer, for example, in Table 3.3, excludes retailers 7 and 9 otherwise the manufacturer would have to costly lower down the wholesale price from 137.53 to 122.18 dollars.

. . . Sensitivity Analysis

In this section, we provide sensitivity analysis for parameters used in our model. Under the emission-cap regulation policy, by intuition, the government-imposed emission cap Ē and the carbon-footprint elasticity b i are two important factors influencing the decisions of the manufacturer, thus we conduct sensitivity analysis for these two parameters as follows.

Emission cap

The emission cap may affect the manufacturer"s wholesale price, carbon footprint of product, and the number of selected retailers, thus it may significantly influence the profit of the manufacturer. To explore these effects, we vary the values of emission cap E from 2000 (a low value) to 40000 (a high value) in our model to identify the corresponding changes to the above parameters. The results are shown in As a general trend, an increase in emission cap results in an increase in the optimal number of retailers, the manufacturer"s maximum profit, and actual emissions. From the results in Figure 3.3, we find some interesting managerial insights.

(1) The profit of the manufacturer is significantly influenced by the emission cap.

When the emission cap is at a high level, the manufacturer can increase his profit by lowering down his wholesale price to sell more products (i.e., select more retailers into the system), or decreasing the percentage of green technology used in production. As shown in Figure 3.3(a), (b) and (c), when the emission cap goes up from 2 to 10 thousand tons, the manufacturer drastically increases his profit from 9.05×10 4 to 2.07×10 5 by decreasing his wholesale price from 152.55 to 114.20 dollars, selecting retailers from 2 to 4, and decreasing the percentage of the green technology used in production from 100% to 6.33%.

(2) It is unreasonable to expect the manufacturer to select all candidate retailers even if the emission cap is high enough. Some retailers may not be selected because a profitable retailer may be not profitable to the manufacturer or a retailer cannot gainfully operate. As shown in Figure 3.3(a) and (b), although the emission cap increases after Ē = 18 thousand tons, the manufacturer declines selecting more than 6 retailers. Furthermore, if the emission cap is relatively low compared to the number of the retailers, as

shown in Figure 3.3(b), more retailers are selected with Ē increasing from 2 to 6 thousand tons.

(3) The optimal production quantity (i.e., the actual emissions) heavily depends on the candidate retailer"s contribution to the manufacturer"s profit instead of their own profitability. If the emission cap is ample but retailers profitable to the manufacturer are few, it is unwise for him to produce at the full emission cap. As

shown in Figure 3.3(d), if Ē=40 thousand tons, only a half utilization is enough for maximizing the manufacturer"s profit.

Carbon-footprint elasticity

As shown in Eq. (3.2.2), the demand of retailer may be greatly influenced by the carbonfootprint elasticity b i . The carbon-footprint elasticity presents the preference of the customer on the green production, i.e., the higher the carbon-footprint elasticity, the greener product the customers prefer to select.

For the carbon-footprint elasticity b i , we randomly take a retailer who is rejected in the basic example in Section 3.4.1.1: retailer 1. If we change the price elasticity b 1 of retailer 1 from 1800 to 800 (the lowest value in the 10 candidate retailers), the manufacturer"s optimal decisions become x * = (1, 1, 0, 1, 0, 1, 0, 0, 0, 1), i.e., retailer 1 is selected into the system. This is because smaller carbon-footprint elasticity implies customers are less sensitive to the change of carbon-footprint. With retailer 1 selected, the manufacturer gets an additional demand of d 1 = 904.03 tons for his product. Consequently, retailer 1"s profit increases to 8.98 thousand dollars. The manufacturer"s profit also increases to 2.04×10 5 dollars, by 9.09%. That"s to say, both the manufacturer and the retailer may benefit from this change.

Let a customer market within high (resp. low) carbon-footprint elasticity denote СiРС-end (resp. low-end) customer market 1 . Then we can obtain some interesting managerial insights. From the sensitivity analysis of b i above, we find that the manufacturer studied in our numerical examples prefers to provide product to a low-end customer market. As seen from the analysis above, the manufacturer benefits drastically from adding a new low-end customer market (i.e., retailer 1) into the system. For the manufacturer, thus, it is important to choose the "right" markets for his product. Moreover, pricing his product appropriately for such markets is also critical for him to maximize his profit.

. Conclusion

This chapter studies long-term strategic decision problems for a manufacturer, whose production is limited by the government-imposed emission-cap regulation policy. The objective is to maximize the profit of the manufacturer by optimally determining the carbon footprint and wholesale price of the product as well as retailer selection.

The problem is formulated as a Stackelberg game model which is proved to be NPhard, non-continuous and analytically intractable. In order to deal with these difficulties, we develop a hybrid algorithm (named Algorithm-3-Hybrid), combining genetic algorithm, dynamic programming approach and analytical methods to solve the model.

Some numerical experiments are conducted to show the application of our proposed models and the algorithms. The computational results show that the hybrid algorithm can efficiently find near optimal solutions and converges with a high robustness.

Furthermore, some valuable managerial insights are obtained from the sensitivity analysis, which is briefly outlined below.

(1) The manufacturer can benefit from retailer selection under the emission-cap regulation policy. An appropriate retailer selection strategy can help the manufacturer to maximize his profit by selling his products to the "right" retailers and cope with the emission limitation imposed by the government.

(2) The governmental emission cap and customers" green preference significantly affect the carbon footprint of the product. Thus, to optimize the carbon footprint may make the manufacturer more profitable while satisfying the customer demands and the emission regulation.

(3) It is important for the manufacturer to choose either low-end or high-end markets to sell his product and to price his product appropriately for these markets.

Furthermore, an optimal differential pricing strategy implemented through his retailers can make the manufacturer more competitive in green-awareness markets.

operating costs to a minimal level that fully satisfies customer demands without any shortage or backlogging. Moreover, an optimal technology selection provides the best balance between production cost and emissions. These optimal operational decisions enable the manufacturer to minimize his overall costs and satisfy the government-imposed emission regulations.

This chapter investigates this practical decision problem under each emission-reduction policy. Under the emission cap-and-trade scheme, particularly, the manufacturer possesses tradable initial emission allowances. Besides the emission-cap constraint for each period, his production emissions over the planning horizon are limited by on-hand emission allowances, but he can choose to buy or sell emission allowances from or to the carbon market.

In order to formulate the problem mathematically, we define the notation used in this chapter as follows.

. . Notation

The notation used throughout this chapter is listed as follows:

Parameters T number of periods involved in a production planning horizon μ emission cap set by the government for each production period R emission limitation in each period related to environmental bearing capacity of the area where the manufacturer is located e r , e Р emissions from producing unit product with technology-r and technology-g, respectively. e r > e g >0 p r , p Р unit production cost using technology-r and technology-g, respectively. 0<p r < p g s r , s g setup cost using technology-r and technology-g, respectively. 0<s r < s g .

d

. Emission-Cap Regulation Policy

This section studies the medium-term operational decision problem under the emission-cap regulation policy. The problem is formulated as a MILP and a polynomial algorithm is developed to solve the proposed model based on some properties of optimal solutions.

One of the crucial steps is to draw an equivalent global production cost function involving two candidate production technologies.

. . Mathematical Formulation

By defining

1 if 0 () 0 if 0 x x x       
, the problem can be formulated as a model, named Model M-4-I, as follows. where ε is an arbitrarily large number.

Model M-4-I

The cost function (i.e., Eq.(4.2.6)) is a classical expression as in existing research (normally within a single technology), such as lot sizing problem [START_REF] Wagner | Dynamic version of the economic lot size model[END_REF][START_REF] Brahimi | Single item lot sizing problems[END_REF]Jans and Degraeve, 2007b), scheduling problem [START_REF] Schutten | List scheduling revisited[END_REF][START_REF] Drexl | Lot sizing and scheduling: Survey and extensions[END_REF][START_REF] Kolisch | An integrated survey of deterministic project scheduling[END_REF], and some other optimization problems [START_REF] Beck | Supply chain coordination via mediated constraint relaxation[END_REF][START_REF] Cachon | Managing supply chain demand variability with scheduled ordering policies[END_REF][START_REF] Erenguc | Integrated production/distribution planning in supply chains: An invited review[END_REF].

However From Model M-4-I-T, it can be seen that x tr "s only appear in the first term of the objective function and in constraints (4.2.15) and (4.2.17). At any optimal solution, for any given x t , the value of x tr must be such that the sum of the first term of the objective function is minimized and the constraints (4.2.15) and (4.2.17) are satisfied.

As a consequence, the problem can be decomposed into two subproblems:

 the first subproblem is to compute the optimal value of x tr for any given x t , such that the sum of the first term of the objective function is minimized while satisfying the constraints (4.2.15) and (4.2.17).

 the second subproblem is to compute the optimal values of x t "s.

In fact, the first subproblem is a technology selection problem, while the second subproblem is a production planning problem. Note that the first subproblem, i.e., the technology selection problem, is parameterized by x t (i.e., the production quantity of period t). More specifically, these two subproblems can be rewritten as follows.

The technology selection problem M-4-TS:

Model M-4-TS 0 ( ) ( ) min ( ) ( ) ( ) tr t
                (4.2.19)
The production planning problem M-4-PP-I: The production planning problem M-4-PP is a classical lot sizing problem but the production cost function Р(•) is obtained by solving the problem M-4-TS. It might be solved in polynomial time if Р(•) has some good properties such as continuous concave piecewise linear function (see [START_REF] Chu | Polynomial algorithms for single-item lot-sizing models with bounded inventory and backlogging or outsourcing[END_REF]). However, as it will be shown hereafter, the production cost function Р(•)

Model M-4-PP-I Minimize 1 1 ( ) ( )
does not have such properties. Actually, the equivalent global production cost function (still called production cost function hereafter, for the sake of simplification) is even not continuous, which makes our model difficult to solve. Nevertheless, thanks to mathematical properties we prove, the problem is shown to be polynomially solvable.

. . Solving Technology Selection Problem

As can be seen, the problem M-4-TS is period-independent. We therefore drop subscript t. For the sake of simplification, x tr is further simplified into z. As a consequence, problem M-4-TS can be further rewritten as

0 () ( ) min ( ) ( ) ( ) . rg r g r g zx e z e x z g x s z s x z p z p x z                 (4.2.25)
Note that Р(x) is defined only when 0 x μ/e Р , since otherwise it is impossible to simultaneously satisfy the constraints 0 z x and ( )

r g e z e x z     .
Furthermore, it is easy to obtain Р(0) = 0 by the definition. Therefore, in the remainder, we just consider the case 0 < x μ/e Р .

Let ( , )

( ) ( ) ( ) r g r g x z s z s x z p z p x z        
, with 0 z x. Whenever x z x

                (4.2.26)
where the three terms in the braces on the right side of Eq. ( 4

                , , otherwise. g x x e              (4.2.28) () 0, 0, , 0 , () , , , otherwise. r r r b g g r g x s p x x e gx s p x e x e                   (4.2.29)
In a production period, if two technologies are used for production, the optimal production quantity of each technology is given by * From Eq. (4.2.27) and Figure 4.1, it can be seen that the cost function is non-continuous, which makes it difficult to solve the production planning problem M-4-PP [START_REF] Keha | A branch-and-cut algorithm without binary variables for nonconvex piecewise linear optimization[END_REF]. However, we try to develop a dynamic programming algorithm and solve Model M-4-PP in polynomial time.

* ( ) ( ) ( ), ( ) ( ) ( ).

. . Solving Production Planning Problem

In this subsection, the problem is decomposed into a series of subproblems (i.e., subplans). Then, a subplan is further decomposed into two smaller subintervals, which can be calculated recursively in polynomial time. Finally, a polynomial dynamic programming algorithm is developed based on multi-level decomposition to solve the model.

. . . Decomposing a Plan into Subplans

For the sake of convenience, we first give some necessary definitions which will be helpful to analyze the problem as follows.

Normal By the definition of subplan, it can be seen that whatever an optimal solution of a subplan is found, the inventory in each period, except for the last one, is positive. The concept of subplan (i.e., subproblem) is critical to develop our algorithm because only these subproblems need to be considered in a dynamic programming approach. Now, let us consider an optimal subplan (i,k) which satisfies the demands d i+1 , ..., d k with minimal cost. Let C(i, k) denote the minimal cumulative production and inventory cost of the subplan, and F(k) denote the minimal total cost of satisfying the demands d 1 ,..., d k such that the inventory level at the end of k is zero. Then, the proposed model can be solved by a dynamic programming approach as follows.

By the definition, we have the following initial condition and recursive equation:

0 (0) 0, ( ) min{ ( ) ( , )}, 1,..., . ik F F k F i C i k k T           (4.2.31)
With the recursive equations, the optimal solutions can be obtained by F(T) in O(T 2 ) time after all C(i,k)"s are known. Therefore, the challenge and critical work to solve the problem is to calculate all possible C(i,k)"s efficiently. In what follows, we show how to calculate the cumulative costs of subplans in polynomial time, and develop a polynomial dynamic programming algorithm to solve the model.

Even though the actual production cost function is not continuous, it is piecewise concave; i.e., each continuous part is a concave function. According to the theorem proposed by (Swoveland, 1975b), we can obtain the following property for a subplan considered in this research.

Theorem 4.2.1 TСere is an optimal solution sucС tСat eacС subplan contains at most one sinРular period.

With the property of subplan, a subplan can be decomposed into two smaller subintervals, which can be calculated polynomially. Consequently, the cumulative cost of a subplan can be calculated in polynomial time. In the remainder of this subsection, we show how to decompose a subplan into subintervals and calculate the cumulative costs of the subintervals polynomially.

. . . Decomposing a Subplan into Subintervals

According to Theorem 4.2.1, we consider the case that there exists one singular period in a subplan. In other words, there is an optimal solution such that all production periods in each subplan are normal periods except for one singular period. Note that a singular will be excluded automatically when it generates more cost than it is not included in a subplan, according to the minimization theory. Based on this structure of optimal solutions, we can decompose a subplan into two polynomially solvable subintervals as introduced below.

Let us consider a subplan (i, j, k), 0 ≤ i < j ≤ k ≤ T, such that all production from i+1 to j-1and from j+1 to k are normal periods, and period j is a singular period which may be executed by any kinds of production. In other words, such a subplan can be decomposed into two subintervals and a singular period j. For the sake of convenience, let (i, j-1) and (j, k) denote these two subintervals, respectively. Note that zero inventory point does not exist in a subinterval except for periods i and k.

Let c(i, j, k) denote the minimal cumulative production and inventory cost of subplan (i, j, k), in which there exists exact one singular period j. Some other definitions are given as follows.

For subinterval (i, j-1), let α i , j-1 (m r , m Р ) denote the minimal cumulative production and inventory cost from i+1 to j-1, with m r and m Р being the numbers of normal periods using technology-r and technology-g, respectively.

For subinterval (j, k), let j, k (n r , n Р ) denote the minimal cumulative production and inventory cost from j+1 to k, with n r and n Р being the numbers of normal periods using technology-r and technology-g, respectively.

For sinРular period j, let Y i, j, k (m r , m Р , n r , n Р ) denote the production and inventory cost of period j. The production quantity x j and the inventory level I j correspond to the numbers of normal periods in the two subintervals.

By the definition of α i , j-1 (m r , m Р ) and j, k (n r , n Р ), we can calculate both of them recursively. Whereafter, Y i, j, k (m r , m Р , n r , n Р ) can be computed by the production cost function (4.2.27), according to the production quantity x j of period j. Then, the cumulative cost of subplan (i, j, k) can be obtained by c(i, j, k)

= α i , j-1 (m r , m Р ) + j, k (n r , n Р ) + Y i, j, k (m r , m Р , n r , n Р ).
Therefore, the remaining work is to calculate the minimal cumulative costs of the subintervals and the cost of the singular period.

. . . Calculating Minimal Cumulative Costs of Subintervals

a. Minimal Cumulative Cost of Subinterval i, j-: i, j-1 m r , m g .

Let α i , s (m r , m Р ) denote the minimal cumulative production cost and inventory cost from i+1 to s, with m r and m Р normal periods using technologies r and Р, respectively. We have the following relationships:

0, 0, 0, r g rg m m m m s i            (4.2.32)
where m r + m Р = 0 implies i = s, and the subinterval is not included in the subplan, because i+1 must be a production period.

The inventory level at the end of s is I s = m r μ/e r + m Р μ/e Р -d i,s . We must have I s > 0 if s ≠ k, since backlogging is not allowed and zero inventory point only exists at periods i and k.

Firstly, we initialize the minimal cumulative cost of subinterval (i, s) by the definition of α i , s (m r , m Р ), as follows.

  0, 0, ,, , otherwise.

rg i i r g mm mm        (4.2.33)
Then, α i , s (m r , m Р ) can be calculated by the following recursive equations as follows.

        1 1 1 , 0,
                               (4.2.34)
In the first case of Eq.(4.2.34), if I s < 0, the solution is infeasible and α i , s (m r , m Р ) is set to be +∞. The second case consists of three subcases, in which С s I s is the holding inventory cost of period s and α i , s-1 (•,•) is the minimal cumulative cost from i+1 to s-1. For the first subcase, there is no production at period s. For the second subcase, s is a normal period using technology-r. For the third subcase, s is a normal period using technology-g. It is easy to see that, for any feasible m r , m Р and 0 ≤ i ≤ s ≤ T, all possible α i , s (m r , m g )"s can be calculated in a computation time of O(T 4 ).

b. Minimal Cumulative Cost of Subinterval j, k : j, k n r , n g , By the definition, t, k (n r , n Р ) is the minimal cumulative production and inventory cost from j+1 to k, with n r and n Р normal periods using technologies r and Р, respectively. For any period t, 0 ≤ j+1 ≤ t ≤ k ≤ T, we have the following relationships of n r and n Р .

0, 0, 0. r g rg n n n n k t            (4.2.35)
Different with the subinterval (i, s), there may be no production in (t, k), i.e. n r + n Р may equal to 0.

The inventory level at the end of period t-1 is I t-1 = d t , k -n r μ/e r -n Р μ/e Р . Then, we can calculate all possible t,k (n r , n Р )"s recursively. The initial and recursive equations are given by Eqs. (4.2.36) and (4.2.37) as follows.

  , 0, 0, , , otherwise.

r g k k r g nn nn        (4.2.36)       1 1 1, , 1
                               1, otherwise. , 1 , k r g nn                  (4.2.37)
In the first case of Eq. (4.2.37), if I t-1 ≤ 0 or I t ≤ 0(t ≠ k), the solution is infeasible and t,k (n r , n Р ) is set to be +∞. The second case consists of three subcases, in which With the recursive equations, all possible t,k (n r , n Р )"s can be computed in O(T 4 ) time.

c. Cost of the Singular Period j: Y i, j, k m r , m g , n r , n g

The production quantity of period j is

x j = d i,k -[(m r +n r ) μ/e r +(m Р +n Р ) μ/e Р ],
the inventory level at the end of the period is

I j = I j-1 + d i,k -[(m r +n r ) μ/e r +(m Р +n Р )
μ/e Р ]-d j , and it must be

I j > 0 if j ≠ k.
Y i,j,k (m r , m g , n r , n g ) can be calculated by the production cost function Р j (x j ) (see Eq. ( 4.2.27)), and the related production quantity of each technology can be obtained by Eq.(4.2.30). If the constraints are not satisfied, the solution is infeasible and the cumulative cost is set to be +∞.

Then, the cost of period j is be given by  

, , ( ), 0 , and 0( ), , , , , otherwise.

j j j j g j r j i j k r g r g h I g x x e x e I j k Y m m n n             (4.2.38)
In subplan (i, j, k), n Р can be determined by the given m r , m Р and n r . Let Q = d i,k -[(m r + n r )μ/e r + m Р μ/e Р ] and P = μ/e Р , then we have n Р = QP   . We, thus, can compute all possible Y i, j, k (m r , m g , n r , n g )"s in O(T 6 ) time.

Up to now, the minimal cumulative costs of the subintervals and the cost of the singular period are calculated polynomially. Then, we can calculate the minimal cumulative cost of the subplan (i, j, k), 0 ≤ i < j ≤ k ≤ T, as follows.

For any given subplan (i, j, k), its minimal cumulative cost is ,,,,,,min ,,,,, , Recall that the model can be solved by a dynamic programming approach with the recursive equations Eq.(4.2.31), thus, we try to develop a polynomial dynamic programming algorithm using the computational results of c(i, j, k).

          1 ,
rg rg i j r g j k r g i j k r g r g mm nn c i j k m m n n Y m m n n       (
We reformulate the recursive equation (4.2.31) into the following equations: 0 (0) 0, ( ) min { ( ) ( , , )}, 1,..., .

i j k F F k F i c i j k k T             (4.2.40)
In the new recursive equations, the optimal solution can be obtained by

F(T) in O(T 3 )
time after the computation of all possible c(i, j, k)"s, which needs O(T 6 ) time. Therefore, the overall complexity to find the optimal solution is O(T 6 ).

The pseudo codes of the dynamic programming algorithm, named Algorithm-4-PDP, are given in Figure 4.2 .

Algorithm-4-PDP

Step

Step 4 Outputting results

Output optimal solutions corresponding to F(T).

. Emission Cap-and-Trade Scheme

In the previous section, we study the manufacturer"s operational decisions on production planning and technology selection under the emission-cap regulation policy. Subsequently, this section studies the problem under the government-imposed emission cap-and-trade scheme.

Under such a scheme, the manufacturer"s production is constrained both by the on-hand emission allowances over the planning horizon and by the environmental bearing capacity in each period. The manufacturer obtains some tradable initial emission allowances at the beginning of the planning horizon. The on-hand emission allowances imply the quantity of carbon he can legally emit or sell in the planning horizon. However, he can also purchase carbon credits from the carbon market if necessary. In either case, the manufacturer must surrender enough allowances to cover all his emissions during the planning horizon, otherwise heavy fines are imposed. His production emissions in each period are also constrained by a constant emission cap. Different from the emission-cap regulation policy, the emission cap in such scheme is subject to the environmental bearing capacity of the area the manufacturer is located.

In addition to production planning and technology selection, the emission allowance trading strategy should be considered under such a scheme. In the remainder of this section, we first formulate the problem as a mathematical model, and then analyze the solution methodology of the model.

. . Mathematical Model

The manufacturer receives an amount of initial emission allowances E at the beginning of the production planning horizon, and he may either buy carbon credits from the carbon market or sell spare allowances to the others at a price of .

Let ()

Γ  denote the cost/revenue of buying/selling  carbon credits. ( ) 0 Γ   implies that the manufacturer has to pay () Γ  to buy additional carbon credits  , ( ) 0 Γ   means he can receive a revenue of () Γ   from selling his spare allowances  . Then, the cost/revenue function can be given by

( ) , . Γ R     Equation Chapter 4 Section 3(4.3.1)
When all x tr "s and x tР "s are known, the quantity of trading carbon allowances in the planning horizon is

  1 ( , ) . xx T r g r tr g tg t e x e x E       (4.3.2)
The cost function, thus, can be formulated as follows.

 

1 1 ( , ) ( ) ( )
                 xx (4.3.3)
As can be seen from Eqs. (4.3.2) and (4.3.3), the allowance trading decision variable  is omitted and replaced by the variables x tr "s and x tР "s. Note that the emission constraint over the planning horizon, i.e., Model M-4-II where the objective function (4.3.4) consists of two terms. The first term includes the production cost and the inventory cost, and the second term represents the cost or revenue related to the emission allowance trade. Constraint (4.3.5) ensures that inventory is balanced. Constraint (4.3.6) limits production emissions with the emission cap in each period. Constraint (4.3.7) defines the initial and end inventory level of the planning horizon.

Minimize   1 1 ( , ) ( ) ( )
The bounds of the decision variables are constrained by Eq. (4.3.8).

. . Solution Methodology

In this section, we analyze the problem based on a reformulation technology and show that the proposed model can be solved by Algorithm-4-PDP developed in the previous section.

In the second term of the objective function (4. In the objective function, -E is a constant independent of the decision variables and hence can be removed. Now, let us integrate the emission cost into the production cost function Р(x), and consider a so-called actual production cost, which consists of the production cost and the emission cost. Under this cost structure, the manufacturer pays the cost for all his production emissions, but all initial emission allowances allocated by the government are considered as revenues. The actual unit production costs of the technologyr and technology-g, i.e., r p and g p , are given as follows. Similar to Section 4.2, the problem can be decomposed into two subproblems: technology selection problem and production planning problem. But, the problem cannot be solved by simply replacing , p Р and p r by R, g p and r p , respectively. Because it is possible that r p g p due to the parameter , while p Р > p r is a necessary assumption when solving the problem.

However, the same method presented 4.2 can be used to analyze the technology selection problem for the case r p g p . Let f(x) denote as the production cost function under the emission-trade scheme. Similar to the production cost structure Р(x), we can obtain the function f(x) as follows.

If g r pp   , () () ( ), , () ( )
, otherwise. ()

a rg b f x R e x R e fx fx        (4.3.10) If g r pp   , () () ( ), , () ( ), otherwise.
                   , , otherwise. g x x R e             (4.3.12) () 0, 0, , 0 , () , , , otherwise.
                  (4.3.13) () 0, 0, , 0 , () , , , otherwise. rr
c g g g x s p x x x fx s p x x x R e                   (4.3.14)
In () ( ), a fx i.e., Eq. (4.3.12), if two technologies are used for production, the optimal production quantity of each technology is . Then, the production planning problem M-4-PP-II can be formulated as follows.

* * ( ) ( ) ( ), ( ) ( ) ( ).
Model M-4-PP-II

Minimize 1 1 ( ) ( ) , x T T t t t t t F f x h I E        (4.3.16) Subject to 1 , 1,..., , t t t t I d I x t T      (4.3.17) 0, T I  (4.3.18) 0 , 1,..., , t g x R e t T    (4.3.19) 0, 1,..., . t I t T  (4.3.20)
In Model M-4-PP-II, observing E is a constant and all constraints are the same to Model M-4-PP-I, thus, we can solve the model by Algorithm-4-PDP developed in the previous section. In other words, the proposed model, considering the emission cap-and-trade scheme, can be also solved in polynomial time.

. Numerical Examples

In this section, we conduct some numerical examples to illustrate the application of the model and the algorithm studied under each policy. It is intuitive that the emission cap and carbon price have significant influences on operational decisions. Therefore, sensitivity analysis is provided to explore these influences.

. . Emission-Cap Regulation Policy

We consider an example of a manufacturer, whose production is constrained by the government-imposed emission-cap regulation policy. He needs to arrange his one-year production planning (12 periods/months). The monthly demands are given in Table 4.1. The emission cap is μ = 20 thousand tons. Some other parameters are given as follows.

The setup costs: The computational results are given in Section 4.4.1.1. We provide sensitivity analysis of the emission cap and explore some valuable managerial insights in Section 4.4.1.2.

. . . Computational Results

Resulting from the computation, the minimal cost is 11.56 million dollars; the total carbon emissions in one year are 216.00 thousand tons. Some other results are given in The results show that the emission cap is not very tight for the manufacturer. As the results shown in Table 4.2, the regular technology and the green technology are used 7 and 5 times, respectively. Note that both technologies are used simultaneously in period 6. The regular technology is used more frequently than the green technology.

The manufacturer always tries to use out the emission permits in each period under the emission-cap regulation policy. As can be seen in Table 4.2, emissions in 9 periods are equal to the emission cap in the 12-period planning horizon.

. . . Sensitivity Analysis

By intuition, the government-imposed emission cap has direct and significant influences on the operational decisions on production planning and technology selection. We provide some sensitivity analysis to explore these influences as follows.

We change the emission cap μ from 15 (a low level) to 55 (a high level) thousand tons.

Note that, an emission cap that is more than 55 thousand tons cannot constrain the manufacturer"s production emissions any more. As can be seen in Figure 4.4 , the results

show the emission cap has significant impacts on, the total cost, the total emissions and technology selection. With the results, we draw some conclusions as follows.

(1) The emission cap has significant influences on the production planning and the total cost. As seen in Figure 4.4 (a), the manufacturer cannot produce any more when the emission cap is lower than 15 thousand tons. When the emission cap increases from 15 to 25 thousand tons, the total cost decreases drastically by (13.26-10.39)/13.26 = 21.64%. This is because, an optimal technology selection strategy may help the manufacturer to obtain a best balance between the emissions and the production cost, while an optimal production planning may help him to minimize the production and inventory costs over a finite production planning. (2) The curves of both the total actual emissions and the total cost are not smooth.

The reason is that the production cost function is piecewise. This implies that the proposed model is difficult to solve.

(3) The manufacturer always tries to use up the permitted emissions when the emission cap is relatively tight. From the results in Figure 4.4 (b), we can see that the total emissions are close to the emission cap when it is less than 25 thousand tons. But the emission cap will be invalid when it goes too high. As shown in the Figure 4.4 (a) and (b), the cost cannot be reduced any more when the emission cap is more than 53 thousand tons; the total emissions will not increase when the emission cap exceeds 29 thousand tons.

(4) The manufacturer does not have motivation to use green technology when the emission cap is too high. As we can see in Figure 4.4 (c), no green technology will be used if the emission cap is up to 29 thousand tons.

. . Emission Cap-and-Trade Scheme

In this section, we conduct a numerical example to show the application of our model for the emission cap-and-trade scheme studied in Section 4.3. In the example, we set all manufacturer-related parameters to the same values as those in Section 4.4.1. In order to make comparisons with the emission-cap regulation policy, we set the environmental bearing capacity to the same as the emission cap in Section 4.4.1, i.e., R = µ = 20 thousand tons. Some other parameters specially used in Model M-4-II are given as follows.

The initial emission allowances for a planning horizon:

E =

. . . Computational Results

The results show that the minimal cost is 12.13 million dollars; the total carbon emissions are 208.00 thousand tons. The manufacturer needs to buy 8.00 thousand tons carbon credits from market to satisfy his production. Some other related results are given in Table 4.3

. . . Sensitivity Analysis

This section analyzes the impacts of carbon price on the manufacturer"s decisions. Note that similar results can be obtained from the sensitivity analysis of emission cap (i.e., environmental bearing capacity) to those under the emission-cap regulation policy, thus we it omit here. The carbon price is changed from 10 to 50 dollars per ton. The results are given in Figure 4.5. With the results shown in Figure 4.5, we draw some interesting observations follows.

(1) The carbon price affects the cost of the manufacturer remarkably, especially when he suffers from a high production cost of the green technology. When the carbon price increases from 10 to 50 dollars per ton, the cost of the manufacturer varies in a narrow range from 10.96 to 12.33 million dollars with a percent of 15.50%, as shown in (2) The emissions decrease drastically when the carbon price goes up. As shown in Figure 4.5(b), when the carbon price increases from 14 to 24 dollars per ton, the emissions decrease from 218 to 161 thousand tons by 26.15%. However, the results also show that the emissions and technology selection strategy may remain the same when changing the carbon price (see Figure 4.5(b)). The reason is the setup cost: when the increase of carbon price is not large enough, the cost of switching to green technology (i.e., incurring higher setup cost) is higher than the cost of buying carbon credits even though the carbon price goes up.

(3) The green technology is used more frequently when the carbon price goes up. As seen from Figure 4.5(c), the number of periods using green technology increases remarkably when the carbon price increases from 14 to 22 dollars per ton. That is because the manufacturer tries to avoid high cost of buying carbon credits or to obtain more revenues from sell more emission allowances by using the green technology more frequently to reduce emissions.

. Conclusion

This chapter studies the manufacturer"s medium-term operational decision problem under two types of government-imposed emission-reduction policies, including emission-cap regulation policy and emission cap-and-trade scheme. The objective is to minimize the overall costs over a finite planning horizon.

The decision problems are formulated as MILP models which are difficult to solve. The manufacturer"s production is capacitated caused by the emission limitation. However, he can control emissions by a technology selection strategy, where two candidate technologies with setup costs could be chosen for production. The equivalent production cost functions turn to be non-continuous due to the emission limitation and technology selection, and bring difficulties in solving the models.

However, a polynomial dynamic programming algorithm (i.e., Algorithm-4-PDP) is developed to solve the models in O(T 6 ) time. In the algorithm, a multi-level decomposition approach is used to reconstruct the structure of solutions and conquer the difficulties brought from the special cost function. In particular, under the emission cap-and-trade scheme, the model is reformulated into an "emission-cap regulation model" by integrating the emission-trading constraint into the objective function and therefore can be solved by Algorithm-4-PDP.

Some numerical examples are conducted to show the application of our models and the algorithm. From the results of these examples, we explore some valuable managerial insights, which are briefly lined as follows.

(1) The technology selection and production planning strategy is significantly affected by emission cap. Therefore, the cost of the manufacturer increases drastically when the government implements a severe regulation policy. As shown in the numerical example, the cost increases by 21.64% when the emission cap lowers from 25 to 15 thousand tons.

(2) The technology selection strategy may remain the same when changing the carbon price under the emission cap-and-trade scheme. This is because the green technology will be used more often only if it generates more profit than setup cost.

(3) An emission cap-and-trade scheme may promote manufacturer self-motivated emission reduction. This is because technology innovation will be promoted in such a scheme.

In conclusion, the manufacturer may be much more flexible in optimizing his operational decisions and may benefit more from these optimizations under the emission cap-and-trade scheme than under the emission-cap regulation policy. Moreover, an emission-reduction policy within emission allowance trade is more effective to achieve the emission-reduction target.

. Problem Description and Notation . . Problem Description

This chapter aims to optimize a local government"s policymaking decisions on emissionreduction policies with the objective of maximizing the social welfare of the local region. The government"s decisions include the emission cap for each manufacturer in the emission-cap regulation policy and the emission-reduction target under emission cap-andtrade scheme.

In practice, green technologies cost more than the regular ones, but the regular technologies emit more emissions than the green ones. That is, emission reduction is at the price of paying economic costs. However, in recent decades, governments pay more attention to sustainable development from the viewpoint of the society. Sustainable development is a normative concept which involves tradeoffs among social, ecological and economic objectives, thus it is required to sustain the integrity of the overall system [START_REF] Hediger | Sustainable development and social welfare[END_REF].

In this chapter, emission-reduction policies are analyzed and studied from the perspective of social welfare, which consists of economic and environmental utilities.

Note that the social utilities considered in our research are just parts of the numerous and various utilities of a society. The social welfare may be influenced significantly by the emission-reduction polices: a severe emission-reduction policy may reduce emissions to a relatively low level (i.e., increase environmental utilities) at the price of raising costs of manufacturers (i.e., decrease economic utilities); in contrast, an easy policy may increase economic utilities at the cost of losing some environmental utilities. Therefore, a successful emission-reduction policy requires a good balance between the economic utilities and the environmental utilities.

This chapter focuses on this practical problem and seeks to maximize the social welfare of a local region by optimizing the government"s emission-reduction policies. In such a region, there are multiple homogenous manufacturers belonging to the same industry. They produce homogenous products emitting carbon dioxide but serve different retail markets.

All manufacturers make their medium-term production planning under the governmentimposed emission-reduction policies.

The manufacturers" operational decisions depend on the emission-reduction policies, while the social welfare could be influenced by the manufacturers" decisions responding to the government"s policies. Therefore, the government has to anticipate the manufacturers" reactions when imposing such policies. In our research, a frame of Stackelberg game is used to discuss the decision process of the government and the manufacturers, which is briefly introduced as follows.

In the Stackelberg game, the government acts as a leader and sets the emissionreduction policies, while the manufacturers act as followers and optimize their operational production planning under the emission-reduction policies imposed by the government. The government dynamically adjusts her policies and observes the manufacturers" optimal responses till the maximal social welfare is achieved. In this chapter, we study two types of emission-reduction policies, i.e., emission-cap regulation policy and emission cap-and-trade scheme, in Section 5.2 and Section 5.3, respectively.

In Section 5.2, we investigate the government"s policymaking problem regarding the emission-cap regulation policy. In such a policy, the government determines emission cap for each manufacturer in the region to limit the manufacturers" missions related to their production activities. As referred in Chapter 4, each manufacturer"s production emissions in each period are limited by a constant emission cap set by the government. For the sake of simplicity, we assume that the numbers of periods in a planning horizon of all manufacturers are the same, e.g., a one-year planning horizon including 6 periods.

The emission caps for all manufacturers could be optimally determined under a Stackelberg game frame. The government first sets an emission cap for each manufacturer, and then all manufacturers plan their production optimally according to the emission caps.

By observing or anticipating the responses of the manufacturers, the government computes the social welfare and adjusts the values of emission caps dynamically to improve the social welfare. These interactive decisions between the government and the manufacturers continue till the Stackelberg equilibrium is achieved. At the equilibrium point, the social welfare cannot be improved anymore. The policy is optimal (i.e., the emission caps are optimal) and the social welfare is maximal at this point.

The problem is formulated as a two-level Stackelberg model. In the model, the government maximizes the social welfare by optimizing emission caps with the first level of the model; the manufacturers minimize their overall costs by optimizing their production planning with the second level of the model, according to the emission caps set by the government. The optimal decisions of both the government and the manufacturers are obtained when the Stackelberg equilibrium is achieved. A hybrid algorithm is developed to find such equilibrium.

In Section 5.3, we discuss the government"s policymaking decisions regarding the emission cap-and-trade scheme. In such a scheme, the government allocates initial emission allowances to each manufacturer in the region, according to the reduction baseline and emission-reduction target. The reduction baseline is the amount of average emissions of the industry when only regular technologies are used for production, while the emission-reduction target is the percentage reduction of emissions of the region. That is, for certain duration (i.e., the demand scales and average emissions are known), the initial emission allowances allocated to the manufacturers only depend on the emissionreduction target.

In the emission cap-and-trade scheme, initial emission allowances are tradable.

Manufacturers can buy (or sell) emission allowances (or carbon credits) from (or to) each other in the region as needed. By the end of each year all manufacturers must surrender enough allowances to cover all their emissions, otherwise heavy fines are imposed. In our research, we consider a finite production horizon and assume that each manufacturer sells all their spare allowances at the end of each year. The carbon price is determined by all manufacturers and formed based on market (European-Commission, 2012). In our research, a Cournot competition model is used to analyze and optimize the carbon price, which depends on the manufacturers" on-hand initial emission allowances.

From the analysis above, we can see that the social welfare depends on the emissionreduction target set by the government. Therefore, the maximal social welfare of the local region can be achieved by optimizing the emission-reduction target. Similar to the mathematical model formulated in Section 5.2, a two-level Stackelberg model is presented to solve the problem in this section.

In the model, the government first sets a value of the emission-reduction target and allocates the initial emission allowances to each manufacturer. Then, the equilibrium carbon price is computed by the Cournot competition model. Meanwhile, all manufacturers react to the government"s decisions and optimally determine their production planning. The government observes the responses of the manufacturers and adjusts the emission-reduction target dynamically till the maximal social welfare is achieved.

. . Notation

The notation used throughout this chapter is as follows: Note that the notation related to the decisions of the manufacturer i is the same as in Chapter 4, each of which is added a subscript i (i=1,…,ε), e.g., d it represents the demand of manufacturer i in period t.

. Emission-Cap Regulation Policy

In this section, we study the policymaking decision problem for the government regarding the emission-cap regulation policy. The government needs to optimally determine the emission cap for each manufacturer to maximize the social welfare of the region. The emission cap for each manufacturer cannot exceed the environmental bearing capacity of the area the manufacturer is located.

We formulate the problem as a two-level Stackelberg game model in Section 5.2.1, and develop a hybrid algorithm to solve the problem in Section 5.2.2.

. . Mathematical Model

. . . Mathematical Formulation

A social welfare function commonly used in literature is the utilitarian welfare function, in which the social welfare is equal to the sum of individual utilities [START_REF] Karp | Social welfare in a common property oligopoly[END_REF]. This research considers two types of utilities: the positive economic utility benefiting from the profits and the neРative environmental utility caused by the damages of carbon emissions emitted by the manufacturers in the local region.

The social welfare function is given by

    g ec ecou ev envu W Φ Φ      
Equation Chapter 5 Section 2(5.2.1)

where () envu Φ  is the economic utility which depends on the total profits of all manufacturers.

() envu Φ  is the environmental utility caused by carbon emissions. α ec and ev are the weights of economic and environmental utilities in the social welfare, respectively.

Note that we must have α ec + ev < 1, since only two types of utilities of the social welfare are considered in our research.

According to [START_REF] Honma | Pollution tax and social welfare in oligopoly: asymmetric taxation on identical polluters[END_REF], the relationship between the environmental damage (denoted by env  ) and the amount of emissions must verify:

2 2 0, 0. env i env i AE AE              (5.2.2)
These relations indicate that both the environmental damage and the marginal damage will increase when increasing emissions. Without loss of generality, some researchers use nonlinear function to represent this relationship, such as quadratic environmental damage [START_REF] Weber | Carbon markets and technological innovation[END_REF], exponential environment consumption (Le [START_REF] Kama | The optimal control of pollution under the risk of irreversible degradation of the environment[END_REF].

In this research, the neРative environmental utility (i.e., the environmental damage) caused by the emissions of manufacturer i is defined as

  exp ( ) envu i i AE T R    .
Then, the environmental utility of the local region can be given by 1 exp ,

M i envu envu i i AE Φ TR              (5.2.3)
where is a parameter representing the environmental impacts caused by carbon emissions.

The higher , the more damage the environment suffers from the same amount of emissions. φ envu is a coefficient representing the relationship between the environmental utility and the environmental damage.

It is assumed that the price of each manufacturer"s product is known in a medium-term planning, then, the profit function of manufacturer i in a finite planning horizon T is given by

1 T i i it i t Pd F     (5.2.4)
where P i is the product price of the manufacturer i. F i is the cost of the manufacturer i over the planning horizon. Since

1 T i it t Pd  
is a constant, to maximize π i is to minimize the cost F i , according to the maximal theory.

Then, the economic utility of the region can be given by

1 M ecou ecou i i Φ     (5.2.5)
where φ ecou is a coefficient representing the relationship between the economic utility and the profits of the manufacturers.

According to the problem description, we formulate the problem as a two-level Stackelberg game model, named Model GM-5-I. The mathematical model includes two levels, i.e., the upper level and the lower level.

TСe upper level for the government to make decisions is achieved by the first Sub-model (named Sub-model G), including Eqs. (5.2.6)-(5.2.7). With Sub-model G, the government maximizes the social welfare by determining μ i " optimally, by observing the best responses of manufacturers.

TСe lower level for each manufacturer to make decisions is achieved by the second Submodel (named Sub-model M), including Eqs. (5.2.8)-(5.2.12). With Sub-model M, manufacturer i minimizes his overall costs of a planning horizon T, according to the emission cap μ i set by the government.

Model GM-5-I is formulated as follows.

Model GM-5-I: (5.2.12)

Maximize 1 1 1 1 () ( ) ( ) exp M T M M ii g ec ecou i it i i ev envu i t i i i AE W Pd F TR                           x μ x , (
In Sub-model G, the objective function (5.2.6) maximizes the social welfare, which consists of the economic utility (the first term) and the environmental utility (the second term). i F is the minimal overall cost and AE i is the total emissions of manufacturer i in a planning horizon, respectively. Note that both of them depend on the decision variable x ir = (x ir1 ,…,x irT ) and x iР = (x iР1 ,…,x iРT ). The percentages of economic utility and environmental utility in the social welfare are given by the weights α ec and ev , respectively. Constraint

(5.2.7) ensures that the emission cap of each period does not exceed the environmental bearing capacity of the area the manufacturer is located.

In Sub-model M, the objective function (5.2.8) minimizes the overall cost of manufacturer i. Constraint (5.2.9) ensures that inventory is balanced. Constraint (5.2.10) ensures the production emissions of the manufacturer do not exceed the emission cap in each period. Constraint (5.2.11) sets the initial and end inventory to be zero. The bounds of the decision variables are constrained by Eq. (5.2.12).

With Model GM-5-I, our objective is to find the optimal strategy (μ * , x i * ) that maximizes the social welfare W Р (µ), meanwhile, manufacturer i"s overall cost F i (x i ) is minimized with the given μ i . Note that we have x i * = (x iР * , x iР *

). Subsequently, the remaining work is to develop an efficient algorithm to solve the mathematical model.

. . . Problem Complexity

Model GM-5-I provides a way to obtain optimal solutions by utilizing a dynamic decision process:

The government first sets a group of values μ = (μ 1 , …, μ M ). Then, each manufacturer reacts to μ i and determines optimal x * i . The government calculates the social welfare W Р (µ) according to the responsive decisions x * i , and tries all possible μ to improve W Р (µ). All manufacturers are involved in the dynamic decisions and follow the government"s decisions. This dynamic process will not stop until the Stackelberg equilibrium is achieved. At the Stackelberg equilibrium, the government cannot improve the social welfare anymore; meanwhile, the manufacturers minimize their costs within the government"s given decisions.

In the Stackelberg game model, for any given μ i , any manufacturer i"s decision problem (i.e., Sub-model M) can be solved by Algorithm-4-PDP, a polynomial algorithm proposed in the Chapter 4. That is to say, x i * can be polynomially computed with given μ i . Therefore, the remaining work is to find the optimal μ * .

Before developing an algorithm to solve our problem, let us analyze the complexity of the model. Some simulations of the decision variables μ are conducted, in which we consider the scenario with only one manufacturer in the region and the results are given in see that the total emissions do not vary smoothly when varying μ i . That"s because the optimal emissions in each period may not be equal to the emission cap. These two reasons also explain why the social welfare curve is not smooth, and is multimodal (see Figure 5.1(c)). In other words, the objective function (5.2.6) is not concave in μ i , since the objective value may go up and down with the change of the manufacturer i"s decision variables x i , which makes F i (x i ) and () The analysis above shows that it is analytically intractable to solve the proposed model; even worse, to the best of our knowledge, it is impossible to solve μ with some combinatorial optimization approaches. Thus, we are encouraged to develop a hybrid algorithm to deal with these difficulties.

i i AE x discontinuous.

. . Solution Methodology

As referred in the previous section, the decision variables x i for each manufacturer i can be solved by Algorithm-4-PDP; the decision variables μ are analytically intractable, and cannot be solved by existing optimization methods. In the light of the complexity of our problem, an algorithm, which can cope with the nonconcavity and analytical intractability, is required to solve the proposed Stackelberg game model. Thus, the variables μ needs to be computed numerically, and develop a hybrid algorithm to solve the problem.

In the hybrid algorithm, GA is used to search the optimal or near optimal μ in numerical way, which can overcome the drawbacks of nonconcavity and multimodality of the objective function. Algorithm-4-PDP is in charge of solving x i with given μ i generated by GA. The global optimal strategy (μ * , x i * ) is obtained when the terminated condition of GA is satisfied.

. . . Genetic Algorithm for Computing μ

In GA, a population of chromosomes is generated and evolves toward optimal solutions. A chromosome corresponds to the solutions of Sub-model G. The initial generation of the population is commonly generated randomly [START_REF] Joines | A genetic algorithm for function optimization: A Matlab implementation[END_REF]. The chromosomes in subsequent generations are produced by using selections, mutations, and crossovers. The quality of a chromosome is evaluated by a fitness function. The fitness function is defined by the objective function (5.2.6) plus some costs for penalizing the constraint violations. That is, a sufficiently heavy penalty will be imposed if constraint (5.2.7) is violated. By using the fitness function, the chromosomes can be ranked from good to bad ones.

A solution corresponding to decision variables μ i "s is represented by a chromosome in GA, where μ i is the emission cap set to manufacturer i. The chromosomes in the generations afterwards are generated by three genetic operators, i.e., operators of selection, crossover and mutation. All parameters of these genetic operators are set to the same as those of the GA used in Section 3.2.2.3. Note that GA is similar to the one used in Chapter 3, so it is not described in detail here.

. . . Hybrid Algorithm

Up to now, the variables μ and x i are solved by GA and Algorithm-4-PDP, respectively.

We, therefore, present a hybrid algorithm combining these two algorithms to find the global optimal strategy (μ * , x i * ).

In the hybrid algorithm, GA is in charge of solving μ as outer loop of the algorithm; meanwhile, Algorithm-4-PDP is in charge of solving x i as inner loop with the given μ i generated by GA. The detailed procedures of the hybrid algorithm are given in Figure 5.2.

We first randomly generate a group of chromosomes representing solutions (μ 1 , …, μ ε ).

Under the given (μ 1 , …, μ ε ), we compute the optimal x * i (i.e., x * ir and x * iР ) by Algorithm-4-PDP and obtain the minimal F i and the related emissions AE i . Meanwhile, we can compute the social welfare W Р by Eq. (5.2.6).

Then, we update the chromosomes from generation to generation. In each generation, (μ 1 , …, μ ε ) are dynamically updated by the three genetic operators. With the given (μ 1 , …, μ ε ) updated in each generation, x * i and W Р are also updated. These processes continue until the termination condition of GA is satisfied, i.e., a convergence accuracy of 1.0×10 -6 for the fitness function is achieved.

Step 5: Update (μ 1 ,…, μ M ) by GA

Step 6: Output the best solutions (μ * 1 ,…, μ * M ), (x * itr , x * itg ) and the maximal social welfare W g

No Yes

Step 4: Is GA termination condition satisfied?

Step 1: Initialize (μ 1 ,…, μ M ) by GA

Step 2: Compute optimal (x * ir , x * ig ) by Algorithm-4-PDP and obtain F i and AE i

Step 3: Calculate the social welfare W g (μ) by Eq. (5.2.6)

Figure 5.2 Procedures of Algorithm-5-Hybrid-I

. Emission Cap-and-Trade Scheme

In the previous section, we study the government"s policymaking problem for a local government regarding the emission-cap regulation policy. Subsequently, this section considers the problem regarding the emission cap-and-trade scheme. We seek to maximize the social welfare of a local region by optimizing the emission-reduction target set by the government.

In the emission cap-and-trade scheme, the government sets an emission-reduction target (i.e., a percentage of emission reduction) and allocates tradable initial emission allowances to each manufacturer in the region. The government pays attention to the environmental issues and pursues a positive emission-reduction target in each year, i.e., ϕ>0.

An allowance allocation mecСanism is used to allocate the initial emission-allowance to manufacturers, which is based on the emission-reduction baseline and the emissionreduction target. The emission-reduction baseline is defined as the amount of average emissions of the industry when only regular technologies are used for production. For example, if the average emissions of producing one ton product by regular technologies (i.e., without using green technologies) in the industry are 2 tons CO 2 , the demand scale (represented by the customer demand) of a manufacturer is 100 tons, and the emission-reduction target for one year is 10%, then the initial emission allowances allocated to the manufacturer are 2×100×(1-10%) = 180 tons.

With tradable initial allowances, the manufacturers optimize their production planning and trade them with others in the region. All manufacturers share their emission-allowance demand information with each other, and the carbon price is market-based and formed automatically in the market. The optimal carbon price, i.e., equilibrium carbon price, can be obtained by solving a Cournot competition model.

According to the equilibrium carbon price, the manufacturers plan their production optimally. Similar to Section 5.2, all manufacturers plan their production over a horizon with the same number of periods. The government computes the social welfare by observing the reactive decisions of all manufacturers. In the same way as for the emissioncap regulation policy, the government maximizes the social welfare by dynamically determining the emission-reduction target under a Stackelberg game frame.

In summary, we solve our problem using a two-stage Stackelberg game model. In the model, the government determines the value of ϕ, and allocates initial emission allowances IE i to each manufacturer i by the allowance allocation mechanism. Then, all manufacturers react to IE i and trade their allowances in the market at an equilibrium carbon price.

Meanwhile, each manufacturer optimizes his production planning x * i optimally, and the government computes the social welfare W Р with the responses of the manufacturers" decisions x * i . The government changes ϕ to improve W Р until it cannot increase anymore.

The Stackelberg equilibrium is achieved by the dynamic decision process, and the optimal decisions of both the government and the manufacturers are obtained.

The remainder of this section is organized as follows. Our problem is formulated in Section 5.3.1, and Section 5.3.2 presents the solution methodology for the proposed model.

. . Mathematical Model

According to the emission allocation mechanism introduced above, the initial emission allowances allocated to manufacturer i are given by

1 1 1 1 1 (1 ) M T M T T i ir it it it i t i t t IE e d d d            

  

Equation Chapter 5 Section 3(5.3.1)

Eq. (5.3.1) implies that the initial emission allowances for a manufacturer depend on the average emissions of unit production with the regular technologies (i.e., without using green technology) in the industry and the market scale (i.e., the customer demand) of the manufacturer.

After all manufacturers obtain their initial emission allowances IE i , they plan their production and evaluate whether their allowances are enough for production (i.e., the spare amount for selling or the shortage to buy). They buy or sell allowances through the carbon-credit trading market in the local region, and the total tradable and available allowances in the market are

1 M i i TIE IE   
. The manufacturers adjust production planning to control their production emissions according to the market-based carbon price. The initial emission allowances will be consumed as many as possible but not exceed TIE.

In what follows, we discuss how to use a Cournot competition model (Cournot and Fisher, 1897) to obtain the equilibrium carbon price. The processes of optimizing such a carbon price can be analyzed under a frame of Cournot competition game: the total initial emission allowances correspond to the total demands of a market in a classical Cournot competition model; the actual emissions of the manufacturers correspond to the production quantities of firms; the carbon price corresponds to the price of the homogeneous product of firms; each manufacturer"s decision on actual emissions (depending on the decisions of production planning) affects the carbon price; the optimal carbon price is achieved when the total actual emissions of all manufacturers are equal to the total initial emission allowances allocated to them.

It can be seen that the process to obtain the equilibrium carbon price is to re-allocate the total initial emission allowances to the manufacturers by adjusting the carbon price optimally. The equilibrium carbon price will be achieved when the total actual emissions are equal to the total initial emission allowances, i.e.,

M M M Mt Mt Mt Mt M t AE F f x h I IE AE F f x h I IE AE F f x h I IE                                    x x x (5.3.2)
Note that, in this research, the total actual emissions may not be exactly to the total initial emission allowances because of the discreteness of the manufacturers" decision problem.

That"s to say, there may be some allowances that cannot be sold out and are kept in the hands of the manufacturers, i.e., the total actual emissions may be strictly less than the total initial emission allowances (i.e., TAE TIE



). Thus, in the next section, an ϵ-approximate optimal solution (on carbon price) is obtained by an algorithm based on dichotomy method and Algorithm-4-PDP.

In the emission cap-and-trade scheme, the initial emission allowances are freely allocated to manufacturers. Therefore, in the function of the social welfare, these economic utilities contributed by the initial emission allowances that are not sold out and kept in the hands of manufacturers should be deducted from the total utility. Then, the economic utility is

() M ecou ec ecou i i U TIE TAE             .
(5.3.3)

According to the Eqs. (5.2.3), (5.2.4) and (5.3.3), the welfare function is given as follows.

 

1 1 1 1 1 1 exp M T M M M M i g ec ecou i it i i i ev envu i i i t i i i AE W Pd F IE AE TR                                     . (5.3.4)
According to the analysis above, the government decision problem is to optimize the emission-reduction target ϕ. The carbon price is optimally computed by the Cournot competition model based on the initial emission allowances IE i "s. For the decision of each manufacturer i, only the decision variable x i (i.e., i can be represented by x i ) need to be computed according to Theorem 4.3.1 and the mathematical model in Section 4.3.1. The decision model of each manufacturer is the same as Model M-4-II-S.

Then the problem can be formulated as the following Stackelberg game model, named

Model GM-5-II. In the model, the government"s decisions are achieved by Eqs. (5.3.5)-

(5.3.7), named Sub-model G, while each manufacturer i"s decisions are achieved by Eqs.

(5.3.8)-(5.3.12), named Sub-model M.

Model GM-5-II: (5.3.12)

Maximize   1 1 1 1 1 1 ( ) ( ) ( ) () exp , M T M M M g ec ecou i it i i i i i i i i t i M ii ev envu i i W Pd F IE AE AE TR                                  x x x (5.3.5) Subject to 0   , (5.3.6) 1 1 1 1 1 (1 ) , M T M T T i ir it it it i t i t t IE e d d d                (
In Sub-model G, the objective function (5.3.5) is to maximize the social welfare including two parts. The first part is the economic utility benefitting from the profits of the manufacturers; the second part is the negative environmental externality caused by the carbon emissions. α ec and ev are the weights of economic and environmental utilities in the social welfare, and we have α ec + ev <1. Constraint (5.3.6) ensures that the emissions reduction must be implemented each year. Eq. (5.3.7) provides the way to allocate initial emission allowances.

Sub-model M is identical to Model M-4-II-S, thus we omit the details here.

As can be seen, similar to Model GM-5-I in the previous section, Model GM-5-II is also difficult to be solved. We, therefore, present a hybrid algorithm to deal with the difficulties by solving ϕ numerically.

. . Solution Methodology

In AE x . In order to find the global optimal ϕ, we must try all possible ϕ numerically till W Р cannot be further improved.

In the remainder of this section, we present a hybrid algorithm to solve all variables analyzed above. In the algorithm, GA is used to solve ϕ numerically; an algorithm based on dichotomy is developed to solve the Cournot competition model and obtain the optimal * ; and Algorithm-4-PDP is used to solve the manufacturers" decisions.

The following property will be helpful to solve the Cournot competition model.

Theorem 5.3.1. For any manufacturer, in an optimal production planninР, Сis actual emissions are non-increasinР witС tСe increase of carbon price.

Proof. The property can be proven by contradiction. Assume that there are two carbon prices and ′ > , such that the actual emissions under is strictly less than those under ′.

Let x and x′ be the production plans under and ′, AE and AE′ be the actual emissions under and ′. By the assumption, we have AE < AE′.

The costs corresponding to optimal production planning x (resp. x′) under carbon price C 2 . Then, we have that following inequalities:

F(x′) + (AE′ -IE) F(x) + (AE -IE) F(x) + (AE -IE) ′ F(x′) + (AE′ -IE) ′
By summing up these two equalities, we obtain:

(AE′ -IE) + (AE -IE) ′ (AE -IE) + (AE′ -IE) ′,
The equality above implies (AE′ -IE)( -′) 0, which is in contradiction with the fact that AE < AE′ and ′> . ■ With Theorem 5.3.1, the following corollary can be directly obtained, which indicates the relationship between the total actual emissions and the total initial emission allowances in the local region.

Corollary 5.3.1. In tСe local reРion, tСe total actual emissions are non-increasinР witС tСe increase of carbon price.

Corollary 5.3.1 tells us that the total actual emissions of manufacturers are negatively correlated to carbon price. With the property, an ϵ-approximate optimal solution can be obtained by dichotomy. We, thus, develop an algorithm, named Algorithm-5-CarbonPrice, to solve the Cournot competition model. In the algorithm, Algorithm-4-PDP is used to calculate the manufacturers" optimal decisions with a given , and a dichotomy method is used to find a ϵ-approximate optimal globally.

The detailed procedures of the algorithm are shown in Figure 5.3. We first initialize the lower and upper bounds of the carbon price by ( LB , UB ). Then, we test the middle of the interval ( LB , UB ), i.e., mid = ( UB -δB )/2, and obtain the actual emissions of each manufacturer i under mid by Algorithm-4-PDP. Subsequently, the total emissions of all manufacturers TAE mid is calculated, We update the bounds ( LB , UB ) and obtain the optimal carbon price * = ( UB -δB )/2 till the terminate condition (i.e., UB -δB < ϵ) is satisfied (i.e., the interval containing the optimal carbon price is narrow enough), or the total emissions of all manufacturers under mid are equal to the total initial emission allowances (i.e., TAE mid = TAE).

Step 6: * = ( UB -LB )/2

Step 7: Output the best solution *

No

Yes

Step 1: Initialize the lower and upper bounds of : ( LB , UB )

Step 3: Let mid = ( UB -LB )/2 and compute total emissions of all manufacturers TAE mid under mid

Step 5: Reset ( LB , UB )

If E mid < E, γ UB ← γ mid, Else (i.e., E mid > E),γ LB ← γ mid .
Step 2: UB -LB < ?

No

Step 4: TAE mid = TAE ? Yes Then, the chromosomes with value ϕ are updated from generation to generation. In each generation, ϕ are dynamically updated by the three genetic operators. With the given ϕ updated in each generation, x * i , * and W Р are also updated. These processes continue until the termination condition of GA is satisfied.

Step 8: Update ϕ by GA

Step 9: Output the best solutions ϕ * , (x * itr , x * itg ), * i and the maximal social welfare W g

No

Yes

Step 7: Is GA termination condition satisfied?

Step 1: Initialize ϕ by GA

Step 2: Compute the initial emission allowances E i by Eq. (5.3.1)

Step 3: Compute optimal * by Algorithm-5-CarbonPrice

Step 5: Compute optimal * i and related F i and AE i

Step 6: Calculate the social welfare W g (ϕ) by Eq. (5.3.5)

Step 4: Obtain optimal (x * ir , x * ig ) by Algorithm-4-PDP

. Numerical Examples

In this section, we provide some numerical examples to show the application of the mathematical models and algorithms studied in this chapter. The numerical examples include two types of emission-reduction policies, i.e., emission-cap regulation policy and emission cap-and-trade scheme. The computational results and sensitivity analysis are discussed in Section 5.4.1 and Section 5.4.2, respectively.

. . Emission-Cap Regulation Policy

We conduct a numerical example to test and analyze the emission-cap regulation policy studied in Section 5.2. The example involves 3 manufacturers (A, B and C) in the same industry in a local region. They produce a homogenous product and serve different retail markets. The government tries to establish an emission-cap regulation policy to maximize the social welfare of the local region. Therefore, she needs to optimally set the emission caps for the three manufacturers.

The manufacturers plan their production over a one-year planning horizon including 6 periods (2 months/period). The values of government-related and manufacturer-related parameters are randomly generated. The parameter values of government are given in Table 5.1. The demands to three manufacturers are given in Table 5.2, and some other parameters are given in Table 5.3 2 The computational results are given in Section 5.4.1.1. In section 5.4.1.2, we perform some sensitivity analysis to draw some interesting and valuable managerial insights.

. . . Computational Results

We test our example 10 times and give the related results as follows. The average social welfare in the 10 tests is 1.643 as shown in Table 5.4. The hybrid algorithm converges with 2 The units of measurement of these parameters are given as follows. the demand (d it ): tonne; the setup cost (s ir and s ir ): dollars per setup; the unit production costs (p ir and p iР ): 80 dollars per tonne; the emissions of unit product (e ir and e iР ): tonne CO 2 per tonne products; the inventory holding cost (С it ): dollars per tonne per month. a high robustness. As seen from Table 5.4, the maximal gap of the objective value is only 0.56%. Thus, we just give the key results of the "best" test, in which the social welfare is 1.653. The optimal emission caps for the manufacturers are 8.19, 14.14 and 22.49 thousand tons, respectively. The numbers of technologies used by the manufacturers are given in Table 5.5. Among the three manufacturers, manufacturer A produces in the greenest way since either his regular or green technology yields the least carbon emissions than the others. As shown above, the emission caps for the manufacturers are 8.19, 14.14 and 22.49 thousand tons, which are 64.28%, 80.24% and 91.10% of the environmental bearing capacity of the area they are located. This implies that, under such an emission-cap regulation, the government can benefit more from the greener manufacturers since their emissionreduction costs are less than those who need to spend high cost on emission reduction. The results in Table 5.5 also indicate this trend. The less green manufacturer C uses regular technology in 4 periods and the greener one (manufacturer A) only uses regular technology in 3 periods. However, it is unfair to the manufacturers who perform more efficiently in emission reduction. We, thus, expect that it will be better in the emission cap-and-trade scheme since they can benefit from the emission reduction by selling their spare emission allowances.

. . . Sensitivity Analysis

The parameter represents the government"s decision preference on the emission reduction. If she prefers environmental utility in the social welfare, she should set with a relatively high value to control carbon emissions at a low level. For the sake of convenience, we call an emission-reduction policy a severe reРulation policy when is set at a relatively high level. In contrast, we call it an easy reРulation policy.

In this section, sensitivity analysis of the parameter is conducted to explore some managerial insights. The value of is changed from 1.0 (a low value) to 3.0 (a high value)

to detect the corresponding changes. The results in Table 5.6 show the numbers of technologies used by the manufacturers when is equal to 2.0. Compared with the technology used in the scenario of = 1.8 (see Table 5.5), only manufacturer A uses two more times of green technology among three manufacturers. This implies that the government prefers to set a tighter emission cap for the greener manufacturer A since he spends the least cost on reducing the same amount of emissions among the three manufacturers. As referred in the previous section, it is unfair to the manufacturer who performances more efficiently in emission reduction. Some other results are given in Figure 5.5, which show that the parameter has significant influences on the social welfare, total costs, total emissions and emission caps.

With the results, we draw some conclusions as follows.

(1) significantly influences the social welfare. As can be seen from Figure 5.5 (a), the social welfare turns to be negative when goes up to 2.4. The reason is that the production costs of the manufacturers increase drastically under a severe regulation policy.

(2) Emission reduction cannot be achieved by increasing if it is at a high level.

When is set to a high-level value, the economic utility decreases, i.e., the cost goes up, more quickly than the incremental environmental utility benefiting from the emission reduction. As shown in Figure 5.5 (b), when is higher than 2.4, the manufacturers refuse to further reduce emissions and the emissions increase since the emission-reduction cost is too high.

. . Emission Cap-and-Trade Scheme

In this section, we provide a numerical example to show the application of the model and algorithm for the emission cap-and-trade scheme studied in Section 5.2. In the example, three homogenous manufacturers in the same industry are involved. The government tries to establish an emission cap-and-trade scheme by optimally determining the emission-reduction target and aims to maximize the social welfare of the local region. In the example, the parameters are identical those used in Section 5.4.1.

. . . Computational Results

The example is tested 10 times and the related results are provided as follows. Results

show that the hybrid algorithm converges to the global maximum with a high robustness since only one variable ϕ needs to solve numerically.

The social welfare is W Р = 1.763, and the equilibrium carbon price is = 38.13 dollars per ton. However, the optimal emission-reduction targets ϕ in these tests may be different due to the fact that the problem involved integer decision variables. They remain unchanged for insignificant variation of some parameters. The optimal ϕ obtained in the 10 tests are given in Table 5.7.

Here we just give some key results of the first test, in which the optimal emissionreduction targets ϕ = 31.39%. The initial emission allowances for the three manufacturers

. . . Sensitivity Analysis

In this section, sensitivity analysis is conducted with respect to the variable ϕ. Note that similar results can be obtained from the sensitivity analysis of to those under the emission-cap regulation policy, thus we it omit here.

Similar to in Section 5.4.1, we call the emission-reduction policy a severe reРulation policy if ϕ is high enough to limit the emissions at a low level. In contrast, we call it an easy reРulation policy.

The values of ϕ is changed from 0.10 (a low value) to 0.45 (a high value) to observe the corresponding changes. All results are given in Based on the results, some managerial insights are obtained as follows.

(1) The emission-reduction target ϕ significantly influences the social welfare.

However, the social welfare may remain the same when ϕ is set to be different but adjacent values, since the discreteness of our problem (caused by the setup cost).

This may also explain that the optimal ϕ could be different in 10 tests, even though the social welfare converges to the same value. As can be seen from (2) The emission-reduction target ϕ has significant influence on the carbon price. This is because ϕ directly affects the total initial emission allowances, which influences the carbon price significantly. As shown in Figure 5.6(d), the carbon price increases drastically from 18.84 to 34.10 dollars per ton by more than 80% when ϕ increases from 10% to 15%.

. Conclusion

This chapter studies policymaking decision problems for a local government on optimizing carbon emission-reduction policies, aiming to maximize the social welfare of a local region. Two types of social utilities, i.e., economic utility and environmental utility, are considered in the social welfare. Generally, a severe emission-reduction policy may increase environmental utilities at the cost of decreasing economic utilities.

However, an easy emission-reduction policy may increase the economic utilities at the cost of damaging the environment. Thus, the government should make a tradeoff between these two utilities by determining her emission-reduction policy appropriately.

To help the government optimize her emission-reduction policies, Stackelberg game models are formulated to describe and analyze the decision process between the government and the manufacturers. With the game models, the government can take the advantage of the leadership in observing the manufacturers" operational decisions reactive to her policymaking decisions. But the models are difficult to solve because of their non-convexity and non-continuity. To deal with these difficulties in solving the problem, hybrid algorithms combining genetic algorithm and polynomial dynamic algorithm are developed for the models. In particular, Cournot competition models are formulated to optimize the market-based carbon price under the emission cap-and-trade scheme.

Some numerical examples are conducted to show the application of our proposed models and the algorithm. From the results of these examples, we derive some valuable managerial insights, which are briefly listed as follows.

(1) The government can achieve the emission-reduction target by raising the value of (a parameter representing the government"s force on emission reduction), but it does not work when it goes up to a high level. In other words, a severe emissioncap regulation policy cannot be expected to achieve a high-level emissionreduction target.

(2) Under severe regulation policy with emission cap-and-trade scheme, the manufacturers, who perform more efficiently on emission reduction, are encouraged to use their green technologies more frequently and may benefit from selling their emission allowances.

(3) Sustained emission reduction can be achieved under the emission cap-and-trade scheme, and it may be also conducive to promote technology innovation. Thus, a cap-and-trade scheme, which is a market-based approach of providing economic incentives, is an efficient and effective policy instrument for emission reduction.

Therefore, determining the carbon footprint appropriately may provide the manufacturer with a good balance among the customer demands, governmental emission regulations and production cost.

Chapter 4 investigated a manufacturer"s medium-term operational decision problems considering government-imposed emission-reduction policies. MILP models were formulated to optimize the manufacturer"s decisions on technology selection and production planning under both emission-reduction policies, respectively. The objectives are to minimize overall costs over a finite production planning horizon.

The models are difficult to solve due to the special cost structure in the models which involve non-continuous production cost functions. However, a polynomial dynamic programming algorithm was developed based on a multi-level decomposition approach.

With the approach, a production plan is decomposed into a series of subplans that can be further decomposed into smaller subintervals. The subintervals include several kinds of production periods that are identified by the specified segments in the production cost function. The proposed algorithm can solve the problems under both policies in O(T 6 ) time, where T is the number of periods involved in the planning horizon. More specifically, a reformulation approach is used to analyze the model under the emission cap-and-trade scheme. Some interesting observations were obtained from numerical experiments:  An optimal technology selection and production planning strategy may help the manufacturer to obtain a good balance among emissions, production cost and inventory cost under government-imposed emission-reduction policies. Therefore, the manufacturer cannot only cope with the governmental emission regulation but also minimize his overall costs by this optimization.

 The technology selection strategy may remain the same when changing the carbon price under the emission cap-and-trade scheme. This is because the green technology will be used more often only if it generates more profit than setup cost. Stackelberg models were formulated to optimize the decisions on emission caps and emission-reduction-target for the emission-cap regulation policy and the emission cap-andtrade scheme, respectively. These models are difficult to solve since their non-convexity and non-continuity. However, we developed hybrid algorithms combining genetic algorithm and polynomial dynamic algorithm to solve the problems. Particularly, an initial emission allowance allocation mechanism was presented for the government to allocate initial emission allowances to the manufacturers, and a Cournot competition model was formulated to optimize the carbon price under the emission cap-and-trade scheme.

Numerical experiments were conducted to illustrate the application of the models and the algorithms. With the computational results and sensitivity analysis, we obtained some interesting managerial insights:  An emission-cap regulation policy may be unfair for those manufacturers who perform more efficiently in emission reduction. In contrast, a market-based emission cap-and-trade scheme could deal with this unfairness and allow the manufacturers great flexibility on emission reduction.

 Manufacturers who perform more efficiently on emission reduction may benefit from selling their emission allowances under a severe regulation policy under an emission cap-and-trade scheme. They are encouraged to use green technology more frequently.

 A market-based emission cap-and-trade scheme is more effective on emission reduction than an emission-cap regulation policy since it could promote sustained emission reduction by market-driven technology innovation.

. Future Research

Emission-reduction issues are receiving increasing attention from the academic community due to the opportunities and challenges they offer in OR/MS area. In this thesis, we have investigated the government"s policymaking decision problems regarding emission-reduction policies and the manufacturers" operational decision problems under these policies. The results show that these problems could be well solved using OR/MS approaches. However, there is still enough room for conducting further research. In what follows, we discuss some potential research questions that seems to be interesting from both theoretical and practical perspectives.

In chapter 3, several research questions regarding long-term strategic decisions are interesting and worthwhile to investigate. The following two research topics seem to be promising.

Sustainable supplier selection:

Sustainable supply chain pays attention to carbon footprint across a whole supply chain, while we just considered the carbon emissions at the side of the manufacturer in our research. It might also be interesting to investigate the carbon footprint at the upstream of the supply chain and reduce emissions of the total product life cycle. We discussed the retailer selection for the manufacturer to select customer markets. However, it may also prove worthwhile to investigate green supplier selection when determining the carbon footprint of products. These suppliers might be distinguished in some features such as carbon emissions of their materials, transportation cost, ordering cost, even the emissions in transportation and so on. The manufacturer should trade off the cost and emissions of each supplier and select some of them to make him most profitable.

Multi-product demand structure: In practice, manufacturers often face various customer markets. For example, customers have distinct preferences on the green feature of the same functional products. To well serve and satisfy their customers, manufacturers would produce multiple products which have the same functionalities but different in carbon footprint. In our research, a single product is considered and distinguished only by the carbon footprint. In the multi-product demand structure, manufacturers could provide multiple products in different markets and maximize their profits through appropriately determining the carbon footprint related to their customer markets. It also might be worthwhile to investigate the existing literature regarding product and market segment in order to formulate and solve the manufacturer"s decision problem with multi-product demand structure.

In chapter 4, several research questions regarding medium-term operational decisions are interesting and worthwhile to investigate. Two research topics are addressed as follows.

Production planning with pricing: In our research, the demand of the product is deterministic in medium-term production planning. It is also interesting and practical to consider the customers are price-sensitive and green-aware as discussed in long-term planning in Chapter 3. The closest literature to this topic is some research on joint lot sizing and pricing decisions [START_REF] Abad | Optimal pricing and lot-sizing under conditions of perishability, finite production and partial backordering and lost sale[END_REF][START_REF] Khouja | A joint optimal pricing, rebate value, and lot sizing model[END_REF], but almost none of them consider technology selection (or operation/production mode selection) issues. It could be expected to explore some efficient algorithm to solve the problem, since little research in the literature contributes on the algorithm even if technology selection is not investigated.

Nevertheless, the results may help manufacturers to maximize their profits by reacting to the customer demands flexibly.

Production planning with multi-product: As discussed above in "Multi-product demand structure", it also might be worthwhile to explore such a demand structure for manufacturers" medium-term operational decisions. Multi-item lot sizing problem is an important stream of literature in production planning, but, to the best of our knowledge, the existing research pays little attention on either the environmental issues or technology selection. However, it will bring great challenges to develop efficient algorithms to solve the problem since a general multi-item lot size model is proven to be NP-hard [START_REF] Afentakis | Optimal lot-sizing algorithms for complex product structures[END_REF]. Thus, it will be encouraged to investigate some heuristic algorithms to deal with these difficulties.

To complete the research of Chapter 5, it might be interesting to discuss policymaking decision problems in which product-market competition is considered in operational manufacturers" decisions.

Product-market competition:

In the product-market competition scenario, customers can choose products among the manufacturers, while the manufacturers should determine the price and carbon footprint of their products appropriately to compete one with another in the markets. In this situation, it is expected to be much fairer for the government to impose emission-reduction polices on the manufacturers in her administrated region, since the emission cap or the initial emission allowances are set or allocated according to the manufacturers" demands, which depend on the manufacturers" production capacity and competition ability. However, due to the reactive decision process between the government and manufacturers, the complexity of the problem may make it difficult to solve.

Figure 1 . 1

 11 Figure 1.1 Carbon emissions in supply chain (Product carbon footprint) ..............................

Figure 1 . 2

 12 Figure 1.2 Decision processes of government and manufacturers .........................................

Figure 2 . 1

 21 Figure 2.1 Framework of literature related to our research ..................................................

Figure 2 . 2

 22 Figure 2.2 Framework of literature regarding partner selection ..........................................

Figure 2 . 3

 23 Figure 2.3 Framework of literature on production planning ................................................

Figure 3 . 1

 31 Figure 3.1 Pseudo codes of Algorithm-3-DP .......................................................................

Figure 3 . 2

 32 Figure 3.2 Procedures of Algorithm-3-Hybrid .....................................................................

Figure 3 . 3

 33 Figure 3.3 Impacts of emission cap Ē ..................................................................................

Figure 4 . 1

 41 Figure 4.1 The production cost curves .................................................................................

Figure 4 . 2

 42 Figure 4.2 Pseudo codes of Algorithm-4-PDP .....................................................................

Figure 4 . 3

 43 Figure 4.3 The actual production cost curves .......................................................................

Figure 4 . 4

 44 Figure 4.4 Impacts of emission cap ......................................................................................

Figure 4 . 5

 45 Figure 4.5 Impacts of carbon price .......................................................................................

Figure 5 . 1

 51 Figure 5.1 Simulations of the objective function by changing μ i .......................................

Figure 5 . 2

 52 Figure 5.2 Procedures of Algorithm-5-Hybrid-I ................................................................

Figure 5 . 3

 53 Figure 5.3 Procedures of Algorithm-5-CarbonPrice ..........................................................

Figure 5 . 4

 54 Figure 5.4 Procedures of Algorithm-5-Hybrid-II ...............................................................

Figure 5 . 5

 55 Figure 5.5 Impacts of parameter (I) .................................................................................

Figure 5 . 6

 56 Figure 5.6 Sensitivity of variable ϕ ....................................................................................

  Emission-reduction pledges under Copenhagen Accord ........................................

  (thousand dollars) ................................................................ Table 4.1 Monthly demands (thousand tons) ....................................................................... Table 4.2 Computational results (I) ...................................................................................... Table 4.3 Computational results (II) ..................................................................................... Table 5.1 Parameter values of the government .................................................................. Table 5.2 Demands to the manufacturers (thousand tons) ................................................. Table 5.3 Parameter values of the manufacturers ............................................................... Table 5.4 Social welfare ..................................................................................................... Table 5.5 Numbers of the technologies used by the manufacturers ................................... Table 5.6 Numbers of the technologies used by three manufacturers ( = 2.0) ................. Table 5.7 Optimal emission-reduction targets .................................................................... Table 5.8 Numbers of the technologies used by three manufacturers ................................

Figure 1 . 1

 11 Figure 1.1 Carbon emissions in supply chain (Product carbon footprint)

Figure 2 . 1

 21 Figure 2.1 Framework of literature related to our research

Figure 2 . 2

 22 Figure 2.2 Framework of literature regarding partner selection Contemporary OR/MS research offers a range of methods and techniques that may support the supplier-selection decision makers in dealing with the complicated decisions. The vast majority of the decision models applied to the supplier selection are multi-criteria approaches and mathematical programming methods. This subsection investigates the existing studies regarding supplier selection from a technique-oriented perspective, such that studies are classified into multi-criteria and mathematical programming based approaches. In addition, game theories are often applied to analyze multi-player decision process in supply chain. Research related game theory in supply chain is also investigated in this section. In what follows, literature is reviewed based on this classification.

  model the Chapter 2 real cost structures of customer-supplier relationships through a trust game theory. They provide empirical data regarding the potential benefits of interfirm trust in three different relationships of an actual supply-chain. Results show interfirm trust can decrease the transaction costs of the relationship and provide competitive advantage for partner selection.

Figure 2 . 3

 23 Figure 2.3 Framework of literature on production planning . . . Single-item Lot Sizing Problem

  show the cases of NI/G/NI/ND, NI/G/NI/C, C/Z/ND/NI and ND/Z/ND/NI can be solve by O(T 4 ), O(T 3 ), O(TlogT) and O(T)

  discuss a lot size model with production capacity and storage capacity. A forward dynamic programming algorithm is developed and solves the problem in O(T 3 ) time. Time windows constraints: Jaruphongsa et al. (2004a) study a two-echelon dynamic lot-sizing model with demand time windows. They respectively consider the effects of backlogging to the model and provide O(T 3 ) and O(T 5 ) algorithms to solve the models without or with backlogging. Different from their previous work, Jaruphongsa et al. (2004b) discuss a lot-sizing model with delivery time window and warehouse space capacity constraints, where delivery time windows and capacity of the warehouse are limited. To optimally solve the model, an O(T 3 ) algorithm is developed based on dynamic programming approach. Hwang et al. (2010) investigate a capacitated single item lot-sizing problem with production time windows, in which n types of demands (similar to n-item demand) are involved in production. They propose an O(nT 3 ) dynamic programming algorithm to solve the model.

  [START_REF] Hoen | Effect of carbon emission regulations on transport mode selection in supply chains[END_REF] evaluate the effects of different emission regulations on the companies" transport mode selection strategies, which based on the trade-off between inventory, transport, and emission costs. Their results show that even though significant emission reduction can be achieved by different transportation mode selection strategies, the decision depends on the regulation policies. Some other literatures are related to our research.[START_REF] Cheng | Logistics for world-wide crude oil transportation using discrete event simulation and optimal control[END_REF] consider multi-mode transportation (pipelines and tankers), stochastic crude oil inventory/transportation problems. They develop a decision support system to investigate and improve a solution based on discrete-event simulation. Jaruphongsa et al. (2005) generalize a classical lot sizing model by considering multi-mode replenishment. They develop a polynomial algorithm based on the network flows for a two-mode scenario. The setup cost and the replenishment capacity are not considered in their model. Sandra Duni (2009) discuss a lot sizing problem with multi-mode replenishment. The firm"s decisions includes: the timing for an order, the choice of shipment modes, and the order size for each mode. They formulate the problem as a mixed-integer programming model and develop a primal-dual algorithm to generate tight lower and upper bounds.

  To the best of our knowledge,[START_REF] Absi | Lot-sizing with carbon emission constraints[END_REF] first address a lot sizing model with emission constraints. In their model, they focus on a multi-item lot sizing problem, in which production is constrained by limit emissions.[START_REF] Montréal | The economic lot-sizing problem with an emission constraint[END_REF] presents a lot sizing model considering emission constraint. They address the constraint by emission in both production and inventory and declare a global restriction over all periods. Setup cost is not included in their model.[START_REF] Heuvel | Finding pareto optimal solutions for the multi-objective economic lot-sizing problem[END_REF] give a multi-objective economic lot-sizing model with emission and setup cost. Different with[START_REF] Montréal | The economic lot-sizing problem with an emission constraint[END_REF], they consider the emission constraint in each period and the global horizon. The problem is shown to be NP-complete and some special classes can be solved in polynomial time.Recently,Absi et al. (2013a) present a series of lot sizing models with four different kinds of emission constraints. The four types of carbon emission constraints are: periodic carbon emission constraint, cumulative carbon emission constraint, rolling carbon emission constraint and global carbon emission constraint. For the first model, they provide a polynomial algorithm for finding the optimal solutions. However, the production in their model actually is not capacitated. They prove the latter three models to be NP-hard but not give any algorithms. Some other literatures are related to this research,[START_REF] Hua | Managing carbon footprints in inventory management[END_REF] study the inventory and order policies under a carbon emission trading mechanism. They use an EOQ model to obtain the optimal order quantity considering emission trade. They also analyze the impacts of carbon trade, carbon price and emission cap on ordering decisions.[START_REF] Gong | Optimal production planning with emissions trading[END_REF] investigate the production planning and emission trading problem in a dynamic production system, in which a manufacturer produces a single product to satisfy random customer demand. They optimize the inventory control and technology selection policies, and the emission trade policies for a finite planning horizon.[START_REF] Benjaafar | Carbon footprint and the management of supply chains: insights from simple models[END_REF] propose a series of traditional lot sizing models to illustrate the impact of carbon emission concerns on the operational decisions of procurement and production planning. Their results show that operational adjustments alone may lead in some cases to significant emission reduction without significant increases in costs.In summary, although researchers are paying more and more attention to environmental issues on the research of production planning (i.e., lot sizing problem), little literature considers emission regulations on operational decision issues. More specifically, few studies investigate the technologies selection issues (i.e., multi-mode production) under the consideration of emission-regulation constraints (especially when production limitation is involved).

  Section 3.1 describes the problem in detail and defines the notation used in this chapter. Section 3.2 formulates a Stackelberg game model for the problem and develops a hybrid algorithm to solve the proposed model. Section 3.3 conducts some numerical examples and provides sensitivity analysis to illustrate the application of the models and algorithms. Section 3.4 summarizes this chapter.

  the long-term planning, therefore, the manufacturer can determine the carbon footprint by m , since e r and e Р are constant.

  .2.22)Observing the model above, the remaining work is to solve the manufacturer"s decisions c p , m and x. As referred the complexity and difficulty of solving the model, we have to know c p and m numerically in order to obtain the value of x. Furthermore, as soon as c p and m are known, a corresponding optimal value of x can be obtained by solving a knapsack problem.Therefore, the optimal strategy requires optimal values of c p and m . Unfortunately, it is impossible to get an analytical expression of ' m  in function of c p and m , because it is impossible to write the analytical expression of x. Thus, c p and m , need to be solved numerically.Once the values of c p , m , y * and p * are obtained, we can substitute them into Sub-model M-I and obtain a typical knapsack-problem, which is given by the following model, namely, Sub-model M-II.

1k

  based on a known optimal solution at stage k-1 can be realized

.

  According to our computational experiments, this algorithm is quite efficient. It is very accurate with the above mentioned granularity of

Figure 3 . 1

 31 Figure 3.1 Pseudo codes of Algorithm-3-DP The Procedures of Hybrid Algorithm In the analysis above, the optimal strategies of the retailers are solved analytically, c p and m are obtained numerically by GA, and x is solved optimally by a dynamic programming algorithm for given values of c p and m . Thus, we are encouraged to develop a hybrid algorithm, named Algorithm-3-Hybrid, to solve our proposed model efficiently. The procedures of Algorithm-3-Hybrid are given in Figure 3.2. As shown in Figure 3.2, our algorithm is designed to effectively use the advantages of various methods. Considering the non-concavity of the objective function (3.2.7) and constraint (3.2.8), we present GA to solve c p and m (see Subsection 3.2.3.1 in detail). We first generate c p and m , and update y * and p * analytically (see Subsection 3.2.3.1 in detail). Meanwhile, x * is updated by Algorithm-3-DP (see Subsection 3.2.3.2 in detail). Finally, the global near-optimal values of c p and m are obtained, and y * , p * and x * are updated simultaneously.

Figure 3 . 2

 32 Figure 3.2 Procedures of Algorithm-3-Hybrid

  p r = 60 dollars per ton, p Р = 80 dollars per ton. The emissions of unit product: e r = 2 tons CO 2 per ton products, e Р = 1 ton CO 2 per ton products.

Figure

  Figure 3.3.

  Figure 3.3 Impacts of emission cap Ē

  Figure 4.1 The production cost curves

  the holding inventory costs and t+1,k (•,•) is the minimal cumulative cost from t+1 to k. The three subcases imply that there is no production, full emission production with technology-r and full emission production with technology-g in period t, respectively.

  1 Initializing F(k) /*Initializing tСe total cost F(k)*/ Initialize F(0) = 0 Step 2 Solving subplan (i, j, k) /*computing the minimal cumulative cost c(i, j, k) */ a) Decomposing subplan into subintervals Decompose (i, j, k) into subintervals (i, j-1) and (j, k) by a singular period j. b) Calculating minimal cumulative costs of subintervals Calculate the minimal cumulative cost of subinterval (i, j-1): α i , j-1 (m r , m Р ); Calculate the minimal cumulative cost of subinterval (j, k): j, k (n r , n Р ); Calculate the minimal cost of singular period j: Y i, j, k (m r , m Р , n r , n Р ). c) Calculating minimal cumulative cost of subplan (i, j, k) Calculate all possible c(i, j, k)"s. Step 3 Solving the problem globally /*Computing the objective function dynamically)*/ Calculating all possible F(k) by Eq.(4.2.40).

Figure 4 . 2

 42 Figure 4.2 Pseudo codes of Algorithm-4-PDP

  and integrated into the objective function (4.3.3), since it can be easily proven that the inequality relationship must be equality at optimum. Similar to Model M-4-I in the previous section, we formulate the problem as a following model, named Model M-4-II, as follows.

  If the manufacturer"s total emissions of the planning horizon exceeds the initial emission allowances, i.e.,

  by Eqs. (4.3.12) -(4.3.14) as follows.

Figure 4 . 3

 43 Figure 4.3 The actual production cost curves

  s r = 90 thousand dollars per setup, s Р = 200 thousand dollars per setup. The unit production costs: p r = 60 dollars per ton, p Р = 80 dollars per ton. The emissions of unit product: e r = 2 tons CO 2 per ton products, e Р = 1 ton CO 2 per ton products. The inventory holding cost: С t = 2 dollars per ton per month.

  Figure 4.4 Impacts of emission cap

  200 thousand tons. The carbon price: = 15 dollars per ton CO 2 . The actual unit production cost: p' r = p r + e r = 60 + 2*15 = 90 thousand dollars per ton, p' Р = p Р + e Р = 80 + 1*15 = 95 thousand dollars per ton.

  Figure 4.5 Impacts of carbon price

  Figure 4.5(a). That is because the manufacturer uses green technology more frequently when the carbon price increases (see Figure4.5(c)) to reduce the quantity of carbon credits to buy, even sell his spare emission Figure4.5(b)). If we increase the unit production cost of the green technology to 160 dollars per ton, the cost will increase remarkably by 39.08%.

Figure 5. 1 .

 1 Figure 5.1. As shown in Figure 5.1, both curves in (a) and (b) are non-continuous but multimodal. In

Figure 5

 5 Figure 5.1(a), the profit curve is not smooth with the changes of μ i . In Figure 5.1(b), we can

( a )

 a Figure 5.1 Simulations of the objective function by changing μ i

  1

(

  resp. ′) are: C 1 = F(x) + (AE -IE) and C 2 = F(x′) + (AE′ -IE) ′. The costs corresponding to production planning x′ (resp. x) under carbon price (resp. ′) are: C 3 = F(x′) + (AE′ -IE) and C 4 = F(x) + (AE -IE) ′. By the optimality of x and AE under , and x′ and AE′ under ′, we have C 3 C 1 and C 4

Figure 5 . 3

 53 Figure 5.3 Procedures of Algorithm-5-CarbonPriceUp to now, all variables except ϕ are solved. As referred in the analysis above, ϕ needs to be solved numerically. Observing only one variable needs to be computed numerically, we use GA to solve ϕ. In GA, all parameters used are set to the same values as the GA of Algorithm-5-Hybrid-I. Then, a hybrid algorithm is developed to compute the values of all variables. In the algorithm, Algorithm-4-PDP and Algorithm-5-CarbonPrice are in charge of computing x i and , respectively. GA is used to solve ϕ.The procedures of the hybrid algorithm are given in Figure5.4. Firstly, a group of chromosomes including one gene ϕ are randomly generated by GA. Under the given ϕ, the initial emission allowances are computed by Eq. (5.3.1). The optimal carbon price * can be computed by Algorithm-5-CarbonPrice and the optimal x * i (i.e., x * ir and x * iР ) can be obtained by Algorithm-4-PDP. Meanwhile, the optimal trading allowance quantity * , the minimal F i and the related emissions

Figure 5 . 4

 54 Figure 5.4 Procedures of Algorithm-5-Hybrid-II

  Figure 5.5 Impacts of parameter (I)

  are57.33, 81.53 and 108.29 thousand tons, respectively. The actual emissions of the manufacturers are 56.84, 80.84 and 107.37 thousand tons. The trading emission allowances of the manufacturers are -10.84, 7.16 and 1.27 thousand tons, which implies that manufacturers B and C should buy carbon credits from manufacturer A. The total spare allowances that remain in the hands of the manufacturers (cannot be sold out) are 2.42 thousand tons, which is 0.99% of the total initial emission allowances. The numbers of technologies used by the three manufacturers are the same in 10 tests, which are given in

*

  There is no production in such a period.

Figure

  Figure 5.6 Sensitivity of variable ϕ

Figure 5

 5 Figure 5.6(a), maximal social welfare keeps at 1.44 when ϕ changes from 0.15 to 0.20. Figure 5.6(c) and (d) also tell the truth that both the actual emissions and the carbon price remains the same when ϕ increases from 0.15 to 0.20. This is because the optimal production planning does not change when ϕ changes from 0.15 to 0.20.



  A market-based regulation policy has its advantages of promoting manufacturer self-motivated emission reduction. Chapter 5 optimized the government"s policymaking decisions on emission-reduction policies, aiming to maximize the social welfare of the local region. With a frame of Chapter 6 130 Stackelberg game, the government can dynamically improve the social welfare by taking the advantage of observing the manufacturers" optimal reactions regarding operational decisions.

Table 2 .

 2 1 Summary of approaches for partner selection ......................................................Table 2.2 Summary of algorithms for capacitated single-item lot sizing problem .............. Table 2.3 Summary of studies most relevant with this research .......................................... Table 2.4 Taxonomy of emissions-reduction policies .......................................................... Table 3.1 Parameter values of 10 candidate retailers ........................................................... Table 3.2 Maximal profit of the manufacturer (×10 5 dollars) .............................................. Table 3.3 Profits of retailers π i

Table 1 .

 1 1 Emission-reduction pledges under Copenhagen Accord

	Country	Commitment to limit emissions by 2020, relative to various base years
	Australia	5% to 25% below 2000 level;
		Moving above 5% is conditional on a global, comprehensive agreement.
	China	40% to 45% cut to 2005 emissions intensity level;
		Increase the proportion of non-fossil fuels used in primary energy consumption to
		15%, and increase forest coverage by 40 million hectares and forest stock volume by
		1.3 billion cubic meters relative to 2005.
	Germany	20% to 30% below 1990 level;
		Moving above 20% is conditional on a global agreement for the period beyond 2012.
	India	20% to 25% cut to 2005 emissions intensity level.
	Japan	25% below 1990 level;

  model involves a single item or multiple items. The framework of literature regarding partner selection can be briefly classified and stated by Figure 2.2.

		Partner selection
		Supplier selection
	Single source	Multiple sources
	Single item	Multiple items	Single item	Multiple items
	represents the issues focused in this research.
	There are vast majority of studies concerning partner selection, especially
	supplier/vendor selection. To classify them, a first distinction can be made by considering
	whether single sourcing where demands are procured from the best supplier or multiple

sourcing where they are split and satisfied by several suppliers

[START_REF] De Boer | A review of methods supporting supplier selection[END_REF]

. In addition, as reported by

[START_REF] Aissaoui | Supplier selection and order lot sizing modeling: A review[END_REF]

, another distinction can be made by considering whether the

Table 2 .1 Summary of approaches for partner selection Multi-criteria approaches

 2

		single sourcing	multiple sourcing
		single item	multiple items	single item	multiple items
	AHP DEA FST	Ghodsypour and O'Brien (1998), Chan (2003)		Akarte et al. (2001), Liu and Hai (2005), Pang and Bai (2013), Shaw et al. (2013) * Liu et al. (2000), Talluri and Narasimhan (2004), Wu (2009), Ramanathan (2007) Pang and Bai (2013), (2011) * , Lee et al. (2009) *	Wang et al. (2004) Kilic (2013) Saen (2006), Saen (2007), Ha and Krishnan (2008) Kilic (2013), Ordoobadi (2009), Amid et al. (2011), Zeydan et al. (2011), Chan et al. (2008), Chan and Kumar (2007)
	Mathematical programming models
		single sourcing	multiple sourcing
		single item	multiple items	single item	multiple items
	LP			Stanley et al. (1954), Talluri and Shaw et al. (2012) Narasimhan (2003), Ng (2008),	Chappell (1974)
	MP MOP GP	Talluri (2002)		Ghodsypour and O"Brien (2001), Cao and Wang (2007), Che et al. (2009), Li et al. (2009), Mendoza and Ventura (2010), Hong et al. (2005) Wu et al. (2010), Weber and Current (1993), Liao and Rittscher (2007), Wu et al. (2009), Hammami et al. (2003), Hajidimitriou and Georgiou (2000) Azadi et al. (2013), Ho et al. (2013)	Kasilingam and Lee (1996), Degraeve et al. (2000), Murthy et al. (2004), Mansini et al. (2012) Wadhwa and Ravindran (2007), Narasimhan et al. (2006), Jolai et al. (2013) Karpak et al. (1999), Wang et al. (2004), Pati et al. (2008), Wang et al., 2013, Wang et al. (2013)

Game models used in supply chain

		partner selection	non selection
	at the side of buyer at the side of supplier	Talluri (2002), Laaksonen et al. (2009)	Wu et al. Wu et al. (2005), Bichescu and Fry Bichescu and Fry (2009), Yu et al. (2009), Viswanathan Viswanathan (2009), Tyan and Wee (2003), Netessine and Rudi (2004), Chen et al. (2010)
	overall benefits of the system		Gheidar Kheljani et al. (2009)
	Note: * indicates that environmental feature is considered in supplier selection.

Table 2 .

 2 2 Summary of algorithms for capacitated single-item lot sizing problem

	Polynomial Algorithm
	Special cases Variants	Problem NI/G/NI/ND NI/G/NI/C C/Z/ND/NI ND/Z/ND/NI G/G/G/C -bounded inventory time windows constraints bounded order quantity	Complexity O(T 4 ) O(T 2 ) O(T 3 ) O(TlogT) O(T) O(T 4 ) O(T 3 ) -O(T 3 ) O(T 3 ) &O(T 5 ) O(T 3 ) O(nT 3 ) * O(T 3 ) O(T 3 )	Authors Bitran and Yanasse (1982) Chung and Lin (1988) Heuvel and Wagelmans (2006) Bitran and Yanasse (1982) Bitran and Yanasse (1982) Bitran and Yanasse (1982) Florian and Klein (1971) Hoesel and Wagelmans (1996) Baker et al. (1978) Lotfi and Yoon (1994) Love (1973) Pochet and Wolsey (1993) Sandbothe and Thompson (1993) Jaruphongsa et al. (2004a) Jaruphongsa et al. (2004b) Hwang et al. (2010) Okhrin and Richter (2011b) Hellion et al. (2012)	Techniques DP, geometric algorithm DP DP DP DP DP DP DP, greedy algorithm B&B B&B, graph search DP DP DP DP DP DP DP DP
	Pseudo-polynomial
	Problem general cost function piecewise linear costs alternative machines	Complexity O(T 2 c̄d ̄) O(T 2 q̄d ̄) --	Authors Florian et al. (1980) Shaw and Wagelmans (1998) DP DP Akbalik and Penz (2009) DP	Techniques
	Heuristics

Table 2 .

 2 3 Summary of studies most relevant with this research

		Emission issues	Multi-mode production
	uncapacitated Lot sizing	Montréal (2011) Benjaafar et al. (2012)	Sandra Duni (2009), Jaruphongsa et al. (2005), Sandra Duni (2009)
	problem	Absi et al. (2013), Gong and Zhou (2011)
	capacitated Lot sizing	Benjaafar et al. (2012)	Akbalik and Penz (2009) (pseudo-polynomial algorithm)
	problem

Table 2

 2

	.4 Taxonomy of emissions-reduction policies
	Direct regulatory instruments	Incentive-based instruments
	Mandatory emission cap	Emissions trading scheme (e.g., cap-and-trade)
	Renewable energy certificate scheme	Emissions tax
	Electricity supply or pricing regulation	Fuel or resource tax
	Technology standard	Emissions abatement subsidy
	Performance Standard
	Fuel content mandate
	Energy efficiency regulation
	Source: Productivity-Commission (

Table 3

 3

		.1 Parameter values of 10 candidate retailers
	i 1	K i 14500	a i 91	b i 2800	ω i 13000	i 12
	2	13000	79	800	10000	17
	3	17500	120	1720	16000	20
	4	21000	123	1100	12000	11
	5	12000	96	1600	14000	25
	6	13000	75	1650	8000	15
	7	14600	80	2400	21000	20
	8	11000	106	1720	8000	18
	9	19000	81	2300	25000	46
	10	14000	52	3200	15000	15

Table 3

 3

	.2 Maximal profit of the manufacturer (×10 5 dollars)
	Test No.	1	2	3	4	5	6	7	8	9	10	Average
	π m	1.8733 1.8733 1.8733 1.8732 1.8732 1.8731 1.8733 1.8733 1.8733 1.8733 1.8732
	Gap(%) * 0.002 a 0.002 0.002 0.000	0.000 -0.007 b 0.002 0.002 0.002 0.002	0
	*Gap=(π m -Average)/Average; a and b are the best and worst objective values in the 10-time tests, respectively.

Table 3 .

 3 3 Profits of retailers π i (thousand dollars)

	i	1	2	3	4	5	6	7	8	9	10
	WitС selection	0(0.68) * 13.58 0(0.02) 36.15 0(-13.55) 4.84 0(3.11) 0(-51.97) 0(91.18) 31.10
	WitСout selection	0	5.20	-1.46 17.22	-22.05	2.85	3.36	-69.11	90.21	56.70
	Change(%)	-	61.72	-	52.37	-	41.08	-	-	-	-82.31

*

  , this function does not match our research well since it is intricate to determine x tr and x tg simultaneously. Thus, in what follows, we try to explore some properties of the problem and reformulate this production cost function into the actual function including only one decision variable x t . As a consequence, we can separately optimize the decisions of production planning and the technology selection. By a variable substitution x t = x tr + x tg in Model M-4-I, we have x tg = x tx tr . Then, Model M-4-I can be rewritten as follows.

	Model M-4-I-T
	Minimize	F	( , ) r xx			1  T  t	 	( ) tr s x r  g s x x ( t tr  	)		r tr p x		( p x x g t tr 	)	 		1  T  t	t t h I	(4.2.13)
	Subject to	t I d I t  	t	1 		, 1,..., , x t t T 				(4.2.14)
		( e x e x x r tr g t tr  	)			, 1,..., , t T 				(4.2.15)
		T I 	0,														(4.2.16)
		0	tr x  	, 1,..., , x t t T 					(4.2.17)
		I	t	0, 1,..., . t T 								(4.2.18)

  From the analysis above, it can be seen that the production cost Р(x) is a piecewise nondecreasing linear function of x on [0, μ/e Р ]. As a consequence, the actual production cost function Р(x) can be formulated as follows.

			If μ/e r <x μ/e Р , we have ( , ) xx   ( , 0) , x	g   s	, p x g	and ( , ) r g g x z s s p x   
	( 	) p p z g r 	is a decreasing function of z, when 0<z<x. The second term of Р(x), i.e.,
	z	(   	0 min )/( g zx e x e e r g  	)	( , ), xz	gets the minimal value when z gets the maximal value, i.e.,
	z	(   	) ( e x e e g r g 	),	which gives ( ) g x s   g	min[	, p x s g r		g r p p r g e e  g r r p e p e r g g e e   	x	].
	Therefore, let	x			( e s e e g r r g  	) [ ( g e p p g r 	)]	, we obtain
			() gx	g r s p x g g s s         	,	, . e x x g r x x / e   , g r r g r g p e p e x e e    r g p p g r e e     
					() gx	     	() () a b g x ( ), ( ), otherwise. rg e x e gx  	,	(4.2.27)
	where	x			( e s e e g r r g  	) [ ( g e p p g r 	)]	, () ()
												0,	x	0,
												r s p x r	,	0	x	r e	,
					() a g x ( )	r s s	g	g r p p r g e e	g r r p e p e r g g e e	x	,	r e x x	,
												gg s p x	,	.2.26) represent minimal
	production costs when only technology-r, both technologies, and only technology-g are
	chosen for production, respectively. In what follows, we analyze the minimal production
	cost Р(x) according to the value of x.
			If 0<x μ/e r , we have ( , ) x x s p x , r r 	( ,0) x	, s p x s p x g g r r    	and ( , ) r g x z s s 
		( p x p g g 		) p z s s r r    g	( p x p g g 		) p x s s r r    g	r p x s p x r r  	,	when 0<z<x.
	Therefore, we obtain () rr g x s p x 	.

a gx and () () b g x are given by Eqs. (4.2.28) and (4.2.29) as follows.

  If I t = 0, we call t a zero inventory point. TСere are at least two zeroinventory periods for any feasible production plan since I 0 = I T = 0 is assumed.

	Singular period: If	t x		{0,	,  r e	g e	}	, we call t a sinРular period.
	Zero Inventory Point: Subplan: A production plan can be decomposed into a series of subplans (i, k), 0 ≤ i < k ≤
	T, in wСicС periods i and k are two adjacent zero-inventory points. An subplan beРins witС
	a production period and ends witС a zero-inventory period from i+1 to k, satisfyinР tСe
	demands d i+1 , ..., d k .
	period: If	t x		{0,	,  r e	g e	}	, we call t a normal period. In a normal period,

eitСer a sinРle tecСnoloРy is used for production and emissions are equal to tСe emission cap, or tСere is no production.

  and the relationship n Р = QP   . Since α i , j-1 (m r , m Р ) and j, k (n r , n

	4.2.39)
	where m r , m Р , n r and n Р are constrained by Eqs. (4.2.32) and (4.2.35), 0 ≤ m r + m g + n r + n g ≤
	k-i,

Р ) can be computed in O(T 4 ) time, and Y i, j, k (m r , m Р , n r , n Р ) can be computed in O(T 6 ) time, all possible c(i, j, k)"s can be computed in O(T 6 ) time.

Table 4 .

 4 1 Monthly demands (thousand tons)

	Period	1	2	3	4	5	6	7	8	9	10	11	12
	d t	11	18	7	14	10	12	17	13	4	8	23	11

Table 4

 4

	.2.
	Table 4.2 Computational results (I)
	Period	1	2	3	4	5	6	7	8	9	10	11	12
	x t	20	10	10	20	0	8+4 *	17	19	10	10	10	10
	I t	9	1	4	10	0	0	0	6	12	14	1	0
	Emissions	20	20	20	20	0	20	17	19	20 20	20	20
	Tech. Selection	g	r	r	g	-	r & g *	g	g	r	r	r	r
	*The production in period 6 should be executed by both technology-r and technology-g with an amount 8 and 4 thousand tons, respectively.

  .

	Table 4.3 Computational results (II)
	Month	1	2	3	4	5	6	7	8	9	10	11	12
	x t	20	10	10	20	0	12	17	19	10	10	10	10
	I t	9	1	4	10	0	0	0	6	12	14	1	0
	Emissions	20	20	20	20	0	12	17	19	20	20	20	20
	Tech. Selection	g	r	r	g	-	g	g	g	r	r	r	r

  the two-stage Stackelberg game model, the initial emission allowances for manufacturers IE i "s are calculated by Eq. (5.3.7) with any given ϕ. With given IE i "s, the equilibrium carbon * can be obtained by theCournot competition model (i.e., (5.3.2)).

	Simultaneously, the minimal cost of the manufacturer

* () x ii F and the related emissions * () i i AE x can be computed by Algorithm-4-PDP. Then, the social welfare W Р can be calculated by objective function (5.3.5) with * () x ii F and * () i i

  .

	Table 5.1 Parameter values of the government
	Parameters			α ec	ev		φ envu	φ ecou
	Value			1.8	0.5	0.3		1×e -6	1
	Table 5.2 Demands to the manufacturers (thousand tons)
	d it		1	2	3	4		5	6
	A		5	7	10	4		8	11
	B		10	12	9	11		9	13
	C		11	18	17	11		16	12
	Table 5.3 Parameter values of the manufacturers
	i	R i (×10 3 )	P i	s ir (×10 3 )	s iР (×10 3 )	p ir	p iР	e ir	e iР	С it
	A	13	110	50	150	30	55	1.6	0.8	4.0
	B	18	105	60	180	25	50	1.8	1.0	3.5
	C	25	100	80	250	20	45	2.0	1.1	3.0

Table 5 .

 5 4 Social welfare Р -Average)/Average; a and b are the worst and best objective values in the 10-time tests.

	Test No.	1	2	3	4	5	6	7	8	9	10	Average
	W Р	1.637 1.644 1.641 1.644	1.643	1.645 1.644 1.643 1.653 1.641	1.643
	Gap(%) * -0.40 a 0.04 -0.16 0.05	-0.02	0.08	0.06	-0.04 0.56 b -0.16	0
	*Gap=(W

Table 5 .

 5 5 Numbers of the technologies used by the manufacturers

Table 5

 5 .6 Numbers of the technologies used by three manufacturers ( = 2.0)

	Tech. Selection	r	g	r & g
	A	1	4	1
	B	3	3	0
	C	4	2	0

Table 5

 5 Table 5.8 Numbers of the technologies used by three manufacturers

	.8.
	Table 5.7 Optimal emission-reduction targets
	Test No.	1	2	3	4	5	6	7	8	9	10	Average
	ϕ(%)	31.39 30.23 32.00 32.00	28.87	30.73 30.51 32.00 31.13 30.61	30.95

A high-end customer market implies the customers prefer to the greener product. That is, the customer demand increases when the percentage of green technology used in production m increases.

Acknowledgements

Acknowledgement

Also I would like to show my appreciation to Prof.

and choose technology for production in each period to cope with the emission constraints and reduce production and operation costs. TСe manufacturer's decision problem for a medium-term planninР is to optimize Сis production planninР and tecСnoloРy selection under tСe Рovernment-imposed emissionreduction policy witС an objective of minimizinР Сis overall cost. Particularly, under tСe emission cap-and-trade scСeme, tСe decision on emission-allowance trade sСould also be considered.

Consistent with the above problem description, this research is divided into two parts.

The first part addresses the decision problems for a manufacturer in response to the government-imposed emission-reduction policy. More specifically, decision problems for long-and medium-term planning are investigated, respectively. The second part investigates the emission-reduction policymaking problems for a local government. The specific research questions are summarized as follows.

Part I: tСe manufacturers' decision problems under Рovernment-imposed emissionreduction policies

1. How should manufacturers design the carbon footprint of their products when facing green-aware customer demands? 2. How should manufacturers price their products? 3. How should manufacturers select retailers to sell their products in retail markets? 4. How should manufacturers optimize production planning? 5. Which technology should manufacturers choose for production in each period?

Note that questions 1-3 are involved in a long-term planning problem while questions 4-5 are involved in a medium-term planning.

. Problem Description and Notation . . Problem Description

This chapter aims to optimize a manufacturer"s medium-term decisions under two types of government-imposed emission-reduction policies: emission-cap regulation policy and emission cap-and-trade scheme. His decisions include production planning and technology selection with an objective of minimizing the overall costs over a finite production planning horizon (e.g., one year including 12 months/periods).

As introduced in the previous chapter, two types of technologies are available for the manufacturer: the regular technology (tecСnoloРy-r) and the green technology (tecСnoloРy-Р). By definition, technology-g generates fewer emissions than technology-r per unit production, but leads to higher setup cost and unit production cost. In each period, either one or both technologies can be chosen for production. Therefore, it is necessary for the manufacturer to optimize his decision on technology selection for each production period to seek a balance between emissions and cost.

It is assumed that the manufacturer serves a market with deterministic customer demand.

Therefore, demand shortage and backlogging are not considered. On-hand inventory is used to streamline production, while inventory cost function is assumed to be linear. Without loss of generality, the initial and end inventory levels are assumed to be zero in the planning horizon.

The manufacturer"s production emissions in each period are constrained by governmentimposed emission-reduction policy: either a mandatory emission cap set by the government under the emission-cap regulation policy or an emission limitation related to the environmental bearing capacity under the emission cap-and-trade scheme. Note that the environmental bearing capacity is due to some particular features of environment, such as ultimate bearing capacity and irreversible degradation (Le [START_REF] Kama | The optimal control of pollution under the risk of irreversible degradation of the environment[END_REF].

Consequently, the manufacturer faces challenges in optimizing his production planning under these emission constraints.

In order to minimize the overall costs over a planning horizon, in each period the manufacturer should determine production quantity, manage inventory level, and choose appropriate technology for production. An optimal production planning reduces the Chapter 5

Carbon Emission-Reduction Policy for Government

This chapter focuses on emission-reduction issues in a local region and investigates policymaking decision problems for a local government. It seeks to maximize the social welfare of the local region by optimizing the government"s emission-reduction policies.

Both emission-cap regulation policy and emission cap-and-trade scheme are considered in our research.

Section 5.1 describes the problem in detail and defines the notation used in this chapter. Section 5.2 studies the decision problem of optimizing the emission-cap regulation policy.

The problem is formulated as a Stackelberg game, and a hybrid algorithm is developed to solve the proposed model. Section 5.3 discusses the scenario of emission cap-and-trade scheme. Section 5.4 conducts some numerical experiments to illustrate the application of the models and the algorithms proposed in this chapter. Section 5.5 summarizes the research of this chapter.

Chapter 6

Conclusions and Future Research

. Conclusions

Carbon emission reduction now becomes a consensus among the international community. This research focused on emission-reduction issues of a local region, in which a local government regulates manufacturers whose production emits carbon dioxide. We The problem is difficult to solve since it was proven to be NP-hard, non-concave, and analytically intractable. A hybrid algorithm was developed to deal with these difficulties.

The proposed algorithm combines analytical methods, genetic algorithm and dynamic programming algorithm.

Numerical examples were conducted to illustrate the application of the model and the algorithm. The results show that the hybrid algorithm can efficiently find near-optimal solutions and converges with a high robustness. Some interesting and valuable managerial insights were obtained from the computational results and sensitivity analysis. The most important of them are shown as follows.

 An optimal retailer selection strategy may help the manufacturer not only to maximize his profit by selling his products to the "right" retailers, but also to cope with the governmental emission regulations.

 An optimal differential pricing strategy implemented through his retailers may make the manufacturer more profitable and competitive in green-awareness markets.

 The government-imposed emission cap and customers" green preference have significant influences on the carbon footprint of the manufacturer"s product.