Submitted by Renata Lopes (renatasil82@gmail.com) on 2018-05-23T12:30:22Z No. of bitstreams: 0 / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2018-05-23T12:52:41Z (GMT) No. of bitstreams: 0 / Made available in DSpace on 2018-05-23T12:52:41Z (GMT). No. of bitstreams: 0 Previous issue date: 2018-05-14 / A partir de uma abordagem interacional, Gille (2001) define a argumentação como um processo constituído por movimentos argumentativos (MA), realizados de forma explícita ou implícita na interação. Nessa perspectiva, a argumentação compreende ações sequenciais coconstruídas na interação, por meio das quais opiniões expressas ou inferidas são negociadas. Dentre os movimentos argumentativos utilizados na sustentação de pontos de vista, Barletta (2014) identifica os MA de evidência legal, os quais correspondem a argumentos que sustentam o ponto de vista de um participante por meio de evidências cujo respaldo se encontra na lei. O estudo da autora incita um olhar mais específico para as contribuições dos MA de evidência legal para o cumprimento do objetivo principal das audiências de conciliação que ocorrem na arena do PROCON – a resolução do conflito. Com a proposta de investigar esse aspecto, agregando achados aos estudos da argumentação no referido contexto institucional, este trabalho teve o objetivo de investigar reformulações de movimentos argumentativos (MA) de evidência legal em duas audiências de conciliação no PROCON de uma cidade da zona da mata mineira. Para tanto, foi desenvolvida uma pesquisa de base qualitativa e interpretativa (DENZIN e LINCOLN, 2006; SCHWANDT, 2006), que contou com o aparato da Análise da Conversa, valendo-se sobretudo de referenciais que tratam da base teórica (SACKS, 1973; SACKS, SCHEGLOFF E JEFFERSON, 1974; SCHEGLOFF, JEFFERSON E SACKS, 1977; POMERANTZ, 1984; entre outros) e metodológica (POMERANTZ E FEHR, 1997) desta vertente de estudos linguísticos, bem como de referenciais que dela partiram para um estudo da prática de reformulação (GARFINKEL E SACKS, 1970; HERITAGE E WATSON, 1979; entre outros). O material linguístico analisado foi gravado em áudio e transcrito de acordo com as convenções propostas pelos analistas da conversa (SACHS, SCHEGLOFF e JEFFERSON, 1974). As análises desenvolvidas nos possibilitaram observar a ocorrência de reformulações tanto dos MA de evidência legal realizados pela mediadora como dos MA de evidência legal realizados pelos reclamados. As reformulações eram dos seguintes tipos: reformulação de checagem (ou reformulação como ação de checagem de entendimento), reformulação do tipo resumo, reformulação desafiadora (ou reformulação como ação de desafio), reformulação feita por meio de explicação, reformulação feita por meio de sugestão, reformulação do cerne, reformulação ratificadora da acusação, reformulação ratificadora do ponto de vista, reformulação ratificadora da legislação, e reformulação do tipo correção exposta; e realizaram diversas ações, no curso das interações, que abriram espaço para o desfecho da audiência. Por fim (e em suma), não obstante se a decisão da reformulação tenha sido sua confirmação ou sua desconfirmação, seu uso culminou em importantes benefícios interacionais. Os resultados alcançados nos permitem advogar que reformulações do movimento argumentativo de evidência legal, no contexto de audiências de conciliação, podem contribuir para o alcance do acordo entre as partes envolvidas, na medida em que operam, turno a turno, na negociação do conflito, desencadeado pela apresentação e sustentação de argumentos divergentes, que expõem diferentes pontos de vista na interação em curso. Conclui-se, então, que, nesta pesquisa, o gerenciamento dos conflitos, gerados por argumentações divergentes, foi possibilitado pelas diversas reformulações realizadas ao longo das audiências de conciliação (aqui analisadas) do PROCON da zona da mata mineira, e culminou no acordo entre as partes. / By adopting an interactive approach, Gille (2001) defines argumentation as a process constituted by argumentative movements (AM) explicitly or implicitly carried out in interaction processes. Thus, argumentation comprises sequential actions co-constructed through interaction, which allow negotiating expressed or inferred opinions. According to Barletta (2014), legal AMs stand out among argumentative movements used to support viewpoints because they correspond to arguments that corroborate participants’ viewpoint by means of evidences supported by laws. The aforementioned author invites us to take a more specific look at the contributions from legal AMs to fulfill the main goal of conciliation hearings taking place at PROCON, i.e., conflict resolution. The aim of the current study is to analyze reformulations applied to legal argumentative movements (AM) in two PROCON conciliation hearings held in a city located in Zona da Mata Region (Minas Gerais State) in order to investigate such contributions and to add findings to studies about argumentation in the aforementioned institutional context. A qualitative and interpretive research (DENZIN and LINCOLN, 2006; SCHWANDT, 2006), which was based on Conversation Analysis, was herein developed. It was mainly supported by references concerning the theoretical (SACKS, 1973; SACKS, SCHEGLOFF and JEFFERSON, 1974; SCHEGLOFF, JEFFERSON and SACKS, 1977; POMERANTZ, 1984; among others) and methodological (POMERANTZ and FEHR, 1997) bases of this linguistic study approach, as well as by references that used such approach to study (re)formulation practices (GARFINKEL and SACKS, 1970; HERITAGE and WATSON, 1979; among others). The herein analyzed linguistic material was audio recorded and transcribed according to conventions proposed by conversation analysts (SACHS, SCHEGLOFF and JEFFERSON, 1974). The analyses conducted in the present study showed legal AM reformulations carried out by both the mediator and the defendants. Both parts presented the following reformulation types: confirmatory reformulation (or reformulation used as the action of confirming the understanding about something), summary-type reformulation, challenging reformulation (or reformulation used as challenging action), reformulation done by means of explanation, reformulation done by means of suggestion, root cause reformulation, reformulation ratifying the accusation, reformulation ratifying the viewpoint, reformulation ratifying the legislation, and correction-type reformulation. These reformulations enabled several actions in the course of the interactions and allowed the hearing to reach an outcome. Finally, the use of reformulations has generated important interactional benefits, regardless of whether the decision to reformulate was based on confirmation or disconfirmation purposes. Results in the current study allow stating that reformulations applied to legal argumentative movements during conciliation hearings may help the involved parts to reach an agreement. It happens because reformulations carried out in each participant’s turn operate towards the negotiation of conflicts triggered by the presentation of and support to divergent arguments, which expose different viewpoints in the interaction in progress. The current study concluded that the management of conflicts generated by divergent arguments was enabled by several reformulations carried out during the herein analyzed conciliation hearings held at PROCON, as well as that such management helped the involved parts to reach an agreement.

