Minimizing total completion time on a batch processing machine with job families

We consider the problem of minimizing the total completion time on a single batch processing machine. The set of jobs to be scheduled can be partitioned into a number of families, where all jobs in the same family have the same processing time. The machine can process at most B jobs simultaneously as a batch, and the processing time of a batch is equal to the processing time of the longest job in the batch. We analyze that properties of an optimal schedule and develop a dynamic programming algorithm of polynomial time complexity when the number of job families is fixed. The research is motivated by the problem of scheduling burn-in ovens in the semiconductor industry

Minimizing total completion time on batch processing machines

We study the problem of minimizing total completion time on single and parallel batch processing machines. A batch processing machine is one which can process up to B jobs simultaneously. The processing time of a batch is equal to the largest processing time among all jobs in the batch. This problem is motivated by burn-in operations in the final testing stage of semiconductor manufacturing and is expected to occur in other production environments. We provide an exact solution procedure for the single-machine problem and heuristic algorithms for both single and parallel machine problems. While the exact algorithms have limited applicability due to high computational requirements, extensive experiments show that the heuristics are capable of consistently obtaining near-optimal solutions in very reasonable CPU times.

Minimizing total weighted completion time in a proportionate flow shop

We study the special case of the m machine flow shop problem in which the processing time of each operation of job j is equal to pj; this variant of the flow shop problem is known as the proportionate flow shop problem. We show that for any number of machines and for any regular performance criterion we can restrict our search for an optimal schedule to permutation schedules. Moreover, we show that the problem of minimizing total weighted completion time is solvable in O(n2) time. © 1998 John Wiley & Sons, Ltd.

Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval

In this note, we consider the scheduling problem of minimizing the sum of the weighted completion times on a single machine with one non-availability interval on the machine under the non-resumable scenario. Together with a recent 2-approximation algorithm designed by Kacem [I. Kacem, Approximation algorithm for the weighted flow-time minimization on a single machine with a fixed non-availability interval, Computers & Industrial Engineering 54 (2008) 401–410], this paper is the first successful attempt to develop a constant ratio approximation algorithm for this problem. We present two approaches to designing such an algorithm. Our best algorithm guarantees a worst-case performance ratio of 2+ε. © 2008 Elsevier B.V. All rights reserved.

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.

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.

Bi-criteria single machine scheduling problem with a learning effect: Aneja-Nair method to obtain the set of optimal sequences

In this paper, we consider the bi-criteria single machine scheduling problem of n jobs with a learning effect. The two objectives considered are the total completion time (TC) and total absolute differences in completion times (TADC). The objective is to find a sequence that performs well with respect to both the objectives: the total completion time and the total absolute differences in completion times. In an earlier study, a method of solving bi-criteria transportation problem is presented. In this paper, we use the methodology of solvin bi-criteria transportation problem, to our bi-criteria single machine scheduling problem with a learning effect, and obtain the set of optimal sequences,. Numerical examples are presented for illustrating the applicability and ease of understanding.

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.

Adult total wellness: group differences based on sitting time and physical activity level

Background An increasing body of evidence associates a high level of sitting time with poor health outcomes. The benefits of moderate to vigorous-intensity physical activities to various aspects of health are now well documented; however, individuals may engage in moderate-intensity physical activity for at least 30 minutes on five or more days of the week and still exhibit a high level of sitting time. This purpose of this study was to examine differences in total wellness among adults relative to high/low levels of sitting time combined with insufficient/sufficient physical activity (PA). The construct of total wellness incorporates a holistic approach to the body, mind and spirit components of life, an approach which may be more encompassing than some definitions of health. Methods Data were obtained from 226 adult respondents (27 ± 6 years), including 116 (51%) males and 110 (49%) females. Total PA and total sitting time were assessed with the International Physical Activity Questionnaire (IPAQ) (short-version). The Wellness Evaluation of Lifestyle Inventory was used to assess total wellness. An analysis of covariance (ANCOVA) was utilised to assess the effects of the sitting time/physical activity group on total wellness. A covariate was included to partial out the effects of age, sex and work status (student or employed). Cross-tabulations were used to show associations between the IPAQ derived high/low levels of sitting time with insufficient/sufficient PA and the three total wellness groups (i.e. high level of wellness, moderate wellness and wellness development needed). Results The majority of the participants were located in the high total sitting time and sufficient PA group. There were statistical differences among the IPAQ groups for total wellness [F (2,220) = 32.5 (p <0.001)]. A Chi-square test revealed a significant difference in the distribution of the IPAQ categories within the classification of wellness [χ2 (N = 226) = 54.5, p < .001]. One-hundred percent (100%) of participants who self-rated as high total sitting time/insufficient PA were found in the wellness development needed group. In contrast, 72% of participants who were located in the low total sitting time/sufficient PA group were situated in the moderate wellness group. Conclusion Many participants who meet the physical activity guidelines, in this sample, sit for longer periods of time than the median Australian sitting time. An understanding of the effects of the enhanced PA and reduced sitting time on total wellness can add to the development of public health initiatives. Keywords: IPAQ; The Wellness Evaluation of Lifestyle (WEL); Sedentary lifestyle

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.