Integer programming can be used to provide solutionsto complex decision and planning problems occurring in a wide varietyof situations. Applying integer programming to a real life problembasically involves a first phase where a mathematical model isconstructed, and a second phase where the problem described by themodel is solved. While the nature of the challenges involved in therespective two phases differ, the strong relationship between theproperties of models, and which methods that are appropriate for theirsolution, links the two phases. This thesis constitutes of threepapers, of which the third one considers the modeling phase, while thefirst and second one consider the solution phase.   Many applications of column generation yield master problems of setpartitioning type, and the first and second papers presentmethodologies for solving such problems. The characteristics of themethodologies presented are that all successively found solutions arefeasible and integral, where the retention of integrality is a majordistinction from other column generation methods presented in theliterature.   The third paper concerns nurse scheduling and describes the results ofa pilot implementation of a scheduling tool at a Swedish nursing ward.This paper focuses on the practical aspects of modeling and thechallenges of providing a solution to a complex real life problem.

In airline scheduling a variety of planning and operational decision problems have to be solved. In this thesis we consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights of a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved subsequently. Also, in minimal cost solutions, aircraft and crew are highly utilised and short turn around times are usually used for aircraft and crew. If such a solution is used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day due to the lack of buffer times. We formulate an integrated aircraft routing and crew pairing model that can generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We propose two new solution methods to solve the integrated model. The first approach is an optimisation based heuristic approach that is capable of generating good quality solutions quickly, the second approach can solve the integrated model to optimality. In an extension of the integrated model we allow the departure times of some flights in the schedule to vary in some time window. This creates additional flexibility that leads to aircraft routing and crew pairing solutions with improved cost and robustness compared to the integrated model without time windows. Using data from domestic Air New Zealand schedules, we evaluate the benefits of the approaches on real world problem instances. Our solutions satisfy all rules imposed for these problems and are ready to be implemented in practice. We generate solutions that dramatically improve the cost and robustness of solutions obtained by existing methods.

<p>In this thesis a method for solving the Generalized Assignment Problem (GAP) is described. It is based on a reformulation of the original problem into a Set Partitioning Problem (SPP), in which the columns represent partial solutions to the original problem. For solving this problem, column generation, with systematic overgeneration of columns, is used. Conditions that guarantee that an optimal solution to a restricted SPP is optimal also in the original problem are given. In order to satisfy these conditions, not only columns with the most negative Lagrangian reduced costs need to be generated, but also others; this observation leads to the use of overgeneration of columns.</p><p>The Generalized Assignment Problem has shown to be NP-hard and therefore efficient algorithms are needed, especially for large problems. The application of the proposed method decomposes GAP into several knapsack problems via Lagrangian relaxation, and enumerates solutions to each of these problems. The solutions obtained from the knapsack problems form a Set Partitioning Problem, which consists of combining one solution from each knapsack problem to obtain a solution to the original problem. The algorithm has been tested on problems with 10 agents and 60 jobs. This leads to 10 knapsack problems, each with 60 variables.</p>

In this thesis a method for solving the Generalized Assignment Problem (GAP) is described. It is based on a reformulation of the original problem into a Set Partitioning Problem (SPP), in which the columns represent partial solutions to the original problem. For solving this problem, column generation, with systematic overgeneration of columns, is used. Conditions that guarantee that an optimal solution to a restricted SPP is optimal also in the original problem are given. In order to satisfy these conditions, not only columns with the most negative Lagrangian reduced costs need to be generated, but also others; this observation leads to the use of overgeneration of columns. The Generalized Assignment Problem has shown to be NP-hard and therefore efficient algorithms are needed, especially for large problems. The application of the proposed method decomposes GAP into several knapsack problems via Lagrangian relaxation, and enumerates solutions to each of these problems. The solutions obtained from the knapsack problems form a Set Partitioning Problem, which consists of combining one solution from each knapsack problem to obtain a solution to the original problem. The algorithm has been tested on problems with 10 agents and 60 jobs. This leads to 10 knapsack problems, each with 60 variables.

Trellis-coded Modulation (TCM) is used in bandlimited communication systems. TCM efficiency improves coding gain by combining modulation and forward error correction coding in one process. In TCM, the bandwidth expansion is not required because it uses the same symbol rate and power spectrum; the differences are the introduction of a redundancy bit and the use of a constellation with double points. <p> In this thesis, a novel TCM encoder/decoder ASIC chip implementation is presented. This ASIC codec not only increases decoding speed but also reduces hardware complexity. The algorithm and technique are presented for a 16-state convolutional code which is used in standard 256-QAM wireless systems. In the decoder, a Hamming distance is used as a cost function to determine output in the maximum likelihood Viterbi decoder. Using the relationship between the delay states and the path state in the Trellis tree of the code, a pre-calculated Hamming distances are stored in a look-up table. In addition, an output look-up-table is generated to determine the decoder output. This table is established by the two relative delay states in the code. The thesis provides details of the algorithm and the structure of TCM codec chip. Besides using parallel processing, the ASIC implementation also uses pipelining to further increase decoding speed. <p> The codec was implemented in ASIC using standard 0.18Ým CMOS technology; the ASIC core occupied a silicon area of 1.1mm2. All register transfer level code of the codec was simulated and synthesized. The chip layout was generated and the final chip was fabricated by Taiwan Semiconductor Manufacturing Company through the Canadian Microelectronics Corporation. The functional testing of the fabricated codec was performed partially successful; the timing testing has not been fully accomplished because the chip was not always stable.

