Search

Accuracy and stability have in recent studies been emphasized as the two major ingredients to learn robot motions from demonstrations with dynamical systems. Several approaches yield stable dynamical systems but are also limited to specific dynamics that can potentially result in a poor reproduction performance. The current work addresses this accuracy-stability dilemma through a new diffeomorphic transformation approach that serves as a framework generalizing the class of demonstrations that are learnable by means of provably stable dynamical systems. We apply the proposed framework to extend the application domain of the stable estimator of dynamical systems (SEDS) by generalizing the class of learnable demonstrations by means of diffeomorphic transformations ? . The resulting approach is named ? -SEDS and analyzed with rigorous theoretical investigations and robot experiments. A novel method named tau-SEDS that learns stable robot motions from demonstrations on the basis of nonlinear dynamical systems is proposed.The method allows learning dynamical systems that are stable and accurate by construction without much tuning effort.The approach is rigorously analyzed within a substantial theoretical framework.Several robotics experiments underline the applicability of the method.

The data-driven approximation of vector fields that encode dynamical systems is a persistently hard task in machine learning. If data is sparse and given in the form of velocities derived from few trajectories only, state-space regions exist, where no information on the vector field and its induced dynamics is available. Generalization towards such regions is meaningful only if strong biases are introduced, for instance assumptions on global stability properties of the to-be-learned dynamics. We address this issue in a novel learning scheme that represents vector fields by means of neural networks, where asymptotic stability of the induced dynamics is explicitly enforced through utilizing knowledge from Lyapunov׳s stability theory, in a predefined workspace. The learning of vector fields is constrained through point-wise conditions, derived from a suitable Lyapunov function candidate, which is first adjusted towards the training data. We point out the significance of optimized Lyapunov function candidates and analyze the approach in a scenario where trajectories are learned and generalized from human handwriting motions. In addition, we demonstrate that learning from robotic data obtained by kinesthetic teaching of the humanoid robot iCub leads to robust motion generation.

This paper deals with scheduling batch (i.e., discontinuous), continuous, and semicontinuous production in process industries (e.g., chemical, pharmaceutical, or metal casting industries) where intermediate storage facilities and renewable resources (processing units and manpower) of limited capacity have to be observed. First, different storage configurations typical of process industries are discussed. Second, a basic scheduling problem covering the three above production modes is presented. Third, (exact and truncated) branch-and-bound methods for the basic scheduling problem and the special case of batch scheduling are proposed and subjected to an experimental performance analysis. The solution approach presented is flexible and in principle simple, and it can (approximately) solve relatively large problem instances with sufficient accuracy.

Inventory constraints refer to so-called cumulative resources, which can store a single or several different products and have a prescribed minimum and maximum inventory, where the inventory is depleted and replenished over time. Some additional applications of cumulative resources, e.g. to investment projects, are also discussed in this paper.

An Advanced Planning System (APS) offers support at all planning levels along the supply chain while observing limited resources. We consider an APS for process industries (e.g. chemical and pharmaceutical industries) consisting of the modules network design (for long–term decisions), supply network planning (for medium–term decisions), and detailed production scheduling (for short–term decisions). For each module, we outline the decision problem, discuss the specifi cs of process industries, and review state–of–the–art solution approaches. For the module detailed production scheduling, a new solution approach is proposed in the case of batch production, which can solve much larger practical problems than the methods known thus far. The new approach decomposes detailed production scheduling for batch production into batching and batch scheduling. The batching problem converts the primary requirements for products into individual batches, where the work load is to be minimized. We formulate the batching problem as a nonlinear mixed–integer program and transform it into a linear mixed–binary program of moderate size, which can be solved by standard software. The batch scheduling problem allocates the batches to scarce resources such as processing units, workers, and intermediate storage facilities, where some regular objective function like the makespan is to be minimized. The batch scheduling problem is modelled as a resource–constrained project scheduling problem, which can be solved by an efficient truncated branch–and–bound algorithm developed recently. The performance of the new solution procedures for batching and batch scheduling is demonstrated by solving several instances of a case study from process industries.

We present heuristic procedures for approximately solving large project scheduling problems with general temporal and resource constraints. In particular, we propose several truncated branch-and-bound techniques, priority-rule methods, and schedule-improvement procedures of types tabu search and genetic algorithm. A detailed experimental performance analysis compares the different heuristics devised and shows that large problem instances with up to 1000 activities and several resources can efficiently be solved with sufficient accuracy.