<p>Accommodating changing consumer tastes, nutritional targets, competitive pressures and government regulations is an ongoing task in the food industry. Product development projects tend to have competing goals and more potential solutions than can be examined efficiently. However, existing databases or spreadsheets containing formulas, ingredient properties, and product characteristics can be exploited using latent variable methods to confront difficult formulation issues. Using these methods, a product developer can target specific final product properties and systematically determine new recipes that will best meet the development objectives.</p> <p>Latent variable methods in reformulation are demonstrated for a product line of frozen muffin batters used in the food service industry. A particular attribute is to be minimized while maintaining the taste, texture, and appearance of the original products, but the minimization is difficult because the attribute in question is not well understood. Initially, existing data is used to develop a partial least squares (PLS) model, which identifies areas for further testing. Design of experiments (DOE) in the latent variable space generates new data that is used to augment the model. An optimization algorithm makes use of the updated model to produce recipes for four different products, and a significant reduction of the target attribute is achieved in all cases.</p> <p>Latent variable methods are also applied to a difficult classification problem in oat milling. Process monitoring involves manually classifying and counting the oats and hulls in the product streams of groats; a task that is time-consuming and therefore infrequent. A solution based on near infrared (NIR) imaging and PLS-discriminant analysis (PLS-DA) is investigated and found to be feasible. The PLS-DA model, built using mixed-cultivar samples, effectively separates the oats and groats into two classes. The model is validated using samples of three pure cultivars with varying moistures and growing conditions.</p> / Master of Applied Science (MASc)

