Vehicle Routing Problems that Minimize the Completion Time: Heuristics, Worst-Case Analyses, and Computational Results

In the standard Vehicle Routing Problem (VRP), we route a fleet of vehicles to deliver the demands of all customers such that the total distance traveled by the fleet is minimized. In this dissertation, we study variants of the VRP that minimize the completion time, i.e., we minimize the distance of the longest route. We call it the min-max objective function. In applications such as disaster relief efforts and military operations, the objective is often to finish the delivery or the task as soon as possible, not to plan routes with the minimum total distance. Even in commercial package delivery nowadays, companies are investing in new technologies to speed up delivery instead of focusing merely on the min-sum objective. In this dissertation, we compare the min-max and the standard (min-sum) objective functions in a worst-case analysis to show that the optimal solution with respect to one objective function can be very poor with respect to the other. The results motivate the design of algorithms specifically for the min-max objective. We study variants of min-max VRPs including one problem from the literature (the min-max Multi-Depot VRP) and two new problems (the min-max Split Delivery Multi-Depot VRP with Minimum Service Requirement and the min-max Close-Enough VRP). We develop heuristics to solve these three problems. We compare the results produced by our heuristics to the best-known solutions in the literature and find that our algorithms are effective. In the case where benchmark instances are not available, we generate instances whose near-optimal solutions can be estimated based on geometry. We formulate the Vehicle Routing Problem with Drones and carry out a theoretical analysis to show the maximum benefit from using drones in addition to trucks to reduce delivery time. The speed-up ratio depends on the number of drones loaded onto one truck and the speed of the drone relative to the speed of the truck.

Reliability concepts applied to cutting tool change time

This paper presents a reliability-based analysis for calculating critical tool life in machining processes. It is possible to determine the running time for each tool involved in the process by obtaining the operations sequence for the machining procedure. Usually, the reliability of an operation depends on three independent factors: operator, machine-tool and cutting tool. The reliability of a part manufacturing process is mainly determined by the cutting time for each job and by the sequence of operations, defined by the series configuration. An algorithm is presented to define when the cutting tool must be changed. The proposed algorithm is used to evaluate the reliability of a manufacturing process composed of turning and drilling operations. The reliability of the turning operation is modeled based on data presented in the literature, and from experimental results, a statistical distribution of drilling tool wear was defined, and the reliability of the drilling process was modeled. (C) 2010 Elsevier Ltd. All rights reserved.

An efficient heuristic for total flowtime minimisation in no-wait flowshops

In this paper, we address the problem of scheduling jobs in a no-wait flowshop with the objective of minimising the total completion time. This problem is well-known for being nondeterministic polynomial-time hard, and therefore, most contributions to the topic focus on developing algorithms able to obtain good approximate solutions for the problem in a short CPU time. More specifically, there are various constructive heuristics available for the problem [such as the ones by Rajendran and Chaudhuri (Nav Res Logist 37: 695-705, 1990); Bertolissi (J Mater Process Technol 107: 459-465, 2000), Aldowaisan and Allahverdi (Omega 32: 345-352, 2004) and the Chins heuristic by Fink and Voa (Eur J Operat Res 151: 400-414, 2003)], as well as a successful local search procedure (Pilot-1-Chins). We propose a new constructive heuristic based on an analogy with the two-machine problem in order to select the candidate to be appended in the partial schedule. The myopic behaviour of the heuristic is tempered by exploring the neighbourhood of the so-obtained partial schedules. The computational results indicate that the proposed heuristic outperforms existing ones in terms of quality of the solution obtained and equals the performance of the time-consuming Pilot-1-Chins.

The influence of preparedness on rapid stepping in young and older adults

Objective: To investigate the influence of age and preparation level on postural muscle activation and step completion time during a rapid step task. Design: Postural muscle onset times (EMG) and ground reaction forces were recorded from healthy young (n = 20, age 21 +/- 3 years) and older (n = 25, age 71 +/- 5 years) female adults during a choice reaction-time stepping paradigm. Main outcome measures: Onset times of six trunk and hip muscles, reaction time and components of the step (weight shift time, step time and task time) were recorded. Results: Muscle activation was delayed and movement time was lengthened in both young and older adults when poorly prepared for a stepping task. While reduced preparation did not influence older adults to a greater extent than young adults, the slowest step response and completion time was evident in older adults when poorly prepared to move. Conclusions: A late postural response when poorly prepared to move may be a contributing factor to an increased risk of overbalancing in older adults. Future assessment of and intervention to improve postural stability in older adults should be expanded to incorporate tasks performed at various levels of preparation.

A hybrid genetic algorithm for the multi-mode resource-constrained project scheduling