Trellis-coded Modulation (TCM) is used in bandlimited communication systems. TCM efficiency improves coding gain by combining modulation and forward error correction coding in one process. In TCM, the bandwidth expansion is not required because it uses the same symbol rate and power spectrum; the differences are the introduction of a redundancy bit and the use of a constellation with double points. <p> In this thesis, a novel TCM encoder/decoder ASIC chip implementation is presented. This ASIC codec not only increases decoding speed but also reduces hardware complexity. The algorithm and technique are presented for a 16-state convolutional code which is used in standard 256-QAM wireless systems. In the decoder, a Hamming distance is used as a cost function to determine output in the maximum likelihood Viterbi decoder. Using the relationship between the delay states and the path state in the Trellis tree of the code, a pre-calculated Hamming distances are stored in a look-up table. In addition, an output look-up-table is generated to determine the decoder output. This table is established by the two relative delay states in the code. The thesis provides details of the algorithm and the structure of TCM codec chip. Besides using parallel processing, the ASIC implementation also uses pipelining to further increase decoding speed. <p> The codec was implemented in ASIC using standard 0.18Ým CMOS technology; the ASIC core occupied a silicon area of 1.1mm2. All register transfer level code of the codec was simulated and synthesized. The chip layout was generated and the final chip was fabricated by Taiwan Semiconductor Manufacturing Company through the Canadian Microelectronics Corporation. The functional testing of the fabricated codec was performed partially successful; the timing testing has not been fully accomplished because the chip was not always stable.

<p>Integer programming can be used to provide solutionsto complex decision and planning problems occurring in a wide varietyof situations. Applying integer programming to a real life problembasically involves a first phase where a mathematical model isconstructed, and a second phase where the problem described by themodel is solved. While the nature of the challenges involved in therespective two phases differ, the strong relationship between theproperties of models, and which methods that are appropriate for theirsolution, links the two phases. This thesis constitutes of threepapers, of which the third one considers the modeling phase, while thefirst and second one consider the solution phase.</p><p> </p><p>Many applications of column generation yield master problems of setpartitioning type, and the first and second papers presentmethodologies for solving such problems. The characteristics of themethodologies presented are that all successively found solutions arefeasible and integral, where the retention of integrality is a majordistinction from other column generation methods presented in theliterature.</p><p> </p><p>The third paper concerns nurse scheduling and describes the results ofa pilot implementation of a scheduling tool at a Swedish nursing ward.This paper focuses on the practical aspects of modeling and thechallenges of providing a solution to a complex real life problem.</p>

In airline scheduling a variety of planning and operational decision problems have to be solved. In this thesis we consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights of a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved subsequently. Also, in minimal cost solutions, aircraft and crew are highly utilised and short turn around times are usually used for aircraft and crew. If such a solution is used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day due to the lack of buffer times. We formulate an integrated aircraft routing and crew pairing model that can generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We propose two new solution methods to solve the integrated model. The first approach is an optimisation based heuristic approach that is capable of generating good quality solutions quickly, the second approach can solve the integrated model to optimality. In an extension of the integrated model we allow the departure times of some flights in the schedule to vary in some time window. This creates additional flexibility that leads to aircraft routing and crew pairing solutions with improved cost and robustness compared to the integrated model without time windows. Using data from domestic Air New Zealand schedules, we evaluate the benefits of the approaches on real world problem instances. Our solutions satisfy all rules imposed for these problems and are ready to be implemented in practice. We generate solutions that dramatically improve the cost and robustness of solutions obtained by existing methods.

In airline scheduling a variety of planning and operational decision problems have to be solved. In this thesis we consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights of a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved subsequently. Also, in minimal cost solutions, aircraft and crew are highly utilised and short turn around times are usually used for aircraft and crew. If such a solution is used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day due to the lack of buffer times. We formulate an integrated aircraft routing and crew pairing model that can generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We propose two new solution methods to solve the integrated model. The first approach is an optimisation based heuristic approach that is capable of generating good quality solutions quickly, the second approach can solve the integrated model to optimality. In an extension of the integrated model we allow the departure times of some flights in the schedule to vary in some time window. This creates additional flexibility that leads to aircraft routing and crew pairing solutions with improved cost and robustness compared to the integrated model without time windows. Using data from domestic Air New Zealand schedules, we evaluate the benefits of the approaches on real world problem instances. Our solutions satisfy all rules imposed for these problems and are ready to be implemented in practice. We generate solutions that dramatically improve the cost and robustness of solutions obtained by existing methods.

In airline scheduling a variety of planning and operational decision problems have to be solved. In this thesis we consider the problems aircraft routing and crew pairing: aircraft and crew must be allocated to flights of a schedule in a minimal cost way. Although these problems are not independent, they are usually formulated as independent mathematical optimisation models and solved sequentially. This approach might lead to a suboptimal allocation of aircraft and crew, since a solution of one of the problems may restrict the set of feasible solutions of the problem solved subsequently. Also, in minimal cost solutions, aircraft and crew are highly utilised and short turn around times are usually used for aircraft and crew. If such a solution is used in operations, a short delay of one flight can cause very severe disruptions of the schedule later in the day due to the lack of buffer times. We formulate an integrated aircraft routing and crew pairing model that can generate solutions that incur small costs and are also robust to typical stochastic variability in airline operations. We propose two new solution methods to solve the integrated model. The first approach is an optimisation based heuristic approach that is capable of generating good quality solutions quickly, the second approach can solve the integrated model to optimality. In an extension of the integrated model we allow the departure times of some flights in the schedule to vary in some time window. This creates additional flexibility that leads to aircraft routing and crew pairing solutions with improved cost and robustness compared to the integrated model without time windows. Using data from domestic Air New Zealand schedules, we evaluate the benefits of the approaches on real world problem instances. Our solutions satisfy all rules imposed for these problems and are ready to be implemented in practice. We generate solutions that dramatically improve the cost and robustness of solutions obtained by existing methods.