Stochastic programming is an optimization technique that incorporates random variables as parameters. Because it better reflects the uncertain real world than its traditional deterministic counterpart, stochastic programming has drawn increasingly more attention among decision-makers, and its applications span many fields including financial engineering, health care, communication systems, and supply chain management. On the flip side, stochastic programs are usually very difficult to solve, which is further compounded by the fact that in many of the aforementioned applications, we also have discrete decisions, thereby rendering these problems even more challenging. In this dissertation, we study the class of two-stage stochastic mixed-integer programs (SMIP), which, as its name suggests, lies at the confluence of two formidable classes of problems. We design a novel algorithm for this class of problems, and also explore specialized approaches for two related real-world applications. Although a number of algorithms have been developed to solve two-stage SMIPs, most of them deal with problems containing purely integer or continuous variables in either or both of the two stages, and frequently require the technology and/or recourse matrices to be deterministic. As a ground-breaking effort, in this work, we address the challenging class of two-stage SMIPs that involve 0-1 mixed-integer variables in both stages. The only earlier work on solving such problems (Car&#248;e and Schultz (1999)) requires the optimization of several non-smooth Lagrangian dual problems using subgradient methods in the bounding process, which turns out to be computationally very expensive. We begin with proposing a decomposition-based branch-and-bound (DBAB) algorithm for solving two-stage stochastic programs having 0-1 mixed-integer variables in both stages. Since the second-stage problems contain binary variables, their value functions are in general nonconvex and discontinuous; hence, the classical Benders' decomposition approach (or the L-shaped method) for solving two-stage stochastic programs, which requires convex subproblem value functions, cannot be directly applied. This motivates us to relax the second-stage problems and accompany this relaxation with a convexification process. To make this process computationally efficient, we propose to construct a certain partial convex hull representation of the two-stage solution space, using the relaxed second-stage constraints and the restrictions confining the first-stage variables to lie within some hyperrectangle. This partial convex hull is sequentially generated using a convexification scheme, such as the Reformulation-Linearization Technique (RLT), which yields valid inequalities that are functions of the first-stage variables and, of noteworthy importance, are reusable in the subsequent subproblems by updating the values of the first-stage variables. Meanwhile, since the first stage contains continuous variables, whenever we tentatively fix these variables at some given feasible values, the resulting constraints may not be facial with respect to the associated bounding constraints that are used to construct the partial convex hull. As a result, the constructed Benders' subproblems define lower bounds for the second-stage value functions, and likewise, the resulting Benders' master problem provides a lower bound for the original stochastic program defined over the same hyperrectangle. Another difficulty resulting from continuous first-stage variables is that when the given first-stage solution is not extremal with respect to its bounds, the second-stage solution obtained for a Benders' subproblem defined with respect to a partial convex hull representation in the two-stage space may not satisfy the model's binary restrictions. We thus need to be able to detect whether or not a Benders' subproblem is solved by a given fractional second-stage solution. We design a novel procedure to check this situation in the overall algorithmic scheme. A key property established, which ensures global convergence, is that these lower bounds become exact if the given first-stage solution is a vertex of the defining hyperrectangle, or if the second-stage solution satisfies the binary restrictions. Based on these algorithmic constructs, we design a branch-and-bound procedure where the branching process performs a hyperrectangular partitioning of the projected space of the first-stage variables, and lower bounds for the nodal problems are computed by applying the proposed modified Benders' decomposition method. We prove that, when using the least-lower-bound node-selection rule, this algorithm converges to a global optimal solution. We also show that the derived RLT cuts are not only reusable in subsequent Benders iterations at the same node, but are also inheritable by the subproblems of the children nodes. Likewise, the Benders' cuts derived for a given sub-hyperrectangle can also be inherited by the lower bounding master programs solved for its children nodes. Using these cut inheritance properties results in significant savings in the overall computational effort. Some numerical examples and computational results are presented to demonstrate the efficacy of this approach. The sizes of the deterministic equivalent of our test problems range from having 386 continuous variables, 386 binary variables, and 386 constraints, up to 1795 continuous variables, 1539 binary variables, and 1028 constraints. The results reveal an average savings in computational effort by a factor of 9.5 in comparison with using a commercial mixed-integer programming package (CPLEX 8.1) on a deterministic equivalent formulation. We then explore an important application of SMIP to enhance the traditional airline fleet assignment models (FAM). Given a flight schedule network, the fleet assignment problem solved by airline companies is concerned with assigning aircraft to flight legs in order to maximize profit with respect to captured path- or itinerary-based demand. Because certain related crew scheduling regulations require early information regarding the type of aircraft serving each flight leg, the current practice adopted by airlines is to solve the fleet assignment problem using estimated demand data 10-12 weeks in advance of departure. Given the level of uncertainty, deterministic models at this early stage are inadequate to obtain a good match of aircraft capacity with passenger demands, and revisions to the initial fleet assignment become naturally pertinent when the observed demand differs considerably from the assigned aircraft capacities. From this viewpoint, the initial decision should embrace various market scenarios so that it incorporates a sufficient look-ahead feature and provides sufficient flexibility for the subsequent re-fleeting processes to accommodate the inevitable demand fluctuations. With this motivation, we propose a two-stage stochastic programming approach in which the first stage is concerned with the initial fleet assignment decisions and, unlike the traditional deterministic methodology, focuses on making only a family-level assignment to each flight leg. The second stage subsequently performs the detailed assignments of fleet types within the allotted family to each leg under each of the multiple potential scenarios that address corresponding path- or itinerary-based demands. In this fashion, the initial decision of what aircraft family should serve each flight leg accomplishes the purpose of facilitating the necessary crew scheduling decisions, while judiciously examining the outcome of future re-fleeting actions based on different possible demand scenarios. Hence, when the actual re-fleeting process is enacted several weeks later, this anticipatory initial family-level assignment will hopefully provide an improved overall fleet type re-allocation that better matches demand. This two-stage stochastic model is complemented with a secondary model that performs adjustments within each family, if necessary, to provide a consistent fleet type-assignment information for accompanying decision processes, such as yield management. We also propose several enhanced fleet assignment models, including a robust optimization model that controls decision variation among scenarios and a stochastic programming model that considers the recapture effect of spilled demand. In addition to the above modeling concepts and framework, we also contribute in developing effective solution approaches for the proposed model, which is a large-scale two-stage stochastic 0-1 mixed-integer program. Because the most pertinent information needed from the initial fleet assignment is at the family level, and the type-level assignment is subject to change at the re-fleeting stage according to future demand realizations, our solution approach focuses on assigning aircraft families to the different legs in the flight network at the first stage, while finding relaxed second-stage solutions under different demand scenarios. Based on a polyhedral study of a subsystem extracted from the original model, we derive certain higher-dimensional convex hull as well as partial convex hull representations for this subsystem. Accordingly, we propose two variants for the primary model, both of which relax the binary restrictions on the second-stage variables, but where the second variant then also accommodates the partial convex hull representations, yielding a tighter, albeit larger, relaxation. For each variant, we design a suitable solution approach predicated on Benders' decomposition methodology. Using certain realistic large-scale flight network test problems having 900 flight legs and 1,814 paths, as obtained from United Airlines, the proposed stochastic modeling approach was demonstrated to increase daily expected profits by about 3% (which translates to about $160 million per year) in comparison with the traditional deterministic model in present usage, which considers only the expected demand. Only 1.6% of the second-stage binary variables turn out to be fractional in the first variant, and this number is further reduced to 1.2% by using the tighter variant. Furthermore, when attempting to solve the deterministic equivalent formulation for these two variants using a commercial mixed-integer programming package (CPLEX 8.1), both the corresponding runs were terminated after reaching a 25-hour cpu time limit. At termination, the software was still processing the initial LP relaxation at the root node for each of these runs, and no feasible basis was found. Using the proposed algorithms, on the other hand, the solution times were significantly reduced to 5 and 19 hours for the two variants, respectively. Considering that the fleet assignment models are solved around three months in advance of departure, this solution time is well acceptable at this early planning stage, and the improved quality in the solution produced by considering the stochasticity in the system is indeed highly desirable. Finally, we address another practical workforce planning problem encountered by a global financial firm that seeks to manage multi-category workforce for functional areas located at different service centers, each having office-space and recruitment-capacity constraints. The workforce demand fluctuates over time due to market uncertainty and dynamic project requirements. To hedge against the demand fluctuations and the inherent uncertainty, we propose a two-stage stochastic programming model where the first stage makes personnel recruiting and allocation decisions, while the second stage, based on the given personnel decision and realized workforce demand, decides on the project implementation assignment. The second stage of the proposed model contains binary variables that are used to compute and also limit the number of changes to the original plan. Since these variables are concerned with only one quality aspect of the resulting workforce plan and do not affect feasibility issues, we replace these binary variables with certain conservative policies regarding workforce assignment change restrictions in order to obtain more manageable subproblems that contain purely continuous variables. Numerical experiments reveal that the stochastic programming approach results in significantly fewer alterations to the original workforce plan. When using a commercial linear programming package CPLEX 9.0 to solve the deterministic equivalent form directly, except for a few small-sized problems, this software failed to produce solutions due to memory limitations, while the proposed Benders' decomposition-based solution approach consistently solved all the practical-sized test problems with reasonable effort. To summarize, this dissertation provides a significant advancement in the algorithmic development for solving two-stage stochastic mixed-integer programs having 0-1 mixed-integer variables in both stages, as well as in its application to two important contemporary real-world applications. The framework for the proposed solution approaches is to formulate tighter relaxations via partial convex hull representations and to exploit the resulting structure using suitable decomposition methods. As decision robustness is becoming increasingly relevant from an economic viewpoint, and as computer technological advances provide decision-makers the ability to explore a wide variety of scenarios, we hope that the proposed algorithms will have a notable positive impact on solving stochastic mixed-integer programs. In particular, the proposed stochastic programming airline fleet assignment and the workforce planning approaches studied herein are well-poised to enhance the profitability and robustness of decisions made in the related industries, and we hope that similar improvements are adapted by more industries where decisions need to be made in the light of data that is shrouded by uncertainty. / Ph. D.

Air transportation offers both passenger and freight services that are essential for economic growth and development. In a highly competitive environment, airline companies have to control their operating costs by managing their flights, aircraft, and crews effectively. This motivates the extensive use of analytical techniques to solve complex problems related to airline operations planning, which includes schedule design, fleet assignment, aircraft routing, and crew scheduling. The initial problem addressed by airlines is that of schedule design, whereby a set of flights having specific origin and destination cities as well as departure and arrival times is determined. Then, a fleet assignment problem is solved to assign an aircraft type to each flight so as to maximize anticipated profits. This enables a decomposition of subsequent problems according to the different aircraft types belonging to a common family, for each of which an aircraft routing problem and a crew scheduling or pairing problem are solved. Here, in the aircraft routing problem, a flight sequence or route is built for each individual aircraft so as to cover each flight exactly once at a minimum cost while satisfying maintenance requirements. Finally, in the crew scheduling or pairing optimization problem, a minimum cost set of crew rotations or pairings is constructed such that every flight is assigned a qualified crew and that work rules and collective agreements are satisfied. In practice, most airline companies solve these problems in a sequential manner to plan their operations, although recently, an increasing effort is being made to develop novel approaches for integrating some of the airline operations planning problems while retaining tractability. This dissertation formulates and analyzes three different models, each of which examines a composition of certain pertinent airline operational planning problems. A comprehensive fourth model is also proposed, but is relegated for future research. In the first model, we integrate fleet assignment and schedule design by simultaneously considering optional flight legs to select along with the assignment of aircraft types to all scheduled legs. In addition, we consider itinerary-based demands pertaining to multiple fare-classes. A polyhedral analysis of the proposed mixed-integer programming model is used to derive several classes of valid inequalities for tightening its representation. Solution approaches are developed by applying Benders decomposition method to the resulting lifted model, and computational experiments are conducted using real data obtained from a major U.S. airline (United Airlines) to demonstrate the efficacy of the proposed procedures as well as the benefits of integration. A comparison of the experimental results obtained for the basic integrated model and for its different enhanced representations reveals that the best modeling strategy among those tested is the one that utilizes a variety of five types of valid inequalities for moderately sized problems, and further implements a Benders decomposition approach for relatively larger problems. In addition, when a heuristic sequential fixing step is incorporated within the algorithm for even larger sized problems, the computational results demonstrate a less than 2% deterioration in solution quality, while reducing the effort by about 21%. We also performed an experiment to assess the impact of integration by comparing the proposed integrated model with a sequential implementation in which the schedule design is implemented separately before the fleet assignment stage based on two alternative profit maximizing submodels. The results obtained demonstrate a clear advantage of utilizing the integrated model, yielding an 11.4% and 5.5% increase in profits in comparison with using the latter two sequential models, which translates to an increase in annual profits by about $28.3 million and $13.7 million, respectively. The second proposed model augments the first model with additional features such as flexible flight times (i.e., departure time-windows), schedule balance, and demand recapture considerations. Optional flight legs are incorporated to facilitate the construction of a profitable schedule by optimally selecting among such alternatives in concert with assigning the available aircraft fleet to all the scheduled legs. Moreover, network effects and realistic demand patterns are effectively represented by examining itinerary-based demands as well as multiple fare-classes. Allowing flexibility on the departure times of scheduled flight legs within the framework of an integrated model increases connection opportunities for passengers, hence yielding robust schedules while saving fleet assignment costs. A provision is also made for airlines to capture an adequate market share by balancing flight schedules throughout the day. Furthermore, demand recapture considerations are modeled to more realistically represent revenue realizations. For this proposed mixed-integer programming model, which integrates the schedule design and fleet assignment processes while considering flexible flight times, schedule balance, and recapture issues, along with optional legs, itinerary-based demands, and multiple fare-classes, we perform a polyhedral analysis and utilize the Reformulation-Linearization Technique in concert with suitable separation routines to generate valid inequalities for tightening the model representation. Effective solution approaches are designed by applying Benders decomposition method to the resulting tightened model, and computational results are presented to demonstrate the efficacy of the proposed procedures. Using real data obtained from United Airlines, when flight times were permitted to shift by up to 10 minutes, the estimated increase in profits was about $14.9M/year over the baseline case where only original flight legs were used. Also, the computational results indicated a 1.52% and 0.49% increase in profits, respectively, over the baseline case, while considering two levels of schedule balance restrictions, which can evidently also enhance market shares. In addition, we measured the effect of recaptured demand with respect to the parameter that penalizes switches in itineraries. Using values of the parameter that reflect 1, 50, 100, or 200 dollars per switched passenger, this yielded increases in recaptured demand that induced additional profits of 2.10%, 2.09%, 2.02%, and 1.92%, respectively, over the baseline case. Overall, the results obtained from the two schedule balance variants of the proposed integrated model that accommodate all the features of flight retiming, schedule balance, and demand recapture simultaneously, demonstrated a clear advantage by way of $35.1 and $31.8 million increases in annual profits, respectively, over the baseline case in which none of these additional features is considered. In the third model, we integrate the schedule design, fleet assignment, and aircraft maintenance routing decisions, while considering optional legs, itinerary-based demands, flexible flight retimings, recapture, and multiple fare-classes. Instead of utilizing the traditional time-space network (TSN), we formulate this model based on a flight network (FN) that provides greater flexibility in accommodating integrated operational considerations. In order to consider through-flights (i.e., a sequence of flight legs served by the same aircraft), we append a set of constraints that matches aircraft assignments on certain inbound legs into a station with that on appropriate outbound legs at the same station. Through-flights can generate greater revenue because passengers are willing to pay a premium for not having to change aircraft on connecting flights, thereby reducing the possibility of delays and missed baggage. In order to tighten the model representation and reduce its complexity, we apply the Reformulation-Linearization Technique (RLT) and also generate other classes of valid inequalities. In addition, since the model possesses many equivalent feasible solutions that can be obtained by simply reindexing the aircraft of the same type that depart from the same station, we introduce a set of suitable hierarchical symmetry-breaking constraints to enhance the model solvability by distinguishing among aircraft of the same type. For the resulting large-scale augmented model formulation, we design a Benders decomposition-based solution methodology and present extensive computational results to demonstrate the efficacy of the proposed approach. We explored four different algorithmic variants, among which the best performing procedure (Algorithm A1) adopted two sequential levels of Benders partitioning method. We then applied Algorithm A1 to perform several experiments to study the effects of different modeling features and algorithmic strategies. A summary of the results obtained is as follows. First, the case that accommodated both mandatory and optional through-flight leg pairs in the model based on their relative effects on demands and enhanced revenues achieved the most profitable strategy, with an estimated increase in expected annual profits of $2.4 million over the baseline case. Second, utilizing symmetry-breaking constraints in concert with compatible objective perturbation terms greatly enhanced problem solvability and thus promoted the detection of improved solutions, resulting in a $5.8 million increase in estimated annual profits over the baseline case. Third, in the experiment that considers recapture of spilled demand from primary itineraries to other compatible itineraries, the different penalty parameter values (100, 50, and 1 dollars per re-routed passenger) induced average respective proportions of 3.2%, 3.4%, and 3.7% in recaptured demand, resulting in additional estimated annual profits of $3.7 million, $3.8 million, and $4.0 million over the baseline case. Finally, incorporating the proposed valid inequalities within the model to tighten its representation helped reduce the computational effort by 11% on average, while achieving better solutions that yielded on average an increase in estimated annual profits of $1.4 million. In closing, we propose a fourth more comprehensive model in which the crew scheduling problem is additionally integrated with fleet assignment and aircraft routing. This integration is important for airlines because crew costs are the second largest component of airline operating expenses (after fuel costs), and the assignment and routing of aircraft plus the assignment of crews are two closely interacting components of the planning process. Since crews are qualified to typically serve a single aircraft family that is comprised of aircraft types having a common cockpit configuration and crew rating, the aircraft fleeting and routing decisions significantly impact the ensuing assignment of cockpit crews to flights. Therefore it is worthwhile to investigate new models and solution approaches for the integrated fleeting, aircraft routing, and crew scheduling problem, where all of these important inter-dependent processes are handled simultaneously, and where the model can directly accommodate various work rules such as imposing a specified minimum and maximum number of flying hours for crews on any given pairing, and a minimum number of departures at a given crew base for each fleet group. However, given that the crew scheduling problem itself is highly complex because of the restrictive work rules that must be heeded while constructing viable duties and pairings, the formulated integrated model would require further manipulation and enhancements along with the design of sophisticated algorithms to render it solvable. We therefore recommend this study for future research, and we hope that the modeling, analysis, and algorithmic development and implementation work performed in this dissertation will lend methodological insights into achieving further advances along these lines. / Ph. D.

Les problèmes de conception de réseaux ont reçu un intérêt particulier et ont été largement étudiés de par leurs nombreuses applications dans différents domaines, tels que les transports et les télécommunications. Nous nous intéressons dans ce mémoire au problème de conception de réseaux avec coûts d’ajout de capacité. Il s’agit d’installer un ensemble d’équipements sur un réseau en vue de satisfaire la demande, tout en respectant les contraintes de capacité, chaque arc pouvant admettre plusieurs équipements. L’objectif est de minimiser les coûts variables de transport des produits et les coûts fixes d’installation ou d’augmentation de capacité des équipements. La méthode que nous envisageons pour résoudre ce problème est basée sur les techniques utilisées en programmation linéaire en nombres entiers, notamment celles de génération de colonnes et de coupes. Ces méthodes sont introduites dans un algorithme général de branch-and-bound basé sur la relaxation linéaire. Nous avons testé notre méthode sur quatre groupes d’instances de tailles différentes, et nous l’avons comparée à CPLEX, qui constitue un des meilleurs solveurs permettant de résoudre des problèmes d’optimisation, ainsi qu’à une méthode existante dans la littérature combinant des méthodes exactes et heuristiques. Notre méthode a été plus performante que ces deux méthodes, notamment pour les instances de très grandes tailles. / Network design problems received a particular interest and have been widely studied because of their many applications in different areas, such as logistics and telecommunications. We focus in this work on the multicommodity capacitated network design problem with capacity expansion costs. It consists in opening a set of facilities on a network in order to meet the demand of some commodities, while respecting the capacity constraints. Each arc can admit several facilities. The objective is to minimize the commodities transportation costs, and the fixed costs of opening or increasing the capacity of the facilities. The method we are using to solve this problem is based on techniques used in integer programming, including column generation and cutting-plane methods. These methods are introduced into a general branch-and-bound algorithm, based on linear relaxation. We test our method on four groups of instances of different sizes, and we compare it with CPLEX, which is one of the best solvers available for optimization problems. We compare it also with an existing method in the literature, combining exact and heuristic methods. Numerical results show that our method was able to outperform both methods, especially when tested on large scale instances.

Qu’est-ce que la spontanéité en langue ? Comment investit-elle les différents types de discours oraux ? Avec quelles limites ? Nous cherchons à mettre au jour les aspects formels (marqueurs) de la spontanéité à partir de corpus de différents types. Nous partons de l’hypothèse selon laquelle un locuteur a tendance à produire des énoncés syntaxiquement plus complexes s’il parle spontanément que s’il surveille son énonciation, et que cette complexité linguistique se manifeste par une réduction syntaxique. La réduction des énoncés ou des formes qui le constituent, alliée à d’autres critères tels que leur caractère prédicatif, et le rôle de l’intonation pour leur complétude, s’observe effectivement dans des énoncés où l’élan de la spontanéité est patent. Cet élan est scalaire, il varie même au sein d’un tour de parole, comme le montrent les auto-ajustements. Sa variation chez un même locuteur se manifeste par des variations linguistiques intrapersonnelles.Ces variations corrélées (élan/langue) sont observables grâce au corpus spécifique que nous avons constitué : au cours d’interactions informelles, un procédé de sollicitation freine l’élan du locuteur, et celui-ci est amené à reformuler son énoncé avec plus d’attention à la forme. Les équivalences sémantiques produites dans ce contexte sont confrontées et mettent au jour l’effet de la scalarité de la spontanéité sur la grammaire des énoncés. Il se confirme que la réduction est bien un marqueur de spontanéité. Mais surtout, cette réduction investit tous les niveaux de la langue. Cette concomitance d’éléments réduits est non seulement compatible avec l’élan de la spontanéité mais elle le nourrit. / What is spontaneity in language? What role does it play in different types of oral discourse, and which constraints is it subject to? This study sets out to identify formal markers of spontaneity in different corpora. We hypothesize that a speaker tends to produce more complex syntactic statements when speaking spontaneously than when monitoring his /her spoken discourse, and that this linguistic complexity is manifested in syntactic reduction. The reduction of the statements or their component forms, combined with other criteria such as their predictive nature, and the role of intonation in their completeness, is indeed observed in statements where the impulse of spontaneity is very evident. This impulse varies, even within a single speaking turn, as can be seen in self-adjustments. Impulse variation in a single speaker is manifested by intrapersonal linguistic variations.These correlated variations (impulse and language) can be observed thanks to the specific corpus compiled for this study, which permits the comparison of semantic equivalences, revealing the effect of the degree of spontaneity on the grammar of statements. The study confirms that reduction is indeed a marker of spontaneity. But reduction affects all levels of language. This concomitance of reduced elements is both compatible with and also fosters the impulse of spontaneity.

Cette étude quasi-expérimentale a pour but de 1) comparer la prise en compte et les effets de trois conditions rétroactives, à savoir la reformulation, l’incitation et un mélange des deux techniques, 2) déterminer le lien entre la prise en compte et l’apprentissage, et 3) identifier l’effet des perceptions des apprenants quant à la rétroaction corrective sur la prise en compte et l’apprentissage. Quatre groupes d’apprenants d’anglais langue seconde ainsi que leurs enseignants provenant d’un CEGEP francophone de l’île de Montréal ont participé à cette étude. Chaque enseignant a été assigné à une condition rétroactive expérimentale qui correspondait le plus à ses pratiques rétroactives habituelles. La chercheure a assuré l’intervention auprès du groupe contrôle. L’utilisation du passé et de la phrase interrogative était ciblée durant l’intervention expérimentale. Des protocoles de pensée à haute voie ainsi qu’un questionnaire ont été utilisés pour mesurer la prise en compte de la rétroaction corrective. Des tâches de description d’images et d’identification des différences entre les images ont été administrées avant l’intervention (pré-test), immédiatement après l’intervention (post-test immédiat) et 8 semaines plus tard (post-test différé) afin d’évaluer les effets des différentes conditions rétroactives sur l’apprentissage des formes cibles. Un questionnaire a été administré pour identifier les perceptions des apprenants quant à la rétroaction corrective. En termes de prise en compte, les résultats indiquent que les participants sont en mesure de remarquer la rétroaction dépendamment de la forme cible (les erreurs dans l’utilisation du passé sont détectées plus que les erreurs d’utilisation de la phrase interrogative) et de la technique rétroactive utilisée (l’incitation et le mélange d’incitation et de reformulations sont plus détectés plus que la reformulation). En ce qui a trait à l’apprentissage, l’utilisation du passé en général est marquée par plus de développement que celle de la phrase interrogative, mais il n'y avait aucune différence entre les groupes. Le lien direct entre la prise en compte et l’apprentissage ne pouvait pas être explicitement établi. Pendant que la statistique inférentielle a suggéré une relation minimale entre la prise en compte du passé et son apprentissage, mais aucune relation entre la prise en compte de la phrase interrogative et son apprentissage, les analyses qualitatives ont montrés à une association entre la prise en compte et l’apprentissage (sur les deux cibles) pour certains étudiants et augmentations sans prise en compte pour d'autres. Finalement, l’analyse factorielle du questionnaire indique la présence de quatre facteurs principaux, à savoir l’importance de la rétroaction corrective, la reformulation, l’incitation et les effets affectifs de la rétroaction. Deux de ces facteurs ont un effet modérateur sur la prise en compte de la rétroaction sans, toutefois, avoir d’impact sur l’apprentissage. / This quasi-experimental study sought to investigate the often assumed yet little investigated relationship between noticing of corrective feedback (CF) and L2 development in relation to learner beliefs about error correction. Specifically, it aimed to (1) uncover the noticeability and effectiveness of three CF techniques (namely, recasts, prompts, a combination of the two) (2) to determine a relationship between noticing of CF and learning of the past tense and questions in the past, and (3) to determine whether learner beliefs about CF mediate what is noticed and learned in the language classroom. The participants were four groups of high-beginner college level francophone ESL learners (n = 99) and their teachers. Each teacher was assigned to a treatment condition that fit his CF style, but the researcher taught the controls. CF was provided to learners in response to their production problems with the simple past and questions in the past. While noticing of CF was assessed through immediate recall and questionnaire responses, learning outcomes were measured by way of picture description and spot the differences tasks administered through a pre-test, post-test, and delayed post-test design. Learner beliefs about CF were probed by means of a 40-item questionnaire. To elicit the learner and teacher perspectives on the study, semi-structured interviews were held with the three teachers and 20 learners, drawn randomly from the participating classes. The results indicated that the noticeability of CF is dependent on the grammatical target it addresses (i.e., feedback on past tense errors was noticed more) and that the feedback techniques that push learners to self-correct alone or in combination with target exemplars are more effective in bringing out the corrective intent of a feedback move. In relation to the learning outcomes, the overall past tense accuracy increased more than that for questions, but there were no differences between the groups. The direct link between noticing and learning could not be unequivocally established. While the inferential statistics suggested a minimal relationship between noticing and past tense scores, especially if the CF was provided with recasts, but no relationship between noticing and questions scores, the qualitative analyses pointed to an association between noticing and test scores (on both targets) for some learners and gains without noticing for others. Finally, in relation to the beliefs about CF, the participants’ responses centered on four common themes (the importance of oral CF, recasts as CF technique, prompts as CF technique, and affective consequences of CF), two of which mediated the noticeability of the supplied CF, but none impacted the learning outcomes.

