Eigenvalues of the Laplacian on symmetric regions

It was shown by Micheletti [11] that the eigenvalues of the Laplacian with Dirichlet boundary conditions are simple for most boundedC ³ regions. We show that this is not true if we restrict our attention to the subset of regions which are invariant under a group of symmetries. We also prove, for some groups, that generically the eigenspaces are irreducible spaces for the action of the group.Supported in part by FAPESP-Fundacão de Amparo à Pesquisa do Estado de São Paulo-São Paulo     

Some integer programs arising in the design of main frame computers

In this paper we describe and discuss a problem that arises in the (global) design of a main frame computer. The task is to assign certain functional units to a given number of so called multi chip modules or printed circuit boards taking into account many technical constraints and minimizing a complex objective function. We describe the real world problem. A thorough mathematical modelling of all aspects of this problem results in a rather complicated integer program that seems to be hopelessly difficult — at least for the present state of integer programming technology. We introduce several relaxations of the general model, which are alsoNP-hard, but seem to be more easily accessible. The mathematical relations between the relaxations and the exact formulation of the problem are discussed as well.On leave from University of São Paulo, Brazil.     

Weekly staff scheduling with workstation group restrictions

This paper addresses the weekly adjustment problem for staff scheduling when movement restrictions exist between workstation groups (WSGs). In practice, it is common for employees to be organized into physical or logical groups to match the layout of a facility or to facilitate managerial oversight. A complication in the problem arises when each employee is required to spend more time at his or her assigned home base during the week than at any other WSG. This conflicts with a common strategy of reassigning employees to different WSGs when idle time exists in their schedules. Ordinarily, the full problem is tackled with a two-phase approach, where optimal shifts and overtime allocations are first derived and then tasks are assigned. When movement restrictions exist in a facility, this approach is no longer practical or even possible for all but the smallest instances. Alternatively, a new model is proposed that integrates WSG restrictions with the shift scheduling and task assignment constraints. The model takes the form of a large-scale integer program and is solved with one of two decomposition heuristics. The first splits the movement restrictions network into manageable pieces; the second uses column generation to identify good individual schedules that are used to construct a set-covering-type master problem. A solution to the master problem provides a feasible solution to the original integer program. Extensive testing was done with data obtained from the U.S. Postal Service mail processing and distribution center in Dallas. The results show that good feasible solutions can be obtained in less than an hour.     

On the effective computation of the inertia of a non-hermitian matrix

Summary given a complex lower Hessenberg matrixA with unit codiagonal, a hermitian matrixH is constructed such that, ifH is non-singular InA= InH. IfA is real,H is real symmetric. Classical results of Fujiwara on the root-separation problem and of Schwarz on the eigenvalue-separation problem are included as special cases.The authors' research was conducted at the Universidade Estadual de Campinas and supported by the Fundação de Amparo à Pesquisa do Estado de São Paulo, Brasil, under grant n⁰ 78/0490.     

The Riemann problem for a class of resonant hyperbolic systems of balance laws

We solve the Riemann problem for a class of resonant hyperbolic systems of balance laws. The systems are not strictly hyperbolic and the solutions take their values in a neighborhood of a state where two characteristic speeds coincide. Our construction generalizes the ones given earlier by Isaacson and Temple for scalar equations and for conservative systems. The class of systems under consideration here includes, in particular, a model from continuum physics that describes the evolution of a fluid flow in a nozzle with discontinuous cross-section.

Résumé

Nous résolvons le problème de Riemann pour une classe de systèmes hyperboliques non-conservatifs et résonants. Ces systèmes ne sont pas strictement hyperboliques et les solutions considérées prennent leurs valeurs au voisinage d'un état constant où deux des vitesses caractéristiques coincident. Notre construction généralise celle donnée précédemment par Isaacson et Temple pour les équations scalaires et les systèmes conservatifs. La classe générale de systèmes étudiée ici comprend, en particulier, un modèle important de la dynamique des milieux continus qui décrit l'évolution d'un fluide dans une tuyère dont la section est discontinue.     

The Influence of Positivism on the Teaching of Mathematics in Brazil: 1870–1930