A construction project is a group of discernible tasks or activities that are conduct-ed in a coordinated effort to accomplish one or more objectives. Construction projects re-quire varying levels of cost, time and other resources. To plan and schedule a construction project, activities must be defined sufficiently. The level of detail determines the number of activities contained within the project plan and schedule. So, finding feasible schedules which efficiently use scarce resources is a challenging task within project management. In this context, the well-known Resource Constrained Project Scheduling Problem (RCPSP) has been studied during the last decades. In the RCPSP the activities of a project have to be scheduled such that the makespan of the project is minimized. So, the technological precedence constraints have to be observed as well as limitations of the renewable resources required to accomplish the activities. Once started, an activity may not be interrupted. This problem has been extended to a more realistic model, the multi-mode resource con-strained project scheduling problem (MRCPSP), where each activity can be performed in one out of several modes. Each mode of an activity represents an alternative way of combining different levels of resource requirements with a related duration. Each renewable resource has a limited availability for the entire project such as manpower and machines. This paper presents a hybrid genetic algorithm for the multi-mode resource-constrained pro-ject scheduling problem, in which multiple execution modes are available for each of the ac-tivities of the project. The objective function is the minimization of the construction project completion time. To solve the problem, is applied a two-level genetic algorithm, which makes use of two separate levels and extend the parameterized schedule generation scheme. It is evaluated the quality of the schedules and presents detailed comparative computational re-sults for the MRCPSP, which reveal that this approach is a competitive algorithm.

A genetic algorithm for project scheduling with multi-modes and renewable resources

This paper presents a genetic algorithm-based approach for project scheduling with multi-modes and renewable resources. In this problem activities of the project may be executed in more than one operating mode and renewable resource constraints are imposed. The objective function is the minimization of the project completion time. The idea of this approach is integrating a genetic algorithm with a schedule generation scheme. This study also proposes applying a local search procedure trying to yield a better solution when the genetic algorithm and the schedule generation scheme obtain a solution. The experimental results show that this algorithm is an effective method for solving this problem.

A two-level genetic algorithm for the multi-mode resource-constrained project scheduling problem

This paper presents a genetic algorithm for the multimode resource-constrained project scheduling problem (MRCPSP), in which multiple execution modes are available for each of the activities of the project. The objective function is the minimization of the construction project completion time. To solve the problem, is applied a two-level genetic algorithm, which makes use of two separate levels and extend the parameterized schedule generation scheme by introducing an improvement procedure. It is evaluated the quality of the schedule and present detailed comparative computational results for the MRCPSP, which reveal that this approach is a competitive algorithm.

Afetação de recursos em sistemas de produção

O problema do escalonamento, por ser um dos factores fundamentais na tomada de decisão para uma boa gestão das operações, tem sido alvo de um amplo estudo, tanto na sua componente teórica como na sua componente prática. A importância de um escalonamento correto das operações é preponderante, quando as pequenas diferenças, em termos de tempos de produção, podem ter um grande impacto na competitividade da organização. Em muitas unidades produtivas, existem máquinas capazes de realizar as mesmas operações com diferentes desempenhos. Isto pode dever-se à necessidade de flexibilizar os recursos ou mesmo a uma atualização da capacidade produtiva. Embora os problemas de máquinas diferentes em paralelo tenham sido alvo de um vasto estudo, muitos deles não são passíveis de ser resolvidos através de métodos exatos. O problema de minimização do makespan (Rm||Cmax), é NP-hard, sendo habitualmente abordado através de heurísticas. Entre as heurísticas utilizadas em problemas de minimização do makespan em máquinas diferentes em paralelo, é possível identificar duas filosofias de afectação: a que utiliza os tempos de processamento para alocar as tarefas e a que utiliza as datas de conclusão. Nesta dissertação, pretende-se dar uma contribuição para a resolução do problema de afectação de recursos em sistemas de produção. Para tal, foram propostas as heurísticas OMTC 3 e Suffrage One. A contribuição consiste na proposta de versões híbridas e modificadas das heurística MCT e Suffrage, uma vez identificadas várias características que podem limitar o seu desempenho, como o facto da heurística MCT alocar as tarefas numa ordem aleatória ou a heurística Suffrage alocar mais que uma tarefa por iteração. Finalmente, procedeu-se à realização de testes computacionais, para avaliar o desempenho das heurísticas propostas. Os testes realizados permitiram concluir que a heurística OMTC 3 apresentou um melhor desempenho que a heurística MCT.

Estudo e análise do sequenciamento de tarefas de produção: job shop scheduling

