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.

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.

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.

Development of a fast capillary electrophoresis method for the determination of propranolol-Total analysis time reduction strategies

The aim of this study was to develop a fast capillary electrophoresis method for the determination of propranolol in pharmaceutical preparations. In the method development the pH and constituents of the background electrolyte were selected using the effective mobility versus pH curves. Benzylamine was used as the internal standard. The background electrolyte was composed of 60 mmol L(-1) tris(hydroxymethyl)aminomethane and 30 mmol L(-1) 2-hydroxyisobutyric acid,at pH 8.1. Separation was conducted in a fused-silica capillary (32 cm total length and 8.5 cm effective length, 50 mu m I.D.) with a short-end injection configuration and direct UV detection at 214 nm. The run time was only 14 s. Three different strategies were studied in order to develop a fast CE method with low total analysis time for propranolol analysis: low flush time (Lflush) 35 runs/h, without flush (Wflush) 52 runs/h, and Invert (switched polarity) 45 runs/h. Since the three strategies developed are statistically equivalent, Mush was selected due to the higher analytical frequency in comparison with the other methods. A few figures of merit of the proposed method include: good linearity (R(2) > 0.9999); limit of detection of 0.5 mg L(-1): inter-day precision better than 1.03% (n = 9) and recovery in the range of 95.1-104.5%. (C) 2009 Elsevier B.V. All rights reserved.

Effects of fixed night shift work on 24 hour blood pressure regulation, state anxiety levels and total sleep time

Nearly 22 million Americans operate as shift workers, and shift work has been linked to the development of cardiovascular disease (CVD). This study is aimed at identifying pivotal risk factors of CVD by assessing 24 hour ambulatory blood pressure, state anxiety levels and sleep patterns in 12 hour fixed shift workers. We hypothesized that night shift work would negatively affect blood pressure regulation, anxiety levels and sleep patterns. A total of 28 subjects (ages 22-60) were divided into two groups: 12 hour fixed night shift workers (n=15) and 12 hour fixed day shift workers (n=13). 24 hour ambulatory blood pressure measurements (Space Labs 90207) were taken twice: once during a regular work day and once on a non-work day. State anxiety levels were assessed on both test days using the Speilberger’s State Trait Anxiety Inventory. Total sleep time (TST) was determined using self recorded sleep diary. Night shift workers demonstrated increases in 24 hour systolic (122 ± 2 to 126 ± 2 mmHg, P=0.012); diastolic (75 ± 1 to 79 ± 2 mmHg, P=0.001); and mean arterial pressures (90 ± 2 to 94 ± 2mmHg, P<0.001) during work days compared to off days. In contrast, 24 hour blood pressures were similar during work and off days in day shift workers. Night shift workers reported less TST on work days versus off days (345 ± 16 vs. 552 ± 30 min; P<0.001), whereas day shift workers reported similar TST during work and off days (475 ± 16 minutes to 437 ± 20 minutes; P=0.231). State anxiety scores did not differ between the groups or testing days (time*group interaction P=0.248), suggesting increased 24 hour blood pressure during night shift work is related to decreased TST, not short term anxiety. Our findings suggest that fixed night shift work causes disruption of the normal sleep-wake cycle negatively affecting acute blood pressure regulation, which may increase the long-term risk for CVD.

Sequencing Jobs with Uncertain Processing Times and Minimizing the Weighted Total Flow Time

We consider an uncertain version of the scheduling problem to sequence set of jobs J on a single machine with minimizing the weighted total flow time, provided that processing time of a job can take on any real value from the given closed interval. It is assumed that job processing time is unknown random variable before the actual occurrence of this time, where probability distribution of such a variable between the given lower and upper bounds is unknown before scheduling. We develop the dominance relations on a set of jobs J. The necessary and sufficient conditions for a job domination may be tested in polynomial time of the number n = |J| of jobs. If there is no a domination within some subset of set J, heuristic procedure to minimize the weighted total flow time is used for sequencing the jobs from such a subset. The computational experiments for randomly generated single-machine scheduling problems with n ≤ 700 show that the developed dominance relations are quite helpful in minimizing the weighted total flow time of n jobs with uncertain processing times.

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.

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.

Total and segmental colonic transit time in constipated patients with Chagas’ disease without megaesophagus or megacolon

Manometric and pharmacological tests have shown that motor abnormalities may occur in the non-dilated colons of chagasic patients. In order to investigate the presence of abnormalities of colonic function in constipated patients with Chagas’ disease (ChC) without megaesophagus or megacolon, studies of total and segmental colonic transit time with radiopaque markers were performed on 15 ChC patients, 27 healthy volunteers and 17 patients with idiopathic constipation (IC). The values obtained for the control group were similar to those reported in the literature (total colonic time: 34.1 ± 15.6 h; right colon: 9.9 ± 7.3 h; left colon: 10.8 ± 10 h, and rectosigmoid: 12.6 ± 9.9 h). Colonic transit time data permitted us to divide both IC and ChC patients into groups with normal transit and those with slow colonic transit. Colonic inertia was detected in 41% of IC patients and in 13% of ChC patients; left colon isolated stasis (hindgut dysfunction) was detected in 12% of IC patients and 7% of ChC patients, and outlet obstruction was detected in 6% of IC patients and 7% of ChC patients. There were no significant differences in total or segmental colonic transit times between slow transit IC and slow transit ChC patients. In conclusion, an impairment of colonic motility was detected in about 30% of constipated patients with Chagas’ disease without megaesophagus or megacolon. This subgroup of patients presented no distinctive clinical feature or pattern of colonic dysmotility when compared to patients with slow transit idiopathic constipation.

