Search

Fluorescence microscopy is an excellent tool to gain knowledge on cellular structures and biochemical processes. Stimulated emission depletion (STED) microscopy provides a resolution in the range of a few ten nanometers at relatively fast data acquisition. As cellular structures can be oriented in any direction, it is of great benefit if the microscope exhibits an isotropic resolution. Here, we present an isoSTED microscope that utilizes water-immersion objective lenses and enables imaging of cellular structures with an isotropic resolution of better than 60 nm in living samples at room temperature and without CO2 supply or another pH control. This corresponds to a reduction of the focal volume by far more than two orders of magnitude as compared to confocal microscopy. The imaging speed is in the range of 0.8 s/μm3. Since fluorescence signal can only be detected from a diffraction-limited volume, a background signal is inevitably observed at resolutions well beyond the diffraction limit. Therefore, we additionally present a method which allows to identify this unspecific background signal and to remove it from the image.

NP-hard scheduling problems with the criterion of minimizing the maximum penalty, e.g. maximum lateness, are considered. For such problems, a metric which delivers an upper bound on the absolute error of the objective function value is introduced. Taking the given instance of some problem and using the introduced metric, the nearest instance is determined for which a polynomial or pseudo-polynomial algorithm is known. A schedule is constructed for this determined instance which is then applied to the original instance. It is shown how this approach can be applied to different scheduling problems.

This paper presents a comprehensive and novel mathematical model to address the scheduling problem of inpatient surgeries. The interaction quality and compatibility level of surgical team members can have a significant impact on the quality and safety of a surgery. The first aim of this paper is to incorporate the decision-making styles of the surgical team members (as a personality indicator) in an operating room scheduling problem to improve the compatibility level within the surgical teams. The second aim of this paper is to provide a more effective and realistic solution for the problem by considering several practical factors. These factors include the availability of material resources (i.e., operating rooms, post-anesthesia beds, and equipment), priorities of patients, and availability, skills, and competencies of the surgical personnel. To cope with the computational complexity of the problem, two metaheuristics (i.e., NSGA-II and MOPSO) are developed to find Pareto solutions. Furthermore, the PROMETHEE-II method is used to select the best among the obtained Pareto solutions. Finally, a real case study is provided to show the applicability of the developed approach.

This paper presents a bi-objective MILP model for the vehicle routing and scheduling problem with cross-docking for perishable products. It is demonstrated that considering merely one objective sacrifices the other one and that the L1 metric method makes a suitable trade-off. Two robust models are developed when the travel time of the outbound vehicles and the freshness-life of the products are uncertain. The results show that the effect of the appearing uncertainty in the travel time on the deterioration of the objectives is higher than the effect of the freshness-life of the products, and using the proposed model, the freshness of the delivered products increases by 74.14% on average without increasing the distribution cost, which can decrease the waste.

This paper deals with the scheduling problem of minimizing the makespan on two identical parallel machines with molds as resource constraints. Two or more jobs with the same mold requirement cannot be processed on the same or different machines at the same time. While quite common in practice, like in wafer fabrication, such problems have not received much attention in the literature. Since this problem is NP-hard, a mathematical model for solving it is derived and tested. Moreover, three simple, fast, and effective heuristics are proposed with a worst-case performance ratio of 3/2. Computational results show that the proposed heuristics can efficiently obtain good solutions for problem instances containing a large number of jobs. In addition, the use of these proposed algorithms as initial solution can improve the performance of metaheuristics. Furthermore, the solutions obtained by these proposed heuristics can be improved by metaheuristics.

A set of jobs has to be processed on a single machine without preemptions of a job. The exact value of the job processing time (duration) is unknown until the completion of the job. Lower and upper bounds on the job duration are known before scheduling. The problem is to minimize total completion time of the given jobs. We apply a stability approach to this scheduling problem and introduce an optimality region for a job permutation as an optimality measure of the schedule. We investigate properties of the optimality region and derive O(n) algorithms for calculating the relative perimeter of the optimality region (the sum of the relative optimality sets of the n jobs) for a fixed job permutation. We present computational results for a comparison of the relative perimeters of the optimality regions for the mid-point permutations, the lower-bound permutations, the upper-bound permutations and the permutations having the largest optimality box.