Esta dissertação apresenta um estudo sobre os problemas de sequenciamento de tarefas de produção do tipo job shop scheduling. Os problemas de sequenciamento de tarefas de produção pretendem encontrar a melhor sequência para o processamento de uma lista de tarefas, o instante de início e término de cada tarefa e a afetação de máquinas para as tarefas. Entre estes, encontram-se os problemas com máquinas paralelas, os problemas job shop e flow shop. As medidas de desempenho mais comuns são o makespan (instante de término da execução de todas as tarefas), o tempo de fluxo total, a soma dos atrasos (tardiness), o atraso máximo, o número de tarefas que são completadas após a data limite, entre outros. Num problema do tipo job shop, as tarefas (jobs) consistem num conjunto de operações que têm de ser executadas numa máquina pré-determinada, obedecendo a um determinado sequenciamento com tempos pré-definidos. Estes ambientes permitem diferentes cenários de sequenciamento das tarefas. Normalmente, não são permitidas interrupções no processamento das tarefas (preemption) e pode ainda ser necessário considerar tempos de preparação dependentes da sequência (sequence dependent setup times) ou atribuir pesos (prioridades) diferentes em função da importância da tarefa ou do cliente. Pretende-se o estudo dos modelos matemáticos existentes para várias variantes dos problemas de sequenciamento de tarefas do tipo job shop e a comparação dos resultados das diversas medidas de desempenho da produção. Este trabalho contribui para demonstrar a importância que um bom sequenciamento da produção pode ter na sua eficiência e consequente impacto financeiro.

Performance on a Virtual Reality Angled Laparoscope Task Correlates with Spatial Ability of Trainees

The aim of the present study was to investigate whether trainees' performance on a virtual reality angled laparoscope navigation task correlates with scores obtained on a validated conventional test of spatial ability. 56 participants of a surgery workshop performed an angled laparoscope navigation task on the Xitact LS 500 virtual reality Simulator. Performance parameters were correlated with the score of a validated paper-and-pencil test of spatial ability. Performance at the conventional spatial ability test significantly correlated with performance at the virtual reality task for overall task score (p < 0.001), task completion time (p < 0.001) and economy of movement (p = 0.035), not for endoscope travel speed (p = 0.947). In conclusion, trainees' performance in a standardized virtual reality camera navigation task correlates with their innate spatial ability. This VR session holds potential to serve as an assessment tool for trainees.

Satisfaction of patients hospitalised in psychiatric hospitals: a randomised comparison of two psychiatric-specific and one generic satisfaction questionnaires.

BACKGROUND: While there is interest in measuring the satisfaction of patients discharged from psychiatric hospitals, it might be important to determine whether surveys of psychiatric patients should employ generic or psychiatry-specific instruments. The aim of this study was to compare two psychiatric-specific and one generic questionnaires assessing patients' satisfaction after a hospitalisation in a psychiatric hospital. METHODS: We randomised adult patients discharged from two Swiss psychiatric university hospitals between April and September 2004, to receive one of three instruments: the Saphora-Psy questionnaire, the Perceptions of Care survey questionnaire or the Picker Institute questionnaire for acute care hospitals. In addition to the comparison of response rates, completion time, mean number of missing items and mean ceiling effect, we targeted our comparison on patients and asked them to answer ten evaluation questions about the questionnaire they had just completed. RESULTS: 728 out of 1550 eligible patients (47%) participated in the study. Across questionnaires, response rates were similar (Saphora-Psy: 48.5%, Perceptions of Care: 49.9%, Picker: 43.4%; P = 0.08), average completion time was lowest for the Perceptions of Care questionnaire (minutes: Saphora-Psy: 17.7, Perceptions of Care: 13.7, Picker: 17.5; P = 0.005), the Saphora-Psy questionnaire had the largest mean proportion of missing responses (Saphora-Psy: 7.1%, Perceptions of Care: 2.8%, Picker: 4.0%; P < 0.001) and the Perceptions of Care questionnaire showed the highest ceiling effect (Saphora-Psy: 17.1%, Perceptions of Care: 41.9%, Picker: 36.3%; P < 0.001). There were no differences in the patients' evaluation of the questionnaires. CONCLUSION: Despite differences in the intended target population, content, lay-out and length of questionnaires, none appeared to be obviously better based on our comparison. All three presented advantages and drawbacks and could be used for the satisfaction evaluation of psychiatric inpatients. However, if comparison across medical services or hospitals is desired, using a generic questionnaire might be advantageous.

Assessment of construct validity of a virtual reality laparoscopy simulator.