For many applications of project scheduling to real-life problems, it is necessary to take into account calendars specifying time intervals during which some resources such as manpower or machines are not available. Whereas the execution of certain activities like packaging may be suspended during breaks, other activities cannot be interrupted due to technical reasons. Minimum and maximum time lags between activities may depend on calendars, too. In this paper, we address the problem of scheduling the activities of a project subject to calendar constraints. We devise efficient algorithms for computing earliest and latest start and completion times of activities. Moreover, we sketch how to use these algorithms for developing priority-rule methods coping with renewable-resource constraints and calendars.

This paper deals with resource-constrained project scheduling problems with nonregular objective functions where general temporal constraints given by minimum and maximum time lags between activities are prescribed. In particular, resource leveling and net present value problems are studied. We present different heuristic and exact procedures for (approximately) solving those problems. A detailed experimental performance analysis shows that these procedures also solve large problem instances in reasonable computing time.

The paper presents polynomial heuristic procedures for different types of resource levelling problems for projects with minimum and maximum time lags between project activities. Both problems without and with explicit resource constraints are treated. Thus far, only pseudopolynomial heuristics for special resource levelling problems without maximum time lags and resource constraints have been proposed. An experimental performance analysis shows that the new heuristics approximately solve problem instances with up to 500 activities and five resources within reasonable computing time.

Summary Aim of the study was to assess the value of in vitro three-dimensional computed tomography (3D-CT) as a new method for the depiction of the fetal skull. 3D-CT images of a fetal head of 24 weeks gestational age were generated with the implemented software on the basis of contiguous CT slices of 1 mm thickness. 3D-CT gave real three-dimensional information about morphology and spatial arrangement of the cranial bones. Using cutting and rotating procedures fast evaluation of all imaged ossified structures in arbitrary views without disturbing superpositions was possible, thus allowing easy identification and accurate description of the cranial bones and making isolated examinations of particular macroscopic sections of the specimens unnecessary. Advantages of 3D-CT over other evaluation techniques for the fetal cranium and its limitations are discussed. In conclusion, 3D-CT promises to be an effective tool for the investigation of fetal cranial development.

Project scheduling is concerned with single-item or small batch production where scarce resources have to be allocated to dependent activities over time. Applications can be found in diverse industries such as construction engineering, software development, etc. Also, project scheduling is increasingly important for make-to-order companies where the capacities have been cut down in order to meet lean management concepts. Likewise, project scheduling is very attractive for researchers, because the models in this area are rich and, hence, difficult to solve. For instance, the resource-constrained project scheduling problem contains the job shop scheduling problem as a special case. So far, no classification scheme exists which is compatible with what is commonly accepted in machine scheduling. Also, a variety of symbols are used by project scheduling researchers in order to denote one and the same subject. Hence, there is a gap between machine scheduling on the one hand and project scheduling on the other with respect to both, viz. a common notation and a classification scheme. As a matter of fact, in project scheduling, an ever growing number of papers is going to be published and it becomes more and more difficult for the scientific community to keep track of what is really new and relevant. One purpose of our paper is to close this gap. That is, we provide a classification scheme, i.e. a description of the resource environment, the activity characteristics, and the objective function, respectively, which is compatible with machine scheduling and which allows to classify the most important models dealt with so far. Also, we propose a unifying notation. The second purpose of this paper is to review some of the recent developments. More specifically, we review exact and heuristic algorithms for the single-mode and the multi-mode case, for the time–cost tradeoff problem, for problems with minimum and maximum time lags, for problems with other objectives than makespan minimization and, last but not least, for problems with stochastic activity durations.

This paper deals with job‐shop scheduling with stochastic precedenceconstraints given by so‐called OR networks. At first, a job‐shop problem withstochastic OR network precedence constraints is described, where the expected makespan isto be minimized. Next, the concept of an aggregate schedule is discussed, which represents a deterministic staticscheduling policy for our stochastic problem. The construction of an appropriate aggregatedisjunctive graph permits us to adapt the shifting bottleneck heuristic. After that,a priority‐rulemethod is proposed for finding an approximate aggregate schedule. An experimentalperformance analysis shows that both heuristics provide good approximate solutions. Finally,we briefly discuss a flow‐shop problem with OR network precedence constraints and thecase of cyclic OR networks.