In the manufacturing of highly customized goods and the operation of automatic logistics systems, efficient schedules constitute an everyday challenge. Therefore, the job shop problem is established as a standard model in scheduling research. While classical variants are well studied, the involvement of practically relevant conditions, such as the absence of intermediate buffers and customer-oriented optimization criteria, shows a lack of theoretical understanding. This work provides a study in this research direction by examining the applicability of a scheduling-tailored heuristic search method to the blocking job shop problem with total tardiness minimization. Permutation-based encodings are used to represent a schedule. Appearing redundancy and feasibility issues are discussed. Two well-known neighborhood structures for sequencing problems are applied and an advanced repairing technique to construct feasible blocking job shop schedules is proposed. The computational results obtained by embedding the components in a simulated annealing framework highlight advantages of the heuristic solution approach against existing general-purpose methods.

In this paper, we consider some special resource-constrained scheduling problems, which occur e.g. in production or in computer science. We consider the minimization of the makespan as well as total tardiness. Some complexity and approximability results are given as well as relationships to other scheduling problems.

A graph is well-indumatched if all its maximal induced matchings are of the same size. We first prove that recognizing whether a graph is well-indumatched is a co-NP-complete problem even for ( 2 P 5 , K 1 , 5 ) -free graphs. We then show that decision problems Independent Dominating Set , Independent Set , and Dominating Set are NP-complete for the class of well-indumatched graphs. We also show that this class is a co-indumatching hereditary class, i.e., it is closed under deleting the end-vertices of an induced matching along with their neighborhoods, and we characterize well-indumatched graphs in terms of forbidden co-indumatching subgraphs. We prove that recognizing a co-indumatching subgraph is an NP-complete problem. We introduce a perfectly well-indumatched graph, in which every induced subgraph is well-indumatched, and characterize the class of these graphs in terms of forbidden induced subgraphs. Finally, we show that the weighted versions of problems Independent Dominating Set and Independent Set can be solved in polynomial time for perfectly well-indumatched graphs, but problem Dominating Set is NP-complete.

In this paper, a generalized formulation of a classical single machine scheduling problem is considered. A set of n jobs characterized by their release dates, deadlines and a start time-dependent processing time function p(t) has to be processed on a single machine. The objective is to find a Pareto-optimal set of schedules with respect to the criteria ϕmax and makespan, where ϕmax is a non-decreasing function depending on the completion times of the jobs. We present an approach that allows to find an optimal schedule with respect to different scheduling criteria, such as the minimization of makespan, lateness or weighted lateness, tardiness and weighted tardiness etc. in time polynomially depending on the number of jobs. The complexity of the presented algorithm is O(n3 max{log n, H, P}), where H and P are the complexity of calculating ϕj(t) and p(t), respectively.

New high-resolution multibeam bathymetry and sub-bottom profile datasets from Fingerdjupet are used for the first detailed geomorphological mapping of the seafloor in this area. The mapped landforms provide evidence for a palaeo-ice stream flowing in a southeasterly direction from Spitsbergenbanken into Fingerdjupet, merging with Bjornoyrenna ice stream, and confirm a theorised palaeo-ice divide located along the bank. The combined landform records and acoustic stratigraphy allow a detailed reconstruction of the glacial dynamics during the last deglaciation. The withdrawal of the Fingerdjupet ice stream from Bjornoyrenna was characterised by rapid retreat, punctuated by periods of stable ice marginal conditions. Five to six major ice margin stillstands and/or readvances associated with the last deglaciation are identified in the seafloor record and acoustic stratigraphy. During these events, large grounding zone wedges were deposited at the ice stream margin. The seabed geomorphology indicates that ice stream dynamics changed as the ice stream retreated from the trough onto the shallower bank. Here, numerous retreat moraines indicate that a grounded ice margin retreated slowly, with several minor stillstands, towards north-northwest. Several controls and/or drivers on the style of ice flow and retreat have been suggested, including catchment size reduction, sea level rise, bedrock topography, drawdown of bank ice and/or migration of the main ice divide over the bank.