BACKGROUND: The aim of this study was to assess whether virtual reality (VR) can discriminate between the skills of novices and intermediate-level laparoscopic surgical trainees (construct validity), and whether the simulator assessment correlates with an expert's evaluation of performance. METHODS: Three hundred and seven (307) participants of the 19th-22nd Davos International Gastrointestinal Surgery Workshops performed the clip-and-cut task on the Xitact LS 500 VR simulator (Xitact S.A., Morges, Switzerland). According to their previous experience in laparoscopic surgery, participants were assigned to the basic course (BC) or the intermediate course (IC). Objective performance parameters recorded by the simulator were compared to the standardized assessment by the course instructors during laparoscopic pelvitrainer and conventional surgery exercises. RESULTS: IC participants performed significantly better on the VR simulator than BC participants for the task completion time as well as the economy of movement of the right instrument, not the left instrument. Participants with maximum scores in the pelvitrainer cholecystectomy task performed the VR trial significantly faster, compared to those who scored less. In the conventional surgery task, a significant difference between those who scored the maximum and those who scored less was found not only for task completion time, but also for economy of movement of the right instrument. CONCLUSIONS: VR simulation provides a valid assessment of psychomotor skills and some basic aspects of spatial skills in laparoscopic surgery. Furthermore, VR allows discrimination between trainees with different levels of experience in laparoscopic surgery establishing construct validity for the Xitact LS 500 clip-and-cut task. Virtual reality may become the gold standard to assess and monitor surgical skills in laparoscopic surgery.

Use of Incentive/Disincentive Contracting to Mitigate Work Zone Traffic Impacts, 2012

Incentive/disincentive clauses (I/D) are designed to award payments to contractors if they complete work ahead of schedule and to deduct payments if they exceed the completion time. A previously unanswered question is, “Did the costs of the actual work zone impacts that were avoided justify the incentives paid?” This report answers that question affirmatively based on an evaluation of 20 I/D projects in Missouri from 2008 to 2011. Road user costs (RUC) were used to quantify work zone impacts and included travel delays, vehicle operating costs, and crash costs. These were computed using work zone traffic conditions for partial-closure projects and detour volumes and routes for full-closure projects. Conditions during construction were compared to after construction. Crash costs were computed using Highway Safety Manual methodology. Safety Performance Functions produced annual crash frequencies that were translated into crash cost savings. In considering an average project, the percentage of RUC savings was around 13% of the total contract amount, or $444,389 of $3,464,620. The net RUC savings produced was around $7.2 million after subtracting the approximately $1.7 million paid in incentives. In other words, for every dollar paid in incentives, approximately 5.3 dollars of RUC savings resulted. I/D provisions were very successful in saving RUC for projects with full-closure, projects in urban areas, and emergency projects. Rural, non-emergency projects successfully saved RUC but not at the same level as other projects. The I/D contracts were also compared to all Missouri Department of Transportation contracts for the same time period. The results show that I/D projects had a higher on-time completion percentage and a higher number of bids per call than average projects. But I/D projects resulted in 4.52% higher deviation from programmed costs and possibly more changes made after the award. A survey of state transportation departments and contractors showed that both agreed to the same issues that affect the success of I/D contracts. Legal analysis suggests that liquidated damages is preferred to disincentives, since enforceability of disincentives may be an issue. Overall, in terms of work zone impact mitigation, I/D contracts are very effective at a relatively low cost.

The Beneficial Effects of Motivational Self-Talk on Endurance Performance and Cognitive Function in the Heat

The role of psychological strategies on endurance performance and cognitive function in the heat is unclear. This thesis tested the effects of a two-week motivational self-talk (MST) intervention - specific to heat stress - on endurance capacity and cognitive function in the heat (35°C 50% RH). The study utilized a pre-test / post-test design testing endurance capacity using a time to exhaustion test (TTE) after exercise-induced hyperthermia. Cognitive function (e.g executive function) was tested at baseline in thermoneutral (22°C 30% RH), before (R1) and after the TTE (R2). MST led to a significant improvement (~30%) in TTE and significantly faster completion time with fewer errors made on executive function tasks at baseline and R2, but not in R1, while there were no differences in the control group. Overall, these results indicate that using a top-down regulation strategy consisting of self-contextualized MST can improve physical and cognitive performance in the heat.

Using ant colonies for solve the multiprocessor task graph scheduling

The problem of scheduling a parallel program presented by a weighted directed acyclic graph (DAG) to the set of homogeneous processors for minimizing the completion time of the program has been extensively studied as academic optimization problem which occurs in optimizing the execution time of parallel algorithm with parallel computer.In this paper, we propose an application of the Ant Colony Optimization (ACO) to a multiprocessor scheduling problem (MPSP). In the MPSP, no preemption is allowed and each operation demands a setup time on the machines. The problem seeks to compose a schedule that minimizes the total completion time.We therefore rely on heuristics to find solutions since solution methods are not feasible for most problems as such. This novel heuristic searching approach to the multiprocessor based on the ACO algorithm a collection of agents cooperate to effectively explore the search space.A computational experiment is conducted on a suit of benchmark application. By comparing our algorithm result obtained to that of previous heuristic algorithm, it is evince that the ACO algorithm exhibits competitive performance with small error ratio.