This article describes the strong influence of positivism on the teaching of mathematics in Brazil. The dissemination of positivism occurred in a very intensive way from 1870 to 1930, due mainly to the strong leadership of teachers at the military and engineering academies. From its firmly entrenched position in these institutions, the positivistic ideology affected the social, political, pedagogical, and ideological life in Brazil. Here, I identify the main representatives of positivism, who focused their research on Auguste Comte's concept of mathematics. They oriented curricula and programs according to Comte's principles as well as produced mathematics with a distinct positivist bent. Although a marked decline occurred after 1930, the positivistic phenomenon was not exhausted as a research topic, and, indeed, it still has not been entirely extinguished in Brazilian life. Copyright 1999 Academic Press.Este trabalho descreve a forte influência do positivismo no ensino da Matemática no Brasil. A difusão do positivismo aconteceu de forma muita intensa entre 1870 e 1930, devido principalmente a atuação dos docentes-militares, que mantinham uma liderança forte nas academias militares e de engenharia. Nestas instituições a ideologia positivista encontrou uma forte sustentação e pode, então, ter efeitos na vida social, polı́tica, pedagógica e ideológica brasileira. Identificamos os principais representantes do positivismo no cı́rculo acadêmico. Detectamos as primeiras manifestações da concepção de Matemática de Auguste Comte em livros-texto. Identificamos a orientação de currı́culos e programas segundo os preceitos de Comte e analisamos principalmente as obras de Matemática de autores positivistas. O declı́nio do positivismos depois de 1930 também é registrado. O fenômeno positivismo não foi esgotado como tema de pesquisa e tudo indica que ainda não se extinguiu completamente da vida brasileira. Copyright 1999 Academic Press.MSC 1991 subject classifications: 01A55, 01A70.     

A combined ship scheduling and allocation problem

We present a bulk ship scheduling problem that is a combined multi-ship pickup and delivery problem with time windows (m-PDPTW) and multi-allocation problem. In contrast to other ship scheduling problems found in the literature, each ship in the fleet is equipped with a flexible cargo hold that can be partitioned into several smaller holds in a given number of ways. Therefore, multiple products can be carried simultaneously by the same ship. The scheduling of the ships constitutes the m-PDPTW, while the partition of the ships' flexible cargo holds and the allocation of cargoes to the smaller holds make the multi-allocation problem. A set partitioning approach consisting of two phases is proposed for the combined ship scheduling and allocation problem. In the first phase, a number of candidate schedules (including allocation of cargoes to the ships' cargo holds) is generated for each ship. In the second phase, we minimise transportation costs by solving a set partitioning problem where the columns are the candidate schedules generated in phase one. The computational results show that the proposed approach works, and optimal solutions are obtained on several cases of a real ship planning problem.     

A model and computational tool for crew scheduling in train transportation of mine materials by using a local search strategy

This work introduces a model of the crew scheduling problem for the operation of trains in the mining industry in the North of Chile. The model possesses particular features due to specific regulations with which train operators in mine material transportation are required to comply: every week, a fixed set of trips must be made according to current demand for the transportation of mine products and supplies. In order to balance the loads of the crews in the long term, the proposed model generates an infinite horizon schedule by means of a rotative scheme in which each crew takes the place of the previous one at the beginning of the next week. This gives rise to a medium/large size 0–1 linear optimization problem, whose solution represents the optimal assignment of drivers to trips with the number of working hours per week distributed equally among crews. The model and algorithm have been implemented with a user interface suitable for the remote execution of real instances on a High Performance Computing platform. The transportation company regularly uses this computerized tool for planning crew schedules and generating efficient assignments for emerging and changing operational conditions.     

Asymptotic behavior of solutions of the Cauchy problem for Burgers type equations

We show that the solutions of the initial value problems for a large class of Burgers type equations approach with time to the sum of appropriately shifted wave-trains and of diffusion waves.

Résumé

Nous montrons que les solutions du problème de Cauchy pour une grande classe d'équations de type de Burgers sont approchées en temps grand vers des sommes d'ondes de diffusion et d'ondes progressives adéquatement translatées.     

Integrated scheduling of crane handling and truck transportation in a maritime container terminal

This paper studies the interactions between crane handling and truck transportation in a maritime container terminal by addressing them simultaneously. Yard trucks are shared among different ships, which helps to reduce empty truck trips in the terminal area. The problem is formulated as a constraint programming model and a three-stage algorithm is developed. At the first stage, crane schedules are generated by a heuristic method. At the second stage, the multiple-truck routing problem is solved based on the precedence relations of the transportation tasks derived from the first stage. At the last stage a complete solution is constructed by using a disjunctive graph. The three procedures are linked by an iterative structure, which facilitates the search for a good solution. The computational results indicate that the three-stage algorithm is effective for finding high-quality solutions and can efficiently solve large problems.     

Algebras, Projective Geometry, Mathematical Logic, and Constructing the World: Intersections in the Philosophy of Mathematics of A. N. Whitehead