During the welding process, the microstructure of the base material changes locally that leads to altering mechanical properties in the weld and the neighboring areas, Heat Affected Zone (HAZ). The constitution of the HAZs also varies spatially as a result of different temperature gradients during heating and cooling cycles. Consequently, the macroscopic material behavior of the HAZ also varies spatially as well and therefore the determination of the mechanical behavior of the welded connection is very challenging. In this study, a hierarchical multiscale approach is presented and applied in order to characterize the material behavior of the Heat Affected Zone (HAZ) in welded connections. First, the metallurgical constituents in particular areas of HAZ have been identified experimentally. Next, several representative volume elements (RVEs) have been constructed using microscopic images. Then employing the computational homogenization methods, the stress–strain curves representing the macroscopic material behavior in respective points of the HAZ have been calculated. Meanwhile, some miniature tensile tests have been performed to experimentally identify the stress–strain behavior in the HAZ. Finally, the numerically calculated stress–strain curves are compared with the measured experimental data and they show a good agreement. The comparison of the results depicts that the proposed multiscale approach is suitable for the characterization of the material properties in welded connections or in general for materials with specially varying microstructures.

In this paper, we consider the scheduling problem of minimizing total weighted job completion time when a set of jobs has to be processed on a set of m parallel identical machines with a common server. We propose an approximation algorithm with a worst-case ratio of 3 1 m . This result improves an existing (5 1 m ) - approximation algorithm given by Wang and Cheng (2001).

We consider the problem of scheduling jobs with given release times and due dates on a single machine to minimize the maximum job lateness. It is NP-hard and remains such if the maximal job processing time is unrestricted and there is no constant bound on the difference between any job release times. We give a polynomial-time solution of the version in which the maximal job processing time and the differences between the job release times are bounded by a constant, which are restrictions that naturally arise in practice. Our algorithm reveals the inherent structure of the problem and also gives conditions when it is able to find an optimal solution unconditionally.

A learning stage of scheduling tends to produce knowledge about a benchmark of priority dispatching rules which allows a scheduler to improve the solution quality for a set of similar job-shop problems. Once trained on the sample job-shop problems (usually with small sizes), the adaptive algorithm solves a similar job-shop problem (with a moderate size or a large size) better than heuristics used as a benchmark at the learning stage of scheduling. Our adaptive algorithm does not guarantee to perform as an exact algorithm or better than a more sophisticated heuristic algorithm (like e.g. the shifting bottleneck one) which need a large running time. For an adaptive algorithm with a learning stage, the job-shop scheduling problem is modeled via a weighted mixed (disjunctive) graph with the conflict resolution strategy used for finding an appropriate schedule.

International audience; For five single machine total tardiness problems a fully polynomial-time approximation scheme (FPTAS) based on a graphical algorithm is presented. The FPTAS has the best running time among the known approximation schemes for these problems.

We consider the following problem. A set of non-preemptable jobs has to be scheduled on two identical parallel machines such that the makespan is minimized. Before processing, each job must be loaded on a machine, which takes a given setup time. All these setups have to be done by a single server which can handle at most one job at a time. For this problem, we propose three mixed integer linear programming formulations. We compare our results with known heuristics.

In structural engineering models are used to represent the behavior of structures close to reality and subsequently to allow a safe design. Scientific investigations, as well as experiences from the daily practice are the basis for the view of the relationship between reality and model. This paper deals with the evaluation of coupled numerical models without a calibration using experimental data as an approximation of physical reality. Here, the focus is on developing a new evaluation method for determining the prognosis quality of complex engineering models. The prognosis quality of coupled models is evaluated using a two-stage model quality analysis which is based on a multicriterial evaluation method. In particular, the probabilistic criteria have a high significance during the evaluation process. Therefore, methods for predicting the uncertainty, sensitivity, robustness and reliability are proposed. Furthermore, aleatoric and epistemic uncertainties are to be taken into consideration when comparing different engineering models with different levels of complexity. For this purpose, different approaches for predicting these uncertainties are implemented. Finally, the model qualities for a complex structure are exemplarily evaluated using the model quality analysis developed.

