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.

Une heuristique de recherche à voisinage variable pour le problème du voyageur de commerce avec fenêtres de temps

Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois.

Une heuristique de recherche à voisinage variable pour le problème du voyageur de commerce avec fenêtres de temps

Nous adaptons une heuristique de recherche à voisinage variable pour traiter le problème du voyageur de commerce avec fenêtres de temps (TSPTW) lorsque l'objectif est la minimisation du temps d'arrivée au dépôt de destination. Nous utilisons des méthodes efficientes pour la vérification de la réalisabilité et de la rentabilité d'un mouvement. Nous explorons les voisinages dans des ordres permettant de réduire l'espace de recherche. La méthode résultante est compétitive avec l'état de l'art. Nous améliorons les meilleures solutions connues pour deux classes d'instances et nous fournissons les résultats de plusieurs instances du TSPTW pour la première fois.

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.

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.

A new evolutionary clustering search for a no-wait flow shop problem with set-up times

This paper addresses the m-machine no-wait flow shop problem where the set-up time of a job is separated from its processing time. The performance measure considered is the total flowtime. A new hybrid metaheuristic Genetic Algorithm-Cluster Search is proposed to solve the scheduling problem. The performance of the proposed method is evaluated and the results are compared with the best method reported in the literature. Experimental tests show superiority of the new method for the test problems set, regarding the solution quality. (c) 2012 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.

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.