Scheduling batches with sequential job processing for two-machine flow and open shops

In this paper, we study a problem of scheduling and batching on two machines in a flow-shop and open-shop environment. Each machine processes operations in batches, and the processing time of a batch is the sum of the processing times of the operations in that batch. A setup time, which depends only on the machine, is required before a batch is processed on a machine, and all jobs in a batch remain at the machine until the entire batch is processed. The aim is to make batching and sequencing decisions, which specify a partition of the jobs into batches on each machine, and a processing order of the batches on each machine, respectively, so that the makespan is minimized. The flow-shop problem is shown to be strongly NP-hard. We demonstrate that there is an optimal solution with the same batches on the two machines; we refer to these as consistent batches. A heuristic is developed that selects the best schedule among several with one, two, or three consistent batches, and is shown to have a worst-case performance ratio of 4/3. For the open-shop, we show that the problem is NP-hard in the ordinary sense. By proving the existence of an optimal solution with one, two or three consistent batches, a close relationship is established with the problem of scheduling two or three identical parallel machines to minimize the makespan. This allows a pseudo-polynomial algorithm to be derived, and various heuristic methods to be suggested.

Three-machine shop scheduling with partially ordered processing routes

This paper considers the problem of sequencing n jobs in a three-machine shop with the objective of minimising the maximum completion time. The shop consists of three machines, M1,M2 and M_{3}. A job is first processed on M1 and then is assigned either the route (M2,M_{3}) or the route (M_{3},M2). Thus, for our model the processing route is given by a partial order of machines, as opposed to the linear order of machines for a job shop, or to an arbitrary sequence of machines for an open shop. The main result is on O(nlog n) time heuristic, which generates a schedule with the makespan that is at most 5/3 times the optimum value.

Scheduling three-operation jobs in a two-machine flow shop to minimize makespan

This paper considers a variant of the classical problem of minimizing makespan in a two-machine flow shop. In this variant, each job has three operations, where the first operation must be performed on the first machine, the second operation can be performed on either machine but cannot be preempted, and the third operation must be performed on the second machine. The NP-hard nature of the problem motivates the design and analysis of approximation algorithms. It is shown that a schedule in which the operations are sequenced arbitrarily, but without inserted machine idle time, has a worst-case performance ratio of 2. Also, an algorithm that constructs four schedules and selects the best is shown to have a worst-case performance ratio of 3/2. A polynomial time approximation scheme (PTAS) is also presented.

Two-Machine Shop Scheduling with an Uncapacitated Interstage Transporter

In this paper we study the two-machine flow shop and open shop problems to minimize the makespan with a single interstage transporter that may carry any number of jobs between the machines at a time. For each of these problems we present a best possible approximation algorithm within a class of schedules with at most two shipments. As a by-product of this research, for the problem of minimizing the makespan on parallel identical machines we analyze the ratio of the makespan for a non-preemptive schedule over the makespan of a preemptive schedule.

Two-machine shop scheduling: Compromise between flexibility and makespan value

In this paper, we consider the problem of providing flexibility to solutions of two-machine shop scheduling problems. We use the concept of group-scheduling to characterize a whole set of schedules so as to provide more choice to the decision-maker at any decision point. A group-schedule is a sequence of groups of permutable operations defined on each machine where each group is such that any permutation of the operations inside the group leads to a feasible schedule. Flexibility of a solution and its makespan are often conflicting, thus we search for a compromise between a low number of groups and a small value of makespan. We resolve the complexity status of the relevant problems for the two-machine flow shop, job shop and open shop. A number of approximation algorithms are developed and their worst-case performance is analyzed. For the flow shop, an effective heuristic algorithm is proposed and the results of computational experiments are reported.

An improved approximation algorithm for the two-machine flow shop scheduling problem with an interstage transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables

An approximation algorithm for the two-machine flow shop with a single transporter

We study the two-machine flow shop problem with an uncapacitated interstage transporter. The jobs have to be split into batches, and upon completion on the first machine, each batch has to be shipped to the second machine by a transporter. The best known heuristic for the problem is a –approximation algorithm that outputs a two-shipment schedule. We design a –approximation algorithm that finds schedules with at most three shipments, and this ratio cannot be improved, unless schedules with more shipments are created. This improvement is achieved due to a thorough analysis of schedules with two and three shipments by means of linear programming. We formulate problems of finding an optimal schedule with two or three shipments as integer linear programs and develop strongly polynomial algorithms that find solutions to their continuous relaxations with a small number of fractional variables.