This paper is concerned with stochastic scheduling problems with several identical parallel machines, where the task durations and precedence constraints are stochastic. The stochastic precedence constraints are given by special GERT networks. At first, basic concepts and results are surveyed for GERT networks and for single-machine and parallel-machine scheduling with GERT network precedence constraints. An example shows where GERT scheduling problems occur in practice. After that, two types of heuristics for identical parallel-machine GERT scheduling problems with objective functions E(C max ), maxE(C),and E(∑ C) are proposed: generalizations of algorithms for corresponding deterministic scheduling problems and so-called priority-rule methods. An empirical analysis shows the best heuristics for each of the objective functions considered.

Maximal time lags between activities of a project play an important role in practice in addition to minimal ones. However, maximal time lags have been discussed very rarely in literature thus far. This paper shows how to model projects with minimal and maximal time lags by cyclic activity-on-node networks. As an important application, the production process for make-to-order production with limited resources is studied, which can be represented by a multi-project network where the individual operations of the jobs correspond to the nodes of the network. For different product structures, careful consideration is given to the modelling of a nondelay performance of overlapping operations by appropriately establishing minimal and maximal time lags.

Most production planning and control (PPC) systems used in practice have an essential weakness in that they do not support hierarchical planning with feedback and do not observe resource constraints at all production levels. Also, PPC systems often do not deal with particular types of production, for example, low-volume production. We propose a capacity-oriented hierarchical approach to single-item and small-batch-production planning for make-to-order production. In particular, the planning stages of capacitated master production scheduling, multi-level lot sizing, temporal and capacity planning, and shop floor scheduling are discussed, where the degree of aggregation of products and resources decreases from stage to stage. It turns out that the optimization problems arising at most stages can be modelled as resourceconstrained project scheduling problems.

The paper presents heuristics for two types of resource—constrained project-scheduling problems: the problem of levelling the resources consumption and the minimum project—duration problem. Both mi...

Extreme learning machines are randomly initialized single-hidden layer feed-forward neural networks where the training is restricted to the output weights in order to achieve fast learning with good performance. This contribution shows how batch intrinsic plasticity, a novel and efficient scheme for input specific tuning of non-linear transfer functions, and ridge regression can be combined to optimize extreme learning machines without searching for a suitable hidden layer size. We show that our scheme achieves excellent performance on a number of standard regression tasks and regression applications from robotics.

The application of machine learning methods in the engineering of intelligent technical systems often requires the integration of continuous constraints like positivity, monotonicity, or bounded curvature in the learned function to guarantee a reliable performance. We show that the extreme learning machine is particularly well suited for this task. Constraints involving arbitrary derivatives of the learned function are effectively implemented through quadratic optimization because the learned function is linear in its parameters, and derivatives can be derived analytically. We further provide a constructive approach to verify that discretely sampled constraints are generalized to continuous regions and show how local violations of the constraint can be rectified by iterative re-learning. We demonstrate the approach on a practical and challenging control problem from robotics, illustrating also how the proposed method enables learning from few data samples if additional prior knowledge about the problem is available.

Recent results on resource-constrained project scheduling with time windows are reviewed. General temporal constraints (resulting from minimum and maximum time lags between project activities), several different types of scarce resources, and a large variety of time-based, financial, and resource-based objective functions are considered. Emphasis is placed on an order-based structural analysis of the feasible region of project scheduling problems and a classification and discussion of objective functions important to practice, which can be exploited for constructing efficient solution procedures. After those structural issues, methods for solving time-constrained project scheduling problems are proposed. Next, the resolution of conflicts for renewable, allocatable, synchronizing, changeover, and cumulative resources and thus the solving of corresponding resource-constrained project scheduling problems are studied. Finally, new applications of resource-constrained project scheduling are presented: factory pick-up of new cars and batch scheduling in process industries.