The influence of tourniquet use and operative time on the incidence of deep vein thrombosis in total knee arthroplasty

OBJECTIVE: To evaluate the association between tourniquet and total operative time during total knee arthroplasty and the occurrence of deep vein thrombosis. METHODS: Seventy-eight consecutive patients from our institution underwent cemented total knee arthroplasty for degenerative knee disorders. The pneumatic tourniquet time and total operative time were recorded in minutes. Four categories were established for total tourniquet time: <60, 61 to 90, 91 to 120, and >120 minutes. Three categories were defined for operative time: <120, 121 to 150, and >150 minutes. Between 7 and 12 days after surgery, the patients underwent ascending venography to evaluate the presence of distal or proximal deep vein thrombosis. We evaluated the association between the tourniquet time and total operative time and the occurrence of deep vein thrombosis after total knee arthroplasty. RESULTS: In total, 33 cases (42.3%) were positive for deep vein thrombosis; 13 (16.7%) cases involved the proximal type. We found no statistically significant difference in tourniquet time or operative time between patients with or without deep vein thrombosis. We did observe a higher frequency of proximal deep vein thrombosis in patients who underwent surgery lasting longer than 120 minutes. The mean total operative time was also higher in patients with proximal deep vein thrombosis. The tourniquet time did not significantly differ in these patients. CONCLUSION: We concluded that surgery lasting longer than 120 minutes increases the risk of proximal deep vein thrombosis.

Obesity Decreases Time to Claudication and Delays Post-Exercise Hemodynamic Recovery in Elderly Peripheral Arterial Disease Patients

Background: Although obesity is usually observed in peripheral arterial disease (PAD) patients, the effects of the association between these diseases on walking capacity are not well documented. Objective: The main objectives of this study were to determine the effects of obesity on exercise tolerance and post-exercise hemodynamic recovery in elderly PAD patients. Methods: 46 patients with stable symptoms of intermittent claudication were classified according to their body mass index (BMI) into normal group (NOR) = BMI < 28.0 and obese or in risk of obesity group (OBE) = BMI >= 28.0. All patients performed a progressive graded treadmill test. During exercise, ventilatory responses were evaluated and pre- and post-exercise ankle and arm blood pressures were measured. Results: Exercise tolerance and oxygen consumption at total walking time were similar between OBE and NOR. However, OBE showed a lower claudication time (309 +/- 151 vs. 459 +/- 272 s, p = 0.02) with a similar oxygen consumption at this time. In addition, OBE presented a longer time for ankle brachial index recovery after exercise (7.8 +/- 2.8 vs. 6.3 +/- 2.6 min, p = 0.02). Conclusion: Obesity in elderly PAD patients decreased time to claudication, and delayed post-exercise hemodynamic recovery. These results suggest that muscle metabolic demand, and not total workload, is responsible for the start of the claudication and maximal exercise tolerance in PAD patients. Moreover, claudication duration might be responsible for the time needed to a complete hemodynamic recovery after exercise. Copyright (c) 2008 S. Karger AG, Basel

Multiple cranial burr holes as an alternative treatment for total scalp avulsion

Total scalp avulsion is a devastating injury in clinical practice. It often occurs in female adults, being rare in children. The standard treatment for scalp avulsion is microsurgical replantation, when feasible. Coverage becomes a major problem when replantation fails or is contraindicated, resulting in significant morbidity and requiring multiple procedures. In this article, in addition to reviewing the literature, we report a historical method for obtaining skin coverage after failure of replantation. The authors report a case of a 10-year-old girl who had her scalp totally avulsed by an agricultural machine, including her right auricle. Microsurgery scalp replantation was attempted immediately after fluid resuscitation. The surgery failed probably due to the long time interval between trauma and surgery, which resulted in total ischemic time of 11 h and consequently made vascular microanastomosis impracticable. Multiple trephination of the calvarium was performed in order to expose the diploe. After 4 weeks, granulation tissue from the holes began to cover the defect, allowing the formation of a vascular bed suitable for skin grafting. Total scalp avulsion in children is seldom reported in the literature. Therefore, its management is both difficult and challenging. The exposure of the diploe with multiple burr holes is a safe and effective method for treating this injury. It may be considered, along with skin grafting, a good therapeutic alternative to be used when microsurgical replantation fails or is not feasible.