A. N. Whitehead (1861–1947) contributed notably to the foundations of pure and applied mathematics, especially from the late 1890s to the mid 1920s. An algebraist by mathematical tendency, he surveyed several algebras in his book Universal Algebra (1898). Then in the 1900s he joined Bertrand Russell in an attempt to ground many parts of mathematics in the newly developing mathematical logic. In this connection he published in 1906 a long paper on geometry, space and time, and matter. The main outcome of the collaboration was a three-volume work, Principia Mathematica (1910–1913): he was supposed to write a fourth volume on parts of geometries, but he abandoned it after much of it was done. By then his interests had switched to educational issues, and especially to space and time and relativity theory, where his earlier dependence upon logic was extended to an ontology of events and to a general notion of “process,” especially in human experience. These innovations led to somewhat revised conceptions of logic and of the philosophy of mathematics. © 2002 Elsevier Science (USA).A. N. Whitehead (1861–1947) contribuiu de forma marcante para os Fundamentos da Matemática Pura e Aplicada, especialmente entre o fim da década de 1890 e meados da década de 1920. Sendo um algebrista na sua vertente matemática, fez um levantamento de diversas álgebras no seu livro Universal Algebra (1898). Pouco depois de 1900 juntou-se a Bertrand Russell numa tentativa para basear várias partes da matemática sobre a lógica matemática, que se começava então a desenvolver. Nesse âmbito publicou em 1906 um longo artigo sobre geometria, espaço e tempo, e matéria. O principal resultado da colaboração foi um trabalho em três volumes, Principia Mathematica (1910–1913): estava previsto que Whitehead escrevesse um quarto volume sobre aspectos das geometrias, mas abandonou-o depois de uma boa parte já estar escrita. Por essa altura os seus interesses tinham-se voltado para questões educacionais; especialmente para o espaço e o tempo e para a teoria da relatividade, onde a sua anterior dependência da lógica se estendeu a uma ontologia de acontecimentos e a uma noção geral de “processo” especialmente na experiência humana. Estas inovações levaram a concepções um pouco revistas da lógica e da filosofia da matemática. © 2002 Elsevier Science (USA).MSC 1991 subject classifications: 00A30; 01A60; 03-03; 03A05.     

On the approximate form of Kluvánek's theorem

An abstract form of the classical approximate sampling theorem is proved for functions on a locally compact abelian group that are continuous, square-integrable and have integrable Fourier transforms. An additional hypothesis that the samples of the function are square-summable is needed to ensure the convergence of the sampling series. As well as establishing the representation of the function as a sampling series plus a remainder term, an asymptotic formula is obtained under mild additional restrictions on the group. In conclusion a converse to Kluvánek's theorem is established.     

Exact algorithms for the traveling salesman problem with draft limits

This paper deals with the Traveling Salesman Problem (TSP) with Draft Limits (TSPDL), which is a variant of the well-known TSP in the context of maritime transportation. In this recently proposed problem, draft limits are imposed due to restrictions on the port infrastructures. Exact algorithms based on three mathematical formulations are proposed and their performance compared through extensive computational experiments. Optimal solutions are reported for open instances of benchmark problems available in the literature.     

On optimal high accuracy linear multistep methods for first kind volterra integral equations

General linear multistep methods which include those of Holyhead et al. [9] and Gladwin et al. [8] are introduced. A new simple root condition for stability is deduced. A theorem relating the coefficients of this new associated stability polynomial to those of the method is proved. This permits a constructive approach for obtaining high accuracy convergent methods. Two such methods are derived and numerical results are presented.This work was done under the financial support of: Fundação de Amparo à Pesquisa do Estado de São Paulo (FAPESP), and Financiadora Nacional de Empreendimentos e Projetos (FINEP)—Ministério do Planejamento (Brazil).     

Dynamic transport scheduling under multiple resource constraints

This paper presents a heuristic for the dynamic vehicle scheduling problem with multiple resource capacity constraints. In the envisaged application, an automated transport system using Automated Guided Vehicles, bottleneck resources are (1) vehicles, (2) docks for loading/unloading, (3) vehicle parking places, and (4) load storage space. This problem is hard, because interrelated activities (loading, transportation, unloading) at several geographical locations have to be scheduled under multiple resource constraints, where the bottleneck resource varies over time. Besides, the method should be suitable for real-time planning. We developed a dedicated serial scheduling method and analyzed its dynamic behavior using discrete event simulation. We found that our method is very well able to find good vehicle schedules satisfying all resource constraints. For comparison, we used a simple approach where we left out the resource constraints and extended the processing times by statistically estimated waiting times to account for finite capacities. We found that our newly designed method finds better schedules in terms of service levels.     