We consider the problem of scheduling jobs with release times and due dates on a single machine to minimize the maximal job lateness. This problem is NP-hard, and its version when the job processing times are restricted to p, 2p, 3p, 4p, …, for an integer p, is also NP-hard. We consider the case when the maximal job processing time is kp, for any constant k, and propose its polynomial-time solution. We easily establish that the version of this problem with unrestricted k is NP-hard. Moreover, it is strongly NP-hard if p has no exponential-time dependence on the maximal job due date. From a practical point of view, this is a realistic assumption.

In this paper, we present a modification of dynamic programming algorithms (DPA), which we denote as graphical algorithms (GrA). For some single machine scheduling problems, it is shown that the time complexity of the GrA is less than the time complexity of the standard DPA. Moreover, the average running time of the GrA is often essentially smaller. A GrA can also solve large-scale instances and instances, where the parameters are not integer. For some problems, GrA has a polynomial time complexity in contrast to a pseudo-polynomial complexity of a DPA.

We present an approach based on a two-stage filtration of the set of feasible solutions for the multiprocessor job-shop scheduling problem. On the first stage we use extensive dominance relations, whereas on the second stage we use lower bounds. We show that several lower bounds can efficiently be obtained and implemented.

For an assembly line, it is necessary to minimize the cycle time for processing a partially ordered set of operations V = {1, …, n} on a set of m linearly ordered working stations. The number m of stations and the initial processing times t = (t1, …, tn) of the operations V are given. However, for a subset V ⊆ V of the manual operations j ∈ V, it is impossible to fix the processing times tj for the whole life cycle of the assembly line. On the other hand, for each automated operation i ∈ V \ V, the processing time ti is fixed. We investigate the stability of an optimal line balance b0 of the assembly line with respect to variations of the processing times tj, j ∈ V. It is shown how to calculate the stability radius ρb0 (t) of an optimal line balance b0, i.e., the maximal value of simultaneous independent variations of the processing times of the manual operations with keeping the optimality of the line balance b0. We survey known results on the stability radius of an optimal line balance for a dual problem which is to minimize the number m of the working stations for the given cycle time.

In this paper, we consider a problem of VLSI (very large scale integrated) design occurring in the routing phase. The problem is to determine the optimal size selection for the gates in a combinatorial circuit which uses the problem of finding a shortest path in an oriented acyclic graph for making certain updates between any two successive iterations. For this NP-hard problem, we give an approximation algorithm.

In this note, we consider a single machine scheduling problem with generalized total tardiness objective function. A pseudo-polynomial time solution algorithm is proposed for a special case of this problem. Moreover, we present a new graphical algorithm for another special case, which corresponds to the classical problem of minimizing the weighted number of tardy jobs on a single machine. The latter algorithm improves the complexity of an existing pseudo-polynomial algorithm by Lawler. Computational results are presented for both special cases considered.

We consider single machine scheduling problems with a non-renewable resource. These types of problems have not been intensively investigated in the literature so far. For several problems of these types with standard objective functions (namely the minimization of makespan, total tardiness, number of tardy jobs, total completion time and maximum lateness), we present some complexity results. Particular attention is given to the problem of minimizing total tardiness. In addition, for the so-called budget scheduling problem with minimizing the makespan, we present some properties of feasible schedules.

We study a planning problem of an imperfect production of a single product. The product is assumed to be continuously divisible. There are two facilities: a main facility dedicated to the original production and a facility dedicated to re-manufacturing defective units coming from the main facility. Units fabricated on the main facility are inspected for quality in batches. The quality inspection requires some time and can be performed on-line or off-line. After the inspection has been completed, defective units of the inspected batch are transported to the re-manufacturing facility. The transportation also requires some time. We assume that the fraction of the defective units is the same in each batch on the manufacturing facility and that the re-manufacturing facility is perfect. Given a demand for good quality units of the product and an upper bound K on the number of batches, the problem is to find a sequence of batch sizes such that the makespan, i.e., the time of the demand satisfaction, is minimized. We suggest a linear programming formulation, prove several properties of an optimal solution, and finally develop an O ( log K ) time solution algorithm. A similar per time unit cost minimization problem is studied as well.

