On certain greedoid polyhedra, partially indexable scheduling problems and extended restless bandit allocation indices

We present a polyhedral framework for establishing general structural properties on optimal solutions of stochastic scheduling problems, where multiple job classes vie for service resources: the existence of an optimal priority policy in a given family, characterized by a greedoid(whose feasible class subsets may receive higher priority), where optimal priorities are determined by class-ranking indices, under restricted linear performance objectives (partial indexability). This framework extends that of Bertsimas and Niño-Mora (1996), which explained the optimality of priority-index policies under all linear objectives (general indexability). We show that, if performance measures satisfy partial conservation laws (with respect to the greedoid), which extend previous generalized conservation laws, then theproblem admits a strong LP relaxation over a so-called extended greedoid polytope, which has strong structural and algorithmic properties. We present an adaptive-greedy algorithm (which extends Klimov's) taking as input the linear objective coefficients, which (1) determines whether the optimal LP solution is achievable by a policy in the given family; and (2) if so, computes a set of class-ranking indices that characterize optimal priority policies in the family. In the special case of project scheduling, we show that, under additional conditions, the optimal indices can be computed separately for each project (index decomposition). We further apply the framework to the important restless bandit model (two-action Markov decision chains), obtaining new index policies, that extend Whittle's (1988), and simple sufficient conditions for their validity. These results highlight the power of polyhedral methods (the so-called achievable region approach) in dynamic and stochastic optimization.

Driver scheduling problem modelling

The Drivers Scheduling Problem (DSP) consists of selecting a set of duties for vehicle drivers, for example buses, trains, plane or boat drivers or pilots, for the transportation of passengers or goods. This is a complex problem because it involves several constraints related to labour and company rules and can also present different evaluation criteria and objectives. Being able to develop an adequate model for this problem that can represent the real problem as close as possible is an important research area.The main objective of this research work is to present new mathematical models to the DSP problem that represent all the complexity of the drivers scheduling problem, and also demonstrate that the solutions of these models can be easily implemented in real situations. This issue has been recognized by several authors and as important problem in Public Transportation. The most well-known and general formulation for the DSP is a Set Partition/Set Covering Model (SPP/SCP). However, to a large extend these models simplify some of the specific business aspects and issues of real problems. This makes it difficult to use these models as automatic planning systems because the schedules obtained must be modified manually to be implemented in real situations. Based on extensive passenger transportation experience in bus companies in Portugal, we propose new alternative models to formulate the DSP problem. These models are also based on Set Partitioning/Covering Models; however, they take into account the bus operator issues and the perspective opinions and environment of the user.We follow the steps of the Operations Research Methodology which consist of: Identify the Problem; Understand the System; Formulate a Mathematical Model; Verify the Model; Select the Best Alternative; Present the Results of theAnalysis and Implement and Evaluate. All the processes are done with close participation and involvement of the final users from different transportation companies. The planner s opinion and main criticisms are used to improve the proposed model in a continuous enrichment process. The final objective is to have a model that can be incorporated into an information system to be used as an automatic tool to produce driver schedules. Therefore, the criteria for evaluating the models is the capacity to generate real and useful schedules that can be implemented without many manual adjustments or modifications. We have considered the following as measures of the quality of the model: simplicity, solution quality and applicability. We tested the alternative models with a set of real data obtained from several different transportation companies and analyzed the optimal schedules obtained with respect to the applicability of the solution to the real situation. To do this, the schedules were analyzed by the planners to determine their quality and applicability. The main result of this work is the proposition of new mathematical models for the DSP that better represent the realities of the passenger transportation operators and lead to better schedules that can be implemented directly in real situations.

A simple optimised search heuristic for the job-shop scheduling problem

This paper presents a simple Optimised Search Heuristic for the Job Shop Scheduling problem that combines a GRASP heuristic with a branch-and-bound algorithm. The proposed method is compared with similar approaches and leads to better results in terms of solution quality and computing times.

Metaheuristics for the bus-driver scheduling problem

We present new metaheuristics for solving real crew scheduling problemsin a public transportation bus company. Since the crews of thesecompanies are drivers, we will designate the problem by the bus-driverscheduling problem. Crew scheduling problems are well known and severalmathematical programming based techniques have been proposed to solvethem, in particular using the set-covering formulation. However, inpractice, there exists the need for improvement in terms of computationalefficiency and capacity of solving large-scale instances. Moreover, thereal bus-driver scheduling problems that we consider can present variantaspects of the set covering, as for example a different objectivefunction, implying that alternative solutions methods have to bedeveloped. We propose metaheuristics based on the following approaches:GRASP (greedy randomized adaptive search procedure), tabu search andgenetic algorithms. These metaheuristics also present some innovationfeatures based on and genetic algorithms. These metaheuristics alsopresent some innovation features based on the structure of the crewscheduling problem, that guide the search efficiently and able them tofind good solutions. Some of these new features can also be applied inthe development of heuristics to other combinatorial optimizationproblems. A summary of computational results with real-data problems ispresented.

Solving a concrete sleepers production scheduling by genetic algorithms

PRECON S.A is a manufacturing company dedicated to produce prefabricatedconcrete parts to several industries as rail transportation andagricultural industries.Recently, PRECON signed a contract with RENFE,the Spanish Nnational Rail Transportation Company to manufacturepre-stressed concrete sleepers for siding of the new railways of the highspeed train AVE. The scheduling problem associated with the manufacturingprocess of the sleepers is very complex since it involves severalconstraints and objectives. The constraints are related with productioncapacity, the quantity of available moulds, satisfying demand and otheroperational constraints. The two main objectives are related withmaximizing the usage of the manufacturing resources and minimizing themoulds movements. We developed a deterministic crowding genetic algorithmfor this multiobjective problem. The algorithm has proved to be a powerfuland flexible tool to solve the large-scale instance of this complex realscheduling problem.

Phylogeographic patterning of mtDNA in the widely distributed harvest mouse (Micromys minutus) suggests dramatic cycles of range contraction and expansion during the mid- to late Pleistocene

We examined sequence variation in the mitochondrial cytochrome b gene (1140 bp, n = 73) and control region (842-851 bp, n = 74) in the Eurasian harvest mouse (Micromys minutus (Pallas, 1771)), with samples drawn from across its range, from Western Europe to Japan. Phylogeographic analyses revealed region-specific haplotype groupings combined with overall low levels of inter-regional genetic divergence. Despite the enormous intervening distance, European and East Asian samples showed a net nucleotide divergence of only 0.36%. Based on an evolutionary rate for the cytochrome b gene of 2.4%(.)(site(.)lineage(.)million years)(-1), the initial divergence time of these populations is estimated at around 80 000 years before present. Our findings are consistent with available fossil evidence that has recorded repeated cycles of extinction and recolonization of Europe by M. minutus through the Quaternary. The molecular data further suggest that recolonization occurred from refugia in the Central to East Asian region. Japanese haplotypes of M. minutus, with the exception of those from Tsushima Is., show limited nucleotide diversity (0.15%) compared with those found on the adjacent Korean Peninsula. This finding suggests recent colonization of the Japanese Archipelago, probably around the last glacial period, followed by rapid population growth.

Linking Real Time and Location in Scheduling Demand-Responsive Transit, September 1996

The role of rural demand-responsive transit is changing, and with that change is coming an increasing need for technology. As long as rural transit was limited to a type of social service transportation for a specific set of clients who primarily traveled in groups to common meal sites, work centers for the disabled, or clinics in larger communities, a preset calendar augmented by notes on a yellow legal pad was sufficient to develop schedules. Any individual trips were arranged at least 24 to 48 hours ahead of time and were carefully scheduled the night before in half-hour or twenty-minute windows by a dispatcher who knew every lane in the service area. Since it took hours to build the schedule, any last-minute changes could wreak havoc with the plans and raise the stress level in the dispatch office. Nevertheless, given these parameters, a manual scheduling system worked for a small demand-responsive operation.

Harvest managements and cultural practices in sugarcane

The presence of trash from the mechanical harvest of green cane on sugarcane plantations promotes changes in the agricultural management, for example, in the mechanical cultural practices of ratoon cane in-between the rows and nitrogen (N) fertilization. The goal of this study was to evaluate the performance of sugarcane in different harvest systems, associated to the mechanical cultural practices in interrows and N rates. The study was carried out on a sugarcane plantation in Sales Oliveira, São Paulo, Brazil, with the sugarcane variety SP81-3250, on soil classified as Acrudox, in a randomized block design with split-split plots and four replications. The main treatments consisted of harvest systems (harvesting green cane or burnt cane), the secondary treatment consisted of the mechanical cultural practices in the interrows and the tertiary treatments were N rates (0, 30, 60, 90, 120 and 160 kg ha-1), using ammonium nitrate (33 % N) as N source. The harvest systems did not differ in sugarcane yield (tons of cane per hectare - TCH), but in burnt cane, the pol percent and total sugar recovery (TSR) were higher. This could be explained by the higher quantity of plant impurities in the harvested raw material in the system without burning, which reduces the processing quality. Mechanical cultural practices in the interrows after harvest had no effect on cane yield and sugar quality, indicating that this operation can be omitted in areas with mechanical harvesting. The application of N fertilizer at rates of 88 and 144 kg ha-1 N, respectively, increased stalk height and TCH quadratically to the highest values for these variables. For the sugar yield per hectare (in pol %), N fertilization induced a linear increase.

Early Changes in Soil Metabolic Diversity and Bacterial Community Structure in Sugarcane under Two Harvest Management Systems

Preharvest burning is widely used in Brazil for sugarcane cropping. However, due to environmental restrictions, harvest without burning is becoming the predominant option. Consequently, changes in the microbial community are expected from crop residue accumulation on the soil surface, as well as alterations in soil metabolic diversity as of the first harvest. Because biological properties respond quickly and can be used to monitor environmental changes, we evaluated soil metabolic diversity and bacterial community structure after the first harvest under sugarcane management without burning compared to management with preharvest burning. Soil samples were collected under three sugarcane varieties (SP813250, SP801842 and RB72454) and two harvest management systems (without and with preharvest burning). Microbial biomass C (MBC), carbon (C) substrate utilization profiles, bacterial community structure (based on profiles of 16S rRNA gene amplicons), and soil chemical properties were determined. MBC was not different among the treatments. C-substrate utilization and metabolic diversity were lower in soil without burning, except for the evenness index of C-substrate utilization. Soil samples under the variety SP801842 showed the greatest changes in substrate utilization and metabolic diversity, but showed no differences in bacterial community structure, regardless of the harvest management system. In conclusion, combined analysis of soil chemical and microbiological data can detect early changes in microbial metabolic capacity and diversity, with lower values in management without burning. However, after the first harvest, there were no changes in the soil bacterial community structure detected by PCR-DGGE under the sugarcane variety SP801842. Therefore, the metabolic profile is a more sensitive indicator of early changes in the soil microbial community caused by the harvest management system.

Timing of primary growth harvest affects the yield and nutritive value of timothy-red clover mixtures

Selostus: Ensimmäisen sadon korjuuaika vaikuttaa timotein ja puna-apilan seosnurmen satoon ja rehuarvoon

Effect of harvest time on storage loss and sprouting in onion

Selostus: Sadonkorjuuajan vaikutus sipulin varastohävikkiin ja varastoinnin jälkeiseen versomiseen

Micro-Computer Based Linear Scheduling Application for Highway Construction Project Control, HR-339A, 1995

This report describes a new approach to the problem of scheduling highway construction type projects. The technique can accurately model linear activities and identify the controlling activity path on a linear schedule. Current scheduling practices are unable to accomplish these two tasks with any accuracy for linear activities, leaving planners and manager suspicious of the information they provide. Basic linear scheduling is not a new technique, and many attempts have been made to apply it to various types of work in the past. However, the technique has never been widely used because of the lack of an analytical approach to activity relationships and development of an analytical approach to determining controlling activities. The Linear Scheduling Model (LSM) developed in this report, completes the linear scheduling technique by adding to linear scheduling all of the analytical capabilities, including computer applications, present in CPM scheduling today. The LSM has tremendous potential, and will likely have a significant impact on the way linear construction is scheduled in the future.