Stochastic min-sum and min-max single-machine scheduling problems are considered where the precedence constraints are given by a so-called OR network. An OR network is a special stochastic activity network (GERT network) which may contain cycles and has some tree-structure property. It turns out that min-max problems are harder than min-sum problems in contrast to deterministic scheduling. If the objective function is the expected weighted flow time, an optimal scheduling policy can be computed in polynomial time. The min-max problem with unit-time activities, maximum expected completion time of the so-called operations as objective function, and precedence constraints given by an acyclic OR network is shown to be NP-hard. However, if we restrict ourselves to priority lists of operations instead of general scheduling policies, there is a polynomial algorithm for the scheduling problem where the activity durations are generally distributed and the objective function is the maximum expected lateness.

Thus far, we have not taken account of the limited availability of resources which are required for carrying out the activities of a project. In what follows, we are going to take scarce resources into consideration. In practice, different types of resources may occur. Renewable resources (such as machines, equipment, manpower, or space) are available at each point in time or, if time is discrete, in each single time period during the execution of the project independently of their utilization formerly. Nonrenewable resources (e.g. money or energy) are depleted by use. Nonrenewable resources only affect the scheduling of activities if activities can be carried out in alternative modes which differ, for example, in duration and amount of resources needed. We then speak of multi-mode project scheduling problems in contrast to single-mode problems. Doubly-constrained resources are restricted at each point in time (or in each time period if time is discrete) during the execution of the project and for the whole project (for example, money with restricted cash flow per period and limited amount of capital available). A doubly-constrained resource can be replaced by a combination of a renewable and a nonrenewable resource. Cumulative or storage resources represent stock-keeping facilities. They can store a single or several different products and have a prescribed minimum and maximum inventory, where the inventory is generally depleted and replenished over time. Sometimes, the activities are divided into families containing activities with similar properties. Synchronizing resources process the activities from such a family batchwise, where all activities in a batch must be started at the same time. Examples of synchronizing resources are furnaces or autoclaves in process industries. In literature, additional resource types have been discussed: partially renewable resources (cf. Bottcher et al., 1999), whose capacity refers to sets of time periods, and spatial resources (see de Boer, 1998, and Demeulemeester and Herroelen, 2002, Ch. 2, Subsect. 2.2.5), for which resource requirements refer to activity families instead of individual activities and resource units are occupied from the start of the first up to the completion of the last activity of the family.

In this chapter, we deal with temporal aspects of project scheduling. That is, we observe that the activities of the project under consideration require time for their completion and that there are generally time windows between activities. However, we do not take into account that in general resources are needed and possibly costs are incurred during the execution of project activities.

The paper deals with short-term planning problems in process industries where final products are obtained by several successive chemical or physical transformations of raw materials using scarce multi-purpose equipment. In batch production mode, the total requirements for intermediate and final products are partitioned into batches. The production start of a batch at a given level requires the availability of all input products. We consider the problem of scheduling the production of given primary requirements for final products such that the makespan is minimized, where the batch sizes can be chosen within prescribed intervals. Further constraints arise from limited production and storage capacities as well as sequence-dependent cleaning times for processing units. We propose a new solution approach which is based on the decomposition of the short-term planning problem into computing appropriate batch sizes (batching) and the subsequent scheduling of batches on processing units (batch scheduling). The former problem is modelled and solved as a nonlinear mixed integer program, whereas the latter problem is addressed using models and methods of resource-constrained project scheduling. The solution procedure proposed (approximately) solves problems of industrial size within a reasonable amount of computing time.

RATIONALE AND OBJECTIVES. A large variety of cardiac MRI sequences have been introduced for heart morphology evaluation. The aim of this study was to establish a practicable and robust examination protocol for standard high-field systems applying nongradient echo sequences with single- and multislice acquisition. METHODS. Fifty-one patients received electrocardiogram-gated MRI of the heart with “black-blood” preparation, comparing three single-slice and three multislice sequences with a T1-weighted turbo spin echo reference sequence. Demarcation of the left ventricular myocardium and cavity and the extent of flow and motion artifacts were assessed. RESULTS. The myocardium and left ventricular cavity were depicted best with the single-slice T1- and T2-weighted turbo spin echo sequence. The nonbreath-hold multislice sequences produced marked artifacts and therefore were of poor diagnostic value. The TIRM haste sequence was best suited for fat suppression. The T2-weighted breath-hold single-shot sequence with half-Fourier imaging proved to be most appropriate for multislice imaging. CONCLUSIONS. Sufficient depiction of heart morphology with comprehensive evaluation of signal changes can be achieved using nongradient spin echo and turbo spin echo sequences with breath-holding. For rational imaging of myocardial and heart chamber morphology, multislice and single-slice sequences should be combined.