An increased use of wood products and an adequate management of forests can help to mitigate climate change. However, planning horizons and response time to changes in forest management are usually long and the respective GHG effects related to the use of wood depend on the availability of harvested wood. Therefore, an integral long-term strategic approach is required to formulate the most effective forest and wood management strategies for mitigating climate change. The greenhouse gas (GHG) dynamics related to the production, use and disposal of wood products are manifold and show a complex time pattern. On the one hand, wood products can be considered as a carbon pool, as is the forest itself. On the other hand, an increased use of wood can lead to the substitution of usually more energy-intense materials and to the substitution of fossil fuels when the thermal energy of wood is recovered. Country-specific import/export flows of wood products and their alternative products as well as their processing stage have to be considered if substitution effects are assessed on a national basis. We present an integral model-based approach to evaluate the GHG impacts of various forest management and wood use scenarios. Our approach allows us to analyse the complex temporal and spatial patterns of GHG emissions and removals including trade-offs of different forest management and wood use strategies. This study shows that the contributions of the forestry and timber sector to mitigate climate change can be optimized with the following key recommendations: (1) the maximum possible, sustainable increment should be generated in the forest, taking into account biodiversity conservation as well as the long-term preservation of soil quality and growth performance; (2) this increment should be harvested continuously; (3) the harvested wood should be processed in accordance with the principle of cascade use, i.e. first be used as a material as long as possible, preferably in structural components; (4) waste wood that is not suitable for further use should be used to generate energy. Political strategies to solely increase the use of wood as a biofuel cannot be considered efficient from a climate perspective; (5) forest management strategies to enhance carbon sinks in forests via reduced harvesting are not only ineffective because of a compensatory increase in fossil fuel consumption for the production of non-wooden products and thermal energy but also because of the Kyoto-“cap” that limits the accountability of GHG removals by sinks under Article 3.3 and 3.4, at least for the first commitment period; (6) the effect of substitution through the material and energy use of wood is more significant and sustained as compared with the stock effects in wood products, which tend towards new steady-state flow equilibria with no further increase of C stocks; (7) from a global perspective, the effect of material substitution exceeds that of energy recovery from wood. In the Swiss context, however, the energy recovery from wood generates a greater substitution effect than material substitution.

In this paper, we consider a parallel machine environment when all jobs have the same processing time and arbitrary release dates and deadlines of the jobs are given. We suppose that the available number of machines, which can be used simultaneously, may vary over time. The aim is to construct a feasible schedule in such a way that the maximal number of simultaneously used machines is minimal. We give a polynomial algorithm for this problem.

A set of jobs has to be scheduled on parallel uniform machines. Each machine can handle at most one job at a time. Each job becomes available for processing at its release date. All jobs have the same execution requirement, and each machine has a known speed. The processing of any job may be interrupted arbitrarily often and resumed later on any machine. We want to find a schedule that minimizes the sum of completion times, i.e., we consider problem Q|r"j,p"j=p,pmtn|@?C"j whose complexity status was open. In this paper, we give a polynomial algorithm for the above problem. The algorithm is based on a reduction of the scheduling problem to a linear program. The crucial condition for implementing the proposed reduction is the known order of job completion times.

The scheduling problem of minimizing total tardiness on a single machine is known to be NP-hard in the ordinary sense. In this paper, we consider the special case of the problem when the processing times p"j and the due dates d"j of the jobs j,[email protected]?N={1,2,...,n}, are oppositely ordered: p"1>=p"2>=...>=p"n and d"[email protected]?d"[email protected][email protected]?d"n. It is shown that already this special case is NP-hard in the ordinary sense, too. The set of jobs N is partitioned into k,[email protected][email protected]?n, subsets M"1,M"2,...,M"k, M"@[email protected]?M"@[email protected]? for @n @m,N=M"[email protected]?M"[email protected][email protected]?M"k, such that max"i","j"@?"M"""@n|d"i-d"j|@?min"j"@?"M"""@np"j for each @n=1,2,...,k. We propose algorithms which solve the problem: in O([email protected]?p"j) time if [email protected]?k=p"2>=...>=p"n mentioned above nor integer processing times to construct an optimal schedule. Finally, we apply the idea of the presented algorithm for the case k=1 to the even-odd partition problem.