A conduta criativa de João Cabral de Melo Neto é tradicionalmente caracterizada como uma atividade controlada por uma razão arquitetônica, que lucidamente projeta, e rigorosamente realiza a obra literária. A abordagem, aqui feita, de seu pensamento sobre a criação quer dizer, das representações do fazer em seus poemas metalinguísticos e também de sua prática criativa legível nos traços de seus manuscritos afasta-nos sensivelmente do paradigma da arquitetura. Em seu lugar, propomos considerar o fazer cabralino como uma atividade de reformulação constante, que produz, durante o processo de escrita, novos sentidos e estruturas não determinados a priori, integrando, dessa forma, a imprevisibilidade e a instabilidade na essência mesma da criação literária. / João Cabral de Melo Neto\'s creative conduct is traditionally characterized as an activity directed by an architectonic reasoning, which consciously projects and rigorously realizes the literary work. The approach taken here of his creative thinking that is, of the representations of the act of making in his metalinguistic poems and of his creative practice which is discernible on the glyphs of his manuscripts takes us sensibly away from an architectural paradigm. Instead, we propose to consider Cabral\'s making act as a constant reformulation activity, which produces, during the writing process, new meanings and structures not determined a priori, in this way integrating imprevisibility and instability to the very essence of literary creation.

Différentes études ont montré que le niveau des futurs enseignants, issus des écoles publiques, en français langue étrangère (FLE) en Égypte est assez faible. Ceux-ci font un grand nombre d’erreurs répétitives à l’oral. Quoique ce manque de précision langagière puisse être dû à plusieurs facteurs, il appert que la rétroaction soit une des variables contribuant à ce phénomène (comme le nombre d’étudiants en classe, la durée du cours, l’âge et la motivation des étudiants, les méthodes d’enseignement, etc.). La rétroaction corrective est généralement définie comme toute correction explicite ou implicite de la part de l’enseignant indiquant que la production de l’apprenant est erronée. Elle est considérée comme indispensable dans les classes de langues secondes (LS) (Shmidt, 1983, 2001 ; Long, 1991, 1996 ; Lightbown, 1998). Pour ces raisons, cette étude porte sur la rétroaction corrective et, plus spécifiquement, sur les croyances des enseignants et des apprenants quant à celle-ci, ainsi qu’à son utilisation dans les classes de FLE en Égypte. Les recherches antérieures indiquent que les croyances des enseignants quant à l’acte d’enseigner influencent leurs pratiques en classe, que les croyances des apprenants influencent leur motivation, leur niveau et leurs efforts déployés pour l’apprentissage de la langue, et qu’une divergence entre les croyances des professeurs et celles des apprenants peut entraîner des effets négatifs sur l’apprentissage de la langue cible, ce qui indique ainsi qu’il est de grande importance d’explorer les croyances. Ainsi, la présente étude vise à explorer les croyances des professeurs égyptiens et celles de leurs étudiants en ce qui a trait à la rétroaction corrective à l’oral, la différence entre ces croyances, et l’identification des pratiques réelles des professeurs afin de décrire à quel point celles-ci reflètent les croyances exprimées. Pour ce faire, un questionnaire a été administré à 175 étudiants et 25 professeurs appartenant à trois universités égyptiennes afin de déterminer leurs croyances déclarées. Des entrevues semi-dirigées et des observations directes ont été réalisées auprès de neuf des 25 professeurs participants pour mieux déterminer leurs croyances et leurs pratiques rétroactives. Les résultats obtenus ont révélé qu’il existe des divergences importantes entre les croyances des professeurs et celles des étudiants, d’un côté, et entre les croyances des professeurs et leur pratique, de l’autre côté. Par exemple, la plupart des étudiants ont déclaré leur opposition à l’utilisation de la reformulation alors que presque la moitié des professeurs ont indiqué être en faveur de cette même technique. Les professeurs ont indiqué que leur choix de techniques rétroactives dépend du type d’erreurs et qu’ils préfèrent inciter les apprenants à s’auto corriger. Cependant, ces mêmes professeurs ont utilisé la reformulation pour corriger la majorité des erreurs de leurs apprenants, quelle que soit leur nature. Nous parvenons ainsi à la conclusion que l’utilisation de la reformulation, qui fait l’objet d’une divergence au niveau des croyances, pourrait être à l’origine du manque de précision langagière rapporté par les chercheurs. / Previous research revealed that Egyptian learners of French as a foreign language who will be the future teachers of French in Egypt produce numerous errors repetitively during oral productions. While this lack of accuracy can be attributed to a cohort of factors (number of students in class, duration of course, age and motivation of students, methods of teaching, etc.), it is assumed in the present study that corrective feedback could be at the origins of the reported results. Defined as implicit or explicit teacher reactions to the learners’ incorrect renditions, corrective feedback is seen by many second language acquisition researchers (Schmidt, 1983, 2001; Long, 1991, 1996; Lightbown, 1998) as a driving force behind interlanguage development. Among other things, corrective feedback draws learners’ attention to form and helps them notice the gap between their interlanguage and the L2 norm. In light of these theoretical arguments along with empirical research findings indicating the benefits of corrective feedback, the present study investigated corrective feedback provided in French as a foreign language classes in Egyptian universities. More specifically, the study explored teachers’ and students’ beliefs about feedback as well as teachers’ in-class use of feedback. Previous research on beliefs indicates that teachers’ beliefs shape their teaching and that learners’ beliefs affect their motivation and determine the effort students are willing to deploy to learn the target language. Based on these theoretical and empirical claims, the present study investigated teachers’ and students’ beliefs about oral corrective feedback in learning French as a foreign language in Egypt and explored teachers’ actual corrective feedback practices to determine the extent to which they correspond to their declared beliefs. A beliefs questionnaire was administered to 175 students and 25 language teachers to determine their beliefs about corrective feedback. Nine of the 25 teachers were also interviewed and observed for a total of 27 hours to further investigate their beliefs and in-class practices. The results indicate a mismatch between teachers’ and students’ beliefs on the one hand, and a divergence between teachers’ beliefs and their actual teaching on the other. In terms of the relationship between students’ and teachers’ beliefs, the results reveal that while the majority of the learners do not see recasts as an effective feedback technique, almost half of the teachers do. As for the mismatch between teachers’ beliefs and their in-class practices, a two-fold pattern emerged. First, all the teachers reported that error type determined the technique they used to correct errors and that they preferred to push their learners to self-correct. However, recasts proved to be the technique of choice and that was regardless of error type. Instances of self-correction were rare with teachers choosing to recast most of their students’ errors instead of pushing them to remedy the errors on their own. As such, it may be speculated that the teachers’ choice of corrective feedback techniques, which happens to run counter to the students’ expectations (as shown in the beliefs questionnaire) may be a major factor behind the students’ reported lack of accuracy