Schedules with due-date assignment and position-dependent processing times

Single machine scheduling problems are considered, in which the processing of jobs depend on positions of the jobs in a schedule and the due-dates are assigned either according to the CON rule (a due-date common to all jobs is chosen) or according to the SLK rule (the due-dates are computed by increasing the actual processing times of each job by a slack, common to all jobs). Polynomial-time dynamic programming algorithms are proposed for the problems with the objective functions that include the cost of assigning the due-dates, the total cost of disgarded jobs (which are not scheduled) and, possibly, the total earliness of the scheduled jobs.

Chronotype, sleep quality and sleep duration in adult distance education: Not related to study progress

Research in traditional education shows chronotype, sleep duration and sleep quality to be related to learning performance. Research in adult students participating in distance education (DE) is scarce. This study aims to provide knowledge on these relationships in this educational setting. In an observational longitudinal study, chronotype, sleep duration (i.e., for work and free days separately) and sleep quality of 894 students were analyzed in a multiple regression analyses. Students provided information on sleep-relatedmeasures and important covariates at the start of their study and study progress was evaluated after 14 months (i.e., the number of successfully completed modules). In linewith previous research, chronotype did not predict study progress. Further, sleep duration did not predict study progress, neither as a linear nor as a polynomial term. Third, sleep quality did not predict study progress. Concluding, these results are in linewith previous research that DE provides a solution to the asynchrony problem. Findings regarding sleep duration and sleep quality are new and unexpected, asking for attention and further research. Despite the study's observational nature, findings suggest that students participating in DE may benefit from this type of education as the asynchrony problem appears not to apply here, as students can choose their own study schedule.

Behavioural and histopathological analyses of ibuprofen treatment on the effect of aggregated AB (1-42) injections in the rat

It has been suggested that inflammatory processes may play a role in the development of Alzheimerâ??s disease (AD), and that nonsteroidal anti-inflammatory drug treatments may provide protection against the onset of AD. In the current study male Wistar rats were trained in two-lever operant chambers under an alternating lever cyclic-ratio ratio (ALCR) schedule. When responding showed no trends, subjects were divided into groups. One group was bilaterally injected into the CA3 area of the hippocampus with 5 μl of aggregated β-amyloid (Aβ) suspension, and one group was bilaterally injected into the CA3 area of the hippocampus with 5 μl of sterile saline. Subgroups were treated twice daily with 0.1 ml (40 mg/kg) ibuprofen administered orally. The results indicated that chronic administration of ibuprofen protected against detrimental behavioural effects following aggregated Aβ injections. Withdrawal of ibuprofen treatment from aggregated Aβ-injected subjects produced a decline in behavioural performance to the level of the non-treated aggregated Aβ-injected group. Ibuprofen treatment reduced the numbers of reactive astrocytes following aggregated Aβ injection, and withdrawal of ibuprofen resulted in an increase of reactive astrocytes. These results suggest that induced inflammatory processes may play a role in AD, and that ibuprofen treatment may protect against some of the symptoms seen in AD.

An operant determination of the behavioural mechanism of benzodiazepine enhancement of food intake

Rationale A recent review paper by Cooper (Appetite 44:133–150, 2005) has pointed out that a role for benzodiazepines as appetite stimulants has been largely overlooked. Cooper’s review cited several studies that suggested the putative mechanism of enhancement of food intake after benzodiazepine administration might involve increasing the perceived pleasantness of food (palatability). Objectives The present study examined the behavioral mechanism of increased food intake after benzodiazepine administration. Materials and methods The cyclic-ratio operant schedule has been proposed as a useful behavioral assay for differentiating palatability from regulatory effects on food intake (Ettinger and Staddon, Physiol Behav 29:455–458, 1982 and Behav Neurosci 97:639–653, 1983). The current study employed the cyclic-ratio schedule to determine whether the effects on food intake of chlordiazepoxide (CDP) (5.0 mg/kg), sodium pentobarbital (5.0 mg/kg), and picrotoxin (1.0 mg/kg) were mediated through palatability or regulatory processes. Results The results of this study show that both the benzodiazepine CDP and the barbiturate sodium pentobarbital increased food intake in a manner similar to increasing the palatability of the ingestant, and picrotoxin decreased food intake in a manner similar to decreasing the palatability of the ingestant. Conclusions These results suggest that the food intake enhancement properties of benzodiazepines are mediated through a mechanism affecting perceived palatability.