This paper considers a flexible flow shop scheduling problem, where at least one production stage is made up of unrelated parallel machines. Moreover, sequence- and machine-dependent setup times are given. The objective is to find a schedule that minimizes a convex sum of makespan and the number of tardy jobs in a static flexible flow shop environment. For this problem, a 0-1 mixed integer program is formulated. The problem is, however, a combinatorial optimization problem which is too difficult to be solved optimally for large problem sizes, and hence heuristics are used to obtain good solutions in a reasonable time. The proposed constructive heuristics for sequencing the jobs start with the generation of the representatives of the operating time for each operation. Then some dispatching rules and flow shop makespan heuristics are developed. To improve the solutions obtained by the constructive algorithms, fast polynomial heuristic improvement algorithms based on shift moves and pairwise interchanges of jobs are applied. In addition, metaheuristics are suggested, namely simulated annealing (SA), tabu search (TS) and genetic algorithms. The basic parameters of each metaheuristic are briefly discussed in this paper. The performance of the heuristics is compared relative to each other on a set of test problems with up to 50 jobs and 20 stages and with an optimal solution for small-size problems. We have found that among the constructive algorithms the insertion-based approach is superior to the others, whereas the proposed SA algorithms are better than TS and genetic algorithms among the iterative metaheuristic algorithms.

The flow-shop minimum-length scheduling problem with n jobs processed on two machines is addressed where processing times are uncertain (only lower and upper bounds for the random processing time are given, while the probability distribution between these bounds is unknown). For such a problem, there often does not exist a dominant schedule that remains optimal for all possible realizations of the job processing times, and so we look for a minimal dominant set of schedules, which may be represented by a partial job order. We investigate properties of this partial job order and show how to construct this order in polynomial time. The approach based on a set of dominant schedules allows us to find special cases of the problem when it is possible to find an optimal schedule in spite of the uncertainty of the numerical data.

A subset of vertices in a graph is called a dissociation set if it induces a subgraph with vertex degree at most 1. A dissociation set D is maximal if no other dissociation set contains D. The complexity of finding a dissociation set of maximum size in line graphs and finding a maximal dissociation set of minimum size in general graphs is considered.

Whereas the overwhelming majority of scheduling problems appears to be NP-hard, models with equal processing time jobs form a remarkable case which is still open for most problems but it intuitively looks polynomially solvable. The basic scheduling problem we are dealing with is the following. There are n jobs, each requiring an identical execution time p. There are associated a release time rj and a deadline Dj with each job. All data are assumed to be integers. The aim is to construct a feasible schedule so as to minimize a given criterion. In this paper, we survey existing approaches for the problem considered, and for various machine environments.

In this paper we propose a decomposition approach that hierarchically integrates the batching and local search heuristics in manufacturing scheduling. The problem comprises two main interrelated stages embedded in any production-transportation supply chain, namely (i) scheduling processing of raw materials and robot's transportation operation within each individual cell, and (ii) scheduling of transportation and distribution of batches of semi-finished products between cells. Several efficient heuristic algorithms are proposed. This work has been motivated by a real-life problem of production planning for a CIM system for manufacturing of multi-component products served by robots.