Planning the Restoration of an Open-cast Coal Site

This paper describes an operational research approach to planning the restoration of an open-cast coal site.No established operational research technique exactly fitted the problem, which was one of planning a large-scale earth-moving operation, where the quantities to be moved were not specified, but had to be planned to conform with stringent restrictions on gradients, continuity, drainage and total volume. A numerical technique was developed, used in conjunction with the dual solutions of successive transportation programmes to reach progressively an optimum solution.The nature of the problem allowed an unusually clear-cut comparison to be made between the previous conventional plan and the operational-research-based plan; the latter showed considerable savings and was put into practice.There would appear to be many other situations where the approach could be applied.     

Use of VNS heuristics for scheduling of patients in hospital

One of the important problems in hospital management is how to schedule the treatments of resident patients in hospital for a given day due to the restrictions imposed by their medical condition as well as restrictions on medical machines and qualified medical personnel availability. Patients are to be subjected to different kinds of treatments, each requiring a medical machine of a certain type as well as a physician being qualified to operate it. This is a highly complex problem not yet adequately addressed in the literature. At present in most hospitals the problem is being solved manually by specialized personnel. However, the resulting schedules are very often inaccurate and inefficient with patients waiting for a long time to be treated and medical personnel often working overtime. In this paper we formulate the model for this problem and develop a simple and efficient method based on Variable Neighbourhood Search for solving it. The heuristics has been tested on real-life as well as on generated instances. Numerical results show that the heuristics proposed outperform commercial software for optimization as well as manual solutions both in quality of solution and in computational time.     

A framework for optimization under ambiguity

Recently, crossdocking techniques have been successfully applied in responsive supply chain management. However, most researches focused on physical layout of a crossdock, or scheduling operations within a crossdock. In this paper, we study a multi-crossdock transshipment service problem with both soft and hard time windows. The flows from suppliers to customers via the crossdocks are constrained by fixed transportation schedules. Cargos can be delayed and consolidated in crossdocks, and both suppliers and customers have specific hard time windows. In addition to hard time windows, customers also have less-restrictive time windows, called soft time windows. The problem to minimize the total cost of the multi-crossdock distribution network, including transportation cost, inventory handling cost and penalty cost, can be proved to be NP-hard in the strong sense and hence efficient heuristics are desired. We propose two types of meta-heuristic algorithms, called Adaptive Tabu Search and Adaptive Genetic Algorithm, respectively, to solve the problem efficiently. We conduct extensive experiments and the results show that both of them outperform CPLEX solver and provide fairly good solutions within realistic timescales. We also perform sensitivity analysis and obtain a number of managerial insights.     

Modelling and solving an <Emphasis Type="Italic">m</Emphasis>-location, <Emphasis Type="Italic">n</Emphasis>-courier,priority-based planning problem on a network

In this paper, we study an m-location, n-courier, priority-based planning problem on a network, which we refer to as the Courier Planning Problem (CPP). The CPP arises on a daily basis in the context of planning the transportation of materials and personnel in peacetime for the Turkish Armed Forces. The main issue addressed in CPP is to transport as many of deliverables as possible from their origins to their destinations via a fleet of transportation assets (couriers) that operate at fixed routes and schedules. Priorities must be taken into account and constraints on the routes, operating schedules, and capacities of the transportation assets must be obeyed. Time windows may be specified for some or all transportation requests and must be satisfied. We study the CPP as well as its two extensions, and present integer programming formulations based on the multi-commodity flow structure. The formulations are tested on real world-based data and display satisfactory computational performance. Our main contributions are to develop an effective formulation scheme for a complicated large-scale real world problem and to demonstrate that such problems are solvable via commercial general purpose solvers through meticulous modelling.     

Boussinesq-type system of equations in the Bénard-Marangoni system

A system of coupled evolution equations for the bulk velocity and the surface displacement is found to govern the longwavelength perturbations in a Bénard-Marangoni system. This system of equations, involving nonlinearity, dispersion, and dissipation, is a generalization of the usual Boussinesq system.Instituto de Física Teórica, Universidade Estadual, Paulista, Rua Pamplona 145, 01405-900 São Paulo SP, Brazil. Laboratoire de Physique Mathématique, Université de Montpellier II, 34095 Montpellier Cedex 05, France. Translated from Teoreticheskaya i Matematicheskaya Fizika, Vol. 99, No. 3, pp. 419–427, June, 1994.