The so-called classical project networks used by the network techniques CPM, PERT, and MPM, only allow for modelling projects whose evolution in time is uniquely specified in advance (cf. Elmaghraby 1977 and Moder et al. 1983). Here, each project activity is carried out exactly once during a single project execution and it is not possible to return to activities previously performed (that is, no feedback is permitted). Many practical projects, however, do not meet those conditions, for example, R&D projects and projects in production management where quality control is included and thus some feedback may occur.

We describe a heuristic procedure for solving multi-product, multi-period, single-level batch-production problems. The method consists of two procedures for a lot-sizing problem with capacity constraints for time-varying demand and a job-shop machine-scheduling problem for given lot sizes, which are applied in succession. We also discuss the performance of the priority rules of the Giffler-Thompson algorithm for solving the job-shop problem.

We have seen in chapter 3 that STEOR networks can be evaluated in a relatively easy manner by means of the MRP method. Nodes with AND entrance or IOR entrance, however, cause some difficulties. Therefore, it suggests itself to investigate GERT networks all of whose AND nodes and IOR nodes lie inside special subnetworks which can be reduced to structures containing only STEOR nodes. Obviously, the reduction of those subnetworks to “STEOR subnetworks” should be done such that the “reduced” GERT network is equivalent to the original (“reducible”) GERT network.

In this chapter we consider the case where different types of cost are incurred by the execution of activities and the occurrence of events of a project modelled by a STEOR network. We will see that the expected total cost of the project depends only on the activation functions Yj of the individual nodes j of the network. Since the activation function Yj of any node j in an admissible EOR network N coincides with the activation function of node j in each STEOR network from a covering of N that contains all nodes from S(j) and all arcs joining those nodes (cf. (3.5.10)), the cost minimization problem for admissible EOR networks of Markov degree d >1 can be solved in the same manner as for STEOR networks.

STEOR networks are GERT networks with only STEOR nodes. STEOR networks represent that class of GERT networks whose evaluation is the easiest due to the fact that Markov renewal processes can be associated with those networks. In particular, STEOR networks satisfy the one-sink condition. Exploiting some results from the theory of Markov renewal processes, an efficient method for computing the activation functions Yij can be found.

In CPM and PERT network techniques, the temporal analysis includes the determination of the earliest and latest times of occurrence of the individual project events besides the computation of the (distribution of the) project duration. For GERT networks, it is also possible to introduce the concepts of earliest and latest times of activation of nodes. Their meaning, however, is different from that for CPM and PERT networks (because project events may occur several times) and their computation is in general much more complicated (cf. Delivorias (1979a, 1979b), Neumann and Steinhardt (1979a), section 2.5, and Wietek (1983)). Therefore, we will not deal with those concepts in this monograph.

Scheduling can be loosely defined as the art of assigning resources to tasks in order to insure the termination of the tasks in a reasonable amount of time or to minimize a certain cost function. Since the terminology of scheduling theory arose in the processing and manufacturing industries, one generally speaks of “machines” instead of resources and of “jobs” instead of tasks that have to be “processed” by the machines.

The construction of an expert-like system for machine scheduling called SCHEDULE is presented. Essential parts of SCHEDULE were developed by students in a laboratory course “Operations Research on Microcomputers” at the University of Karlsruhe, Germany. SCHEDULE consists of the components data base, knowledge base, inference engine, explanation facility, dialog component, and knowledge acquisition component. The knowledge base contains an algorithm base for solving different types of scheduling problems. To establish the rules of the knowledge base the well-known three-field classification of deterministic machine scheduling problems and the concept of the reduction digraph are exploited. Experiences gained during building and demonstrating SCHEDULE are reported.

This paper presents methods for the time-oriented evaluation of special GERT networks. If every node of a GERT network has an exclusive-or entrance and a stochastic exit (so-called STEOR node), then a Markov renewal process can be assigned to this activity network. In this case, the quantities of interest in project scheduling may be determined from the renewal functions of the process. In addition, GERT networks containing “non-STEOR nodes” are treated where the non-STEOR nodes are allowed to occur only within special subnetworks, called basic element structures. Numerical tests have shown that in most cases the methods described consume less computing time than simulation.