Cette étude quasi-expérimentale a pour but de 1) comparer la prise en compte et les effets de trois conditions rétroactives, à savoir la reformulation, l’incitation et un mélange des deux techniques, 2) déterminer le lien entre la prise en compte et l’apprentissage, et 3) identifier l’effet des perceptions des apprenants quant à la rétroaction corrective sur la prise en compte et l’apprentissage. Quatre groupes d’apprenants d’anglais langue seconde ainsi que leurs enseignants provenant d’un CEGEP francophone de l’île de Montréal ont participé à cette étude. Chaque enseignant a été assigné à une condition rétroactive expérimentale qui correspondait le plus à ses pratiques rétroactives habituelles. La chercheure a assuré l’intervention auprès du groupe contrôle. L’utilisation du passé et de la phrase interrogative était ciblée durant l’intervention expérimentale. Des protocoles de pensée à haute voie ainsi qu’un questionnaire ont été utilisés pour mesurer la prise en compte de la rétroaction corrective. Des tâches de description d’images et d’identification des différences entre les images ont été administrées avant l’intervention (pré-test), immédiatement après l’intervention (post-test immédiat) et 8 semaines plus tard (post-test différé) afin d’évaluer les effets des différentes conditions rétroactives sur l’apprentissage des formes cibles. Un questionnaire a été administré pour identifier les perceptions des apprenants quant à la rétroaction corrective. En termes de prise en compte, les résultats indiquent que les participants sont en mesure de remarquer la rétroaction dépendamment de la forme cible (les erreurs dans l’utilisation du passé sont détectées plus que les erreurs d’utilisation de la phrase interrogative) et de la technique rétroactive utilisée (l’incitation et le mélange d’incitation et de reformulations sont plus détectés plus que la reformulation). En ce qui a trait à l’apprentissage, l’utilisation du passé en général est marquée par plus de développement que celle de la phrase interrogative, mais il n'y avait aucune différence entre les groupes. Le lien direct entre la prise en compte et l’apprentissage ne pouvait pas être explicitement établi. Pendant que la statistique inférentielle a suggéré une relation minimale entre la prise en compte du passé et son apprentissage, mais aucune relation entre la prise en compte de la phrase interrogative et son apprentissage, les analyses qualitatives ont montrés à une association entre la prise en compte et l’apprentissage (sur les deux cibles) pour certains étudiants et augmentations sans prise en compte pour d'autres. Finalement, l’analyse factorielle du questionnaire indique la présence de quatre facteurs principaux, à savoir l’importance de la rétroaction corrective, la reformulation, l’incitation et les effets affectifs de la rétroaction. Deux de ces facteurs ont un effet modérateur sur la prise en compte de la rétroaction sans, toutefois, avoir d’impact sur l’apprentissage. / This quasi-experimental study sought to investigate the often assumed yet little investigated relationship between noticing of corrective feedback (CF) and L2 development in relation to learner beliefs about error correction. Specifically, it aimed to (1) uncover the noticeability and effectiveness of three CF techniques (namely, recasts, prompts, a combination of the two) (2) to determine a relationship between noticing of CF and learning of the past tense and questions in the past, and (3) to determine whether learner beliefs about CF mediate what is noticed and learned in the language classroom. The participants were four groups of high-beginner college level francophone ESL learners (n = 99) and their teachers. Each teacher was assigned to a treatment condition that fit his CF style, but the researcher taught the controls. CF was provided to learners in response to their production problems with the simple past and questions in the past. While noticing of CF was assessed through immediate recall and questionnaire responses, learning outcomes were measured by way of picture description and spot the differences tasks administered through a pre-test, post-test, and delayed post-test design. Learner beliefs about CF were probed by means of a 40-item questionnaire. To elicit the learner and teacher perspectives on the study, semi-structured interviews were held with the three teachers and 20 learners, drawn randomly from the participating classes. The results indicated that the noticeability of CF is dependent on the grammatical target it addresses (i.e., feedback on past tense errors was noticed more) and that the feedback techniques that push learners to self-correct alone or in combination with target exemplars are more effective in bringing out the corrective intent of a feedback move. In relation to the learning outcomes, the overall past tense accuracy increased more than that for questions, but there were no differences between the groups. The direct link between noticing and learning could not be unequivocally established. While the inferential statistics suggested a minimal relationship between noticing and past tense scores, especially if the CF was provided with recasts, but no relationship between noticing and questions scores, the qualitative analyses pointed to an association between noticing and test scores (on both targets) for some learners and gains without noticing for others. Finally, in relation to the beliefs about CF, the participants’ responses centered on four common themes (the importance of oral CF, recasts as CF technique, prompts as CF technique, and affective consequences of CF), two of which mediated the noticeability of the supplied CF, but none impacted the learning outcomes.