Dynamic Job Scheduling on the Grid Environment using the Great Deluge Algorithm

The utilization of the computational Grid processor network has become a common method for researchers and scientists without access to local processor clusters to avail of the benefits of parallel processing for compute-intensive applications. As a result, this demand requires effective and efficient dynamic allocation of available resources. Although static scheduling and allocation techniques have proved effective, the dynamic nature of the Grid requires innovative techniques for reacting to change and maintaining stability for users. The dynamic scheduling process requires quite powerful optimization techniques, which can themselves lack the performance required in reaction time for achieving an effective schedule solution. Often there is a trade-off between solution quality and speed in achieving a solution. This paper presents an extension of a technique used in optimization and scheduling which can provide the means of achieving this balance and improves on similar approaches currently published.

Stochastic protein folding simulation in the three-dimensional HP-model

We present results from three-dimensional protein folding simulations in the HP-model on ten benchmark problems. The simulations are executed by a simulated annealing-based algorithm with a time-dependent cooling schedule. The neighbourhood relation is determined by the pull-move set. The results provide experimental evidence that the maximum depth D of local minima of the underlying energy landscape can be upper bounded by D < n(2/3). The local search procedure employs the stopping criterion (In/delta)(D/gamma) where m is an estimation of the average number of neighbouring conformations, gamma relates to the mean of non-zero differences of the objective function for neighbouring conformations, and 1-delta is the confidence that a minimum conformation has been found. The bound complies with the results obtained for the ten benchmark problems. (c) 2008 Elsevier Ltd. All rights reserved.

Atomic layer deposition of hafnium oxide dielectrics on silicon and germanium substrates

Hafnium oxide films have been deposited at 250 °C on silicon and germanium substrates by atomic layer deposition (ALD), using tetrakis-ethylmethylamino hafnium (TEMAH) and water vapour as precursors in a modified Oxford Instruments PECVD system. Self-limiting monolayer growth has been verified, characterised by a growth rate of 0.082 nm/ cycle. Layer uniformity is approximately within ±1% of the mean value. MOS capacitors have been fabricated by evaporating aluminium electrodes. CV analysis has been used to determine the bulk and interface properties of the HfO 2, and their dependence on pre-clean schedule, deposition conditions and post-deposition annealing. The dielectric constant of the HfO 2 is typically 18. On silicon, best results are obtained when the HfO 2 is deposited on a chemically oxidised hydrophilic surface. On germanium, best results are obtained when the substrate is nitrided before HfO 2 deposition, using an in-situ nitrogen plasma treatment. © Springer Science+Business Media, LLC 2007.

Dual adaptation to two opposing visuomotor rotations when each is associated with different regions of workspace

Studies examining dual adaptation to opposing novel environments have yielded contradictory results, with previous evidence supporting both successful dual adaptation and interference leading to poorer adaptive performance. Whether or not interference is observed during dual adaptation appears to be dependent on the method used to allow the performer of the task to distinguish between two novel environments. This experiment tested if colour cues, a separation in workspace, and presentation schedule, could be used to distinguish between two opposing visuomotor rotations and enable dual adaptation. Through the use of a purpose designed manipulandum, each visuomotor rotation was either presented in the same region of workspace and associated with colour cues (Group 1), different regions of workspace in addition to colour cues (Groups 2 and 3) or different regions of workspace only (Groups 4 and 5). We also assessed the effectiveness of the workspace separation with both randomised and alternating presentation schedules (Groups 4 and 5). The results indicated that colour cues were not effective at enabling dual adaptation when each of the visuomotor rotations was associated with the same region of workspace. When associated with different regions of workspace, however, dual adaptation to the opposing rotations was successful regardless of whether colour cues were present or the type of presentation schedule.