This paper considers project networks all of whose nodes have an exclusive-or entrance and whose arc weights consist of the execution probabilities and distribution functions of the durations of the respective project activities. EOR networks have some nice properties, for example, a set of Markov renewal processes can be assigned to such a network. The renewal functions of those processes correspond to special activation functions of the network and can (approximately) be computed very efficiently. At last a method for the complete evaluation of an EOR project network in the sense of time planning is presented.

Decision activity networks with six different types of nodes are investigated where to each arc are assigned the duration (a random variable with given distribution) and the performance probability of the corresponding activity. Certain restrictions concerning the structure of such decision networks make the reduction to networks possible which contain only nodes with exclusive-or entrance and stochastic exit side. At first, the probabilities that the distinct terminal events occur and the distribution of project duration are determined. The following minimization of the expected project cost results in an optimal control problem. The cost functional contains simple and double integrals subject to integral equations as restrictions. That problem may be solved by means of gradient methods in Hilbert spaces.

In chapters 2 to 5 we have restricted ourselves to the evaluation of GERT networks where the execution probabilities and the distribution functions of the durations of the individual activities are independent of the time of occurrence of the initial events of these activities (compare (1.2.5)). Many projects, however, for which the time planning is to be carried out by means of GERT networks do not satisfy this restriction.

GERT networks all of whose nodes have OR entrance and deterministic or stochastic exit and which are called OR networks are considered. The assumption that, figuratively speaking, different walks emanating from a deterministic node do not meet anywhere in an OR network results in a certain tree structure: If we shrink all strong components of the network to one node each, then any partial network whose activities are carried out during a single project execution represents an outtree. The above assumption also permits an OR network with “deterministic degree” d to be covered by d+1 STEOR networks (that is, GERT networks all of whose nodes have exclusive-or entrance and stochastic exit).

OR networks are cyclic GERT project networks all of whose nodes have an OR entrance and a deterministic or stochastic exit. The assumption that, figuratively speaking, different walks emanating from a deterministic node of an OR network do not meet beyond that node ensures that an OR network has some (generalized) tree structure. The tree-structure property can be exploited to generalize Smith’s ratio rule from deterministic scheduling to solve the stochastic single-machine scheduling problem for minimizing the sum of expected weighted completion times subject to precedence constraints given by an OR network. We consider two different cases: First, activities in cycles are counted for the objective function as often as they are carried out, and second, a passage through a strong component is viewed as a whole and taken into account only once.

In chapters 1 through 4 we have merely dealt with GERT networks which possess only STEOR nodes within cycles (according to assumption A5). In many cases, however, this restriction makes the assignment of a GERT network to a real project evolution impossible. We consider as an example the examination of a plan for a construction project.

GERT networks which only contain STEOR nodes can easily be evaluated in principle as we have seen in chapter 2. Difficulties, however, are caused by nodes with deterministic exit and, above all, by nodes with AND entrance or with IOR entrance. In this chapter we treat GERT networks which, on one hand, contain non-STEOR nodes but which, on the other hand, are still relatively easily evaluated, and for which, as with STEOR networks, exactly one target event occurs with probability one during each project execution. It is obvious that these two requirements entail certain restrictions placed on the structure of the corresponding GERT networks. It proves to be expedient in this context to admit non-STEOR nodes only within special reducible subnetworks2) the so-called basic element structures. After having evaluated these basic element structures, we obtain a STEOR network to which the MRP method treated in sections 2.2 and 2.3 may be applied.

In this chapter we present a procedure for the evaluation of admissible GERT networks (that is, the networks satisfy the assumptions A1 through A7) which also contain non-STEOR nodes outside of pre-basic element structures. This procedure, which determines the activation distribution of the sinks of an admissible GERT network (compare section 1.4, in particular (1.4.1), (1.4.2), (1.4.3)), requires a relatively great computational effort. Except for particular cases, the method of simulation or a combination of simulation and the algorithms described in chapters 2 and 3 (compare chapter 7) is therefore to be preferred to this evaluation procedure. A simpler version of this procedure suffices to determine so-called “non-genuine” IOR nodes and to replace them by EOR nodes, as is necessary, for example, in order to apply the BES method from chapter 3 (compare convention (3.1.2)). This will be discussed in section 4.4.