This paper considers the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. It continues recent work by Brasel et al. [H. Brasel, A. Herms, M. Morig, T. Tautenhahn, T. Tusch, F. Werner, Heuristic constructive algorithms for open shop scheduling to minmize mean flow time, European J. Oper. Res., in press (doi.10.1016/j.ejor.2007.02.057)] on constructive algorithms. For this strongly NP-hard problem, we present two iterative algorithms, namely a simulated annealing and a genetic algorithm. For the simulated annealing algorithm, several neighborhoods are suggested and tested together with the control parameters of the algorithm. For the genetic algorithm, new genetic operators are suggested based on the representation of a solution by the rank matrix describing the job and machine orders. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The algorithms are compared relative to each other, and the quality of the results is also estimated partially by a lower bound for the corresponding preemptive open shop problem. For most of the problems, the genetic algorithm is superior when fixing the same number of 30000 generated solutions for each algorithm. However, in contrast to makespan minimization problems, where the focus is on problems with an equal number of jobs and machines, it turns out that problems with a larger number of jobs than machines are the hardest problems.

In this paper, we consider the problem of scheduling n jobs on m machines in an open shop environment so that the sum of completion times or mean flow time becomes minimal. For this strongly NP-hard problem, we develop and discuss different constructive heuristic algorithms. Extensive computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The quality of the solutions is evaluated by a lower bound for the corresponding preemptive open shop problem and by an alternative estimate of mean flow time. We observe that the recommendation of an appropriate constructive algorithm strongly depends on the ratio n/m.

In this paper, metaheuristic approaches for the two-machine flow-shop problem with a common due date and the weighted late work performance measure (F2|d"j=d|Y"w) are presented. The late work criterion estimates the quality of a solution with regard to the duration of the late parts of jobs, not taking into account the quantity of the delay for the fully late activities. Since the problem mentioned is known to be NP-hard, three trajectory methods, namely simulated annealing, tabu search and variable neighborhood search are proposed based on the special features of the case under consideration. Then, the results of computational experiments are reported, in which the metaheuristics were compared one to each other, as well to an exact approach and a list scheduling algorithm.

Many pathogens utilize the formation of transmembrane pores in target cells in the process of infection. A great number of pore-forming proteins, both bacterial and viral, are considered to be important virulence factors, which makes them attractive targets for the discovery of new therapeutic agents. Our research is based on the idea that compounds designed to block the pores can inhibit the action of virulence factors, and that the chances to find high affinity blocking agents increase if they have the same symmetry as the target pore. Recently, we demonstrated that derivatives of beta-cyclodextrin inhibited anthrax lethal toxin (LeTx) action by blocking the transmembrane pore formed by the protective antigen (PA) subunit of the toxin. To test the broader applicability of this approach, we sought beta-cyclodextrin derivatives capable of inhibiting the activity of Staphylococcus aureus alpha-hemolysin (alpha-HL), which is regarded as a major virulence factor playing an important role in staphylococcal infection. We identified several amino acid derivatives of beta-cyclodextrin that inhibited the activity of alpha-HL and LeTx in cell-based assays at low micromolar concentrations. One of the compounds was tested for the ability to block ion conductance through the pores formed by alpha-HL and PA in artificial lipid membranes. We anticipate that this approach can serve as the basis for a structure-directed drug discovery program to find new and effective therapeutics against various pathogens that utilize pore-forming proteins as virulence factors.

The problem of scheduling the production of new and recovering defective items of the same product manufactured on the same facility is studied. The items are produced in batches. The processing of a batch includes two stages. In the first stage, all items of a batch are manufactured and good-quality items go to the inventory to satisfy given demands. In the second stage, defective items of the same batch are reworked. After rework each item has the required good-quality. During waiting for rework defective items are assumed to deteriorate. This results in an increase in time and cost for performing rework processes. It is assumed that the percentage of defective items is the same in each batch, and that they are uniformly distributed in each batch. A setup time as well as a setup cost is required to start batch processing and to switch from production to rework. The objective is to find batch sizes such that all demands are satisfied and total setup, rework and inventory holding cost is minimized. Polynomial time algorithms are presented to solve two realistic special cases of this problem. A generalization to a multiple product case is discussed.

We study a deterministic problem of planning the production of new and recovering defective items of the same product manufactured on the same facility. Items of the product are produced in batches. The processing of a batch includes two stages. In the first work stage, all items of a batch are manufactured and good quality items go to the inventory to satisfy given demands. In the second rework stage, some of the defective items of the same batch are reworked. Each reworked item has the required good quality. While waiting for rework, defective items deteriorate. There is a given deterioration time limit. A defective item, that is decided not to be reworked or cannot be reworked because its waiting time will exceed the deterioration time limit, is disposed of immediately after its work operation completes. Deterioration results in an increase in time and cost for performing rework processes. It is assumed that the percentage of defective items is the same in each batch, and that they are evenly distributed in each batch. A setup time as well as a setup cost is required to start batch processing and to switch from production to rework. The objective is to find batch sizes and positions of items to be reworked such that a given number of good-quality items is produced and total setup, rework, inventory holding, shortage and disposal cost is minimized. A polynomial dynamic programming algorithm is presented to solve this problem.

In this paper, the problem of scheduling n jobs on m machines in an open shop environment is considered so that mean flow time becomes minimal. Since this problem is strongly NP-hard, different constructive and iterative heuristic algorithms are developed and discussed. Computational results are presented for problems with up to 50 jobs and 50 machines, respectively. The quality of the solutions is estimated by a lower bound for the corresponding preemptive open shop problem and by an alternative estimation of mean flow time.

It is known that all 2-connected, linearly convex triangular grid graphs, with only one exception, are hamiltonian (Reay and Zamfirescu, 2000). In the paper, it is shown that this result holds for a wider class of connected, locally connected triangular grid graphs and, with more exceptions, even for some general class of graphs. It is also shown that the HAMILTONIAN CYCLE problem is NP-complete for triangular grid graphs.

This article addresses the job-shop scheduling problem of minimizing the length of a schedule (makespan) for processing n jobs by one or two machines with sequence-dependent setup times and clean-up times. The processing of each job includes at most two operations that have to be non-preemptive. Machine routes may differ from job to job. If all setup and clean-up times are equal to zero, this problem is polynomially solvable via Jackson's pair of job permutations, otherwise it is NP-hard even if each of n jobs consists of one operation on the same machine. We present sufficient conditions when Jackson's pair of job permutations may be used for solving the two-machine job-shop scheduling problem with sequence-dependent setup times and clean-up times. For the general case of the latter problem, the results obtained provide polynomial lower and upper bounds for the objective function which may be used in an implicit enumeration technique, e.g., in a branch-and-bound algorithm.

In this paper we analyze different solution procedures for the two-machine flow shop scheduling problem with a common due date and weighted late work criterion, i.e. for problem F2|dj = d|Yw, which is known to be binary NP-hard. In computational experiments we compare the practical efficiency of a dynamic programming approach, an enumerative method and a heuristic list scheduling procedure. Test results show that each solution method has its advantages and none of them can be rejected from consideration a priori.

The paper is on the two-machine non-preemptive flow-shop scheduling problem with a total weighted late work criterion and a common due date ( F 2| d i = d | Y w ). The late work performance measure estimates the quality of the obtained solution with regard to the duration of late parts of tasks not taking into account the quantity of this delay. We prove the binary NP-hardness of the problem mentioned by showing a transformation from the partition problem to its decision counterpart. Then, a dynamic programming approach of pseudo-polynomial time complexity is formulated.

We study the single machine scheduling problem with controllable job processing times to minimize a linear combination of the total weighted job completion time and the total weighted processing time compression. We show that this scheduling problem is a positive half-product minimization problem. Positive half-products make up an interesting subclass of half-products and are introduced in this paper to provide a conceptual framework for the problem with controllable job processing times as well as other problems. This framework allows to readily derive in one fell swoop a number of results for the problem with controllable processing times from more general results obtained earlier for the half-product. We also present fast fully polynomial time approximation schemes for the problem with controllable processing times. The schemes apply to all positive half-products.

We consider a job shop scheduling problem under uncertain processing times and fixed precedence and capacity constraints. Each of the random processing times can take any real value between given lower and upper bounds. The goal is to find a set of schedules which contains at least one optimal schedule (with mean flow time criterion) for any admissible realization of the random processing times. In order to compute such a set of schedules efficiently and keep it as small as possible, we develop several exact and heuristic algorithms and report computational experience based on randomly generated instances.