A two-machine flowshop problem with processing time-dependent buffer constraints—An application in multimedia presentations

To have a quality multimedia presentation through networks, its presentation lag needs to be controlled. One way to reduce the lag is to prefetch the media objects before their due dates. This paper explores techniques for optimizing the object sequence in a prefetch-enabled TV-like presentation. An optimal solution is the one with which the presentation lag is minimized. We formulate the problem into a two-machine flowshop scheduling problem with a single chain precedence constraint and a player-side buffer constraint. The player-side buffer is “processing time-dependent” and distinguished from the conventional item-based intermediate buffer constraints discussed in previous flowshop studies. We prove the problem to be strongly NP-hard. A branch and bound algorithm equipped with four lower bounds and an NEH-based upper bound is developed. The simulation results show that the average gaps between the overall lower bounds and the NEH-based upper bound are less than 3% for problems with a large buffer size, and less than 13% for problems with a small buffer size and high density of precedence constraints. For applications where the media objects are delivered through extremely busy servers with which only very restricted CPU resources can be allocated for computation, the CDS-based algorithm provides better sequences than the NEH-based algorithm.     

Routing under constraints: Problem of visit to megalopolises

Consideration was given to the problems of routing transfers under conditions of precedence and dynamic constraints including the dependence of the list of jobs both already completed by the instant of transfer or, on the contrary, not yet completed. The transfer costs also can be dependent on the list of jobs. The megalopolises (nonempty finite sets) are the objects of visits, which corresponds to the possible multiple-choice of transfers. The widely understood dynamic programming in a realization not requiring (under the precedence conditions) construction of the entire array of the Bellman function values is used as the basic method of study. The procedure of constructing a “complete” solution including determination of the optimal solution route and track (trajectory) and the procedure determining the problem value (global extremum) can be used separately to test the heuristic algorithms. An efficient heuristic algorithm was constructed to solve the routing problems of great dimension complicated by the constraints typical of the sheet cutting on the machines with computerized numerical control. For moderate problems, the results obtained were compared with the optimal result provided by the dynamic programming.     

IPSS: A Hybrid Approach to Planning and Scheduling Integration

Recently, the areas of planning and scheduling in artificial intelligence (AI) have witnessed a big push toward their integration in order to solve complex problems. These problems require both reasoning on which actions are to be performed as well as their precedence constraints (planning) and the reasoning with respect to temporal constraints (e.g., duration, precedence, and deadline); those actions should satisfy the resources they use (scheduling). This paper describes IPSS (integrated planning and scheduling system), a domain independent solver that integrates an AI planner that synthesizes courses of actions with constraint-based techniques that reason based upon time and resources. IPSS is able to manage not only simple precedence constraints, but also more complex temporal requirements (as the Allen primitives) and multicapacity resource usage/consumption. The solver is evaluated against a set of problems characterized by the use of multiple agents (or multiple resources) that have to perform tasks with some temporal restrictions in the order of the tasks or some constraints in the availability of the resources. Experiments show how the integrated reasoning approach improves plan parallelism and gains better makespans than some state-of-the-art planners where multiple agents are represented as additional fluents in the problem operators. It also shows that IPSS is suitable for solving real domains (i.e., workflow problems) because it is able to impose temporal windows on the goals or set a maximum makespan, features that most of the planners do not yet incorporate     

Elements of dynamic programming in local improvement constructions for heuristic solutions of routing problems with constraints

We consider methods for solving routing problems with precedence constraints that use iterative modes based on Bellman insertions while recomputing precedence constraints of the original problem; we assume that the dimension of the latter is sufficiently large, which does not let us, due to complexity of computations, immediately apply dynamic programming in the “global” version.     

Multiagent based dynamic resource scheduling for distributed multiple projects using a market mechanism

The resource scheduling problem in a multi-project environment extends job-shop scheduling problems by allowing for task dependency and multiple self-interested entities. In this paper we deal with short-term scheduling of resources, which are shared by multiple projects. In specific, we address the dynamic nature of the situation. We model this as a dynamic economy, where the multiple local markets are established and cleared over time, trading resource time slots (goods). Due to the dynamic and distributed nature of the economy, through our approach we can achieve higher levels of flexibility, scalability and adaptability. Unlike most market-based mechanisms, which are based on equilibrium concepts and iterative adjustment of resources prices, we propose a novel market mechanism called precedence cost tâtonnement (P-TâTO), which solves individual resource-constrained local resource scheduling in an optimal way, and searches for a precedence conflict-free schedule through a tâtonnement type procedure. In this paper, we discuss our dynamic economy model and some details of the market mechanism along with empirical analysis results.     

An optimal dynamic threat evaluation and weapon scheduling technique

Real time scheduling problems demand high level of flexibility and robustness under complex dynamic scenarios. Threat Evaluation (TE) and Weapon Assignment (WA), together TEWA is one such complex dynamic system that has optimal or near optimal utilization of scarce defensive resources, a supreme priority. Several static solutions of TEWA have been proposed. This paper discusses an optimal dynamic multi-air threat evaluation and weapon allocation algorithm using a variant of Stable Marriage Algorithm (SMA). WA uses a new dynamic weapon scheduling algorithm, allowing multiple engagements using shoot-look-shoot strategy, to compute near-optimal solution. For optimality different types of constraints are identified and defined. Testing part of this paper shows feasibility of this approach for a range of scenarios.     

Risk-sensitive decision-theoretic diagnosis

We consider the problem of determining the optimal sequence of tests for the discovery of a faulty component, where there is a random cost associated with testing a component. Our work is motivated by applications in telecommunications networks, e.g., location and isolation of faults (or intruders) in IP networks. A novel feature in our approach is that a risk-sensitive performance criterion is used in order to rank different competing schedules. Risk-sensitivity is incorporated through the use of an exponential utility function, and hence optimal schedules attain a trade-off between minimal expected costs and, e.g., a low variance about the achievable expected costs. We characterize optimal schedules both when the testing sequence is not subject to precedence constraints, and when it is subject to such constraints, given by an arbitrary partial order. For the case with precedence constraints, we show that our models can be analyzed via modular decompositions, as studied by Monma and Sidney (1987)     

An Experimental Study of Algorithms for Weighted Completion Time Scheduling

We consider the total weighted completion time scheduling problem for parallel identical machines and precedence constraints, P| prec|\sum w _i C _i . This important and broad class of problems is known to be NP-hard, even for restricted special cases, and the best known approximation algorithms have worst-case performance that is far from optimal. However, little is known about the experimental behavior of algorithms for the general problem. This paper represents the first attempt to describe and evaluate comprehensively a range of weighted completion time scheduling algorithms. We first describe a family of combinatorial scheduling algorithms that optimally solve the single-machine problem, and show that they can be used to achieve good performance for the multiple-machine problem. These algorithms are efficient and find schedules that are on average within 1.5\percent of optimal over a large synthetic benchmark consisting of trees, chains, and instances with no precedence constraints. We then present several ways to create feasible schedules from nonintegral solutions to a new linear programming relaxation for the multiple-machine problem. The best of these linear programming-based approaches finds schedules that are within 0.2\percent of optimal over our benchmark. Finally, we describe how the scheduling phase in profile-based program compilation can be expressed as a weighted completion time scheduling problem and apply our algorithms to a set of instances extracted from the SPECint95 compiler benchmark. For these instances with arbitrary precedence constraints, the best linear programming-based approach finds optimal solutions in 78\percent of cases. Our results demonstrate that careful experimentation can help lead the way to high quality algorithms, even for difficult optimization problems. Received October 30, 1998; revised March 28, 2001.     

A time-decomposition method for sequence-dependent setup schedulingunder pressing demand conditions

This paper develops a method for continuous-time scheduling problems in flexible manufacturing systems. The objective is to find the optimal schedule subject to different production constraints: precedence constraints (bills of materials), sequence-dependent setup times, finite machine capacities, and pressing demands. Differential equations along with mixed constraints are used to model production and setup processes in a canonical form of optimal control. The proposed approach to the search for the optimal solution is based on the maximum principle analysis and time-decomposition methodology. To develop fast near-optimal solution algorithms for sizable problems, we replace the general problem with a number of sub-problems so that solving them iteratively provides tight lower and upper estimates of the optimal solution     

Task scheduling with precedence constraints to minimize the total completion time

The authors study the problem of scheduling a set of tasks with known execution times and arbitrary precedence constraints to computing systems. The objective function used to measure the performance of a schedule in this paper is the sum of completion times of all tasks, which is called total completion time. Finding the minimum total completion time of tasks with precedence constraints on the uniprocessor system is known to be NP-complete, let alone on the multiprocessor system (Garey and Johnson 1979) Based on the well-known A? algorithm proposed in the field of artificial intelligence (Nilson 1980) two algorithms are developed to solve efficiently the scheduling problems on the uniprocessor system and multiprocessor system. Some evaluation functions are proposed to accelerate the search of an optimal schedule. A table named the backwards range-limited table is used to assist the computation of the evaluation function. Experimental results show that the proposed approaches can achieve the optimal schedule with greatly reduced search tree size, especially when bounding rules are applied.     

Project scheduling under resource constraints: Application of the cumulative global constraint in a decision support framework

This paper concerns project scheduling under resource constraints. Traditionally, the objective is to find a unique solution that minimizes the project makespan, while respecting the precedence constraints and the resource constraints. This work focuses on developing a model and a decision support framework for industrial application of the cumulative global constraint. For a given project scheduling, the proposed approach allows the generation of different optimal solutions relative to the alternate availability of outsourcing and resources. The objective is to provide a decision-maker an assistance to construct, choose, and define the appropriate scheduling program taking into account the possible capacity resources. The industrial problem under consideration is modeled as a constraint satisfaction problem (CSP). It is implemented under the constraint programming language CHIP V5. The provided solutions determine values for the various variables associated to the tasks realized on each resource, as well as the curves with the profile of the total consumption of resources on time.     

Setting due dates to minimize the total weighted possibilistic mean value of the weighted earliness-tardiness costs on a single machine

In this paper, it is investigated how to sequence jobs with fuzzy processing times and predict their due dates on a single machine such that the total weighted possibilistic mean value of the weighted earliness-tardiness costs is minimized. First, an optimal polynomial time algorithm is put forward for the scheduling problem when there are no precedence constraints among jobs. Moreover, it is shown that if general precedence constraints are involved, the problem is NP-hard. Then, four reduction rules are proposed to simplify the constraints without changing the optimal schedule. Based on these rules, an optimal polynomial time algorithm is proposed when the precedence constraint is a tree or a collection of trees. Finally, a numerical experiment is given.     

Scheduling Under Common Due Date, A Single Resource and Precedence Constraints—A Dynamic Approach

This paper discusses dynamic methods for solving a class of multi-project scheduling problems in which rates of job performances are controllable and resources such as money, energy or manpower per time unit, are renewable and continuously divisible. The objective is to complete the projects as close to the common due date as possible. Two different ways of imposing sequential precedence relations between project jobs are explored by formulating two dynamic models and studying their relationships on the optimal solution. Efficient time-decomposition algorithms for finding either globally optimal schedules or lower bound guided near-optimal solutions are suggested and computationally tested.     

基于优先关系的飞机机载设备维修拆卸CPN模型

现有的拆卸Petri网模型用于维修拆卸序列规划时,存在约束关系描述不准确、网系统模型结构复杂等不足.文中根据飞机机载设备维修拆卸的特点,考虑拆卸优先约束关系对拆卸时间的影响,提出了基于拆卸优先约束关系和着色网的DCPN模型.首先建立m维可拆情况下拆卸优先矩阵的生成方法,并改进其取值和表征,解决了设备间约束关系的准确描述问题;然后采用着色网建模方法简化了网系统模型.基于DCPN的可达图和有界、并发、冲突等动态特性,实现了对拆卸序列及其并发操作的自动求解.最后通过实例证明了DCPN模型以及相应的拆卸序列求解方法的正确性.     

Single machine due date assignment scheduling problem with customer service level in fuzzy environment

Due date assignment scheduling problems with deterministic and stochastic parameters have been studied extensively in recent years. In this paper, we consider a single machine due date assignment scheduling problem with uncertain processing times and general precedence constraint among the jobs. The processing times of the jobs are assumed to be fuzzy numbers. We first propose an optimal polynomial time algorithm for the problem without precedence constraints among jobs. Then, we show that if general precedence constraint is involved, the problem is NP-hard. Finally, we show that if the precedence constraint is a tree or a collection of trees, the problem is still polynomially solvable.     

Project scheduling with irregular costs: complexity, approximability, and algorithms

We address a generalization of the classical discrete time-cost tradeoff problem where the costs are irregular and depend on the starting and the completion times of the activities. We present a complete picture of the computational complexity and the approximability of this problem for several natural classes of precedence constraints. We prove that the problem is NP-hard and hard to approximate, even in case the precedence constraints form an interval order. For precedence constraints with bounded height, there is a complexity jump from height one to height two: For height one, the problem is polynomially solvable, whereas for height two, it is NP-hard and APX-hard. Finally, the problem is shown to be polynomially solvable if the precedence constraints have bounded width or are series parallel.Received: 2 February 2004, Published online: 29 October 2004     

Dynamic scheduling of design activities with resource constraints

A design process can be represented as a network of design activities. A number of design projects may be undertaken simultaneously. This paper deals with the problem of scheduling design activities of multiple design projects competing for the limited available resources. The problem of determining a schedule subject to precedence and resource constraints is difficult to solve. It becomes even more complex when unforeseen changes are considered, for example, in the level of resources. Therefore, the scheduling problem is decomposed into a series of multidimensional (multiresource) knapsack problems. Due to high computational complexity of the multidimensional knapsack problem, two solution procedures are proposed     

The total completion time open shop scheduling problem with a given sequence of jobs on one machine

This paper addresses the open shop scheduling problem to minimize the total completion time, provided that one of the machines has to process the jobs in a given sequence. The problem is NP-hard in the strong sense even for the two-machine case. A lower bound is derived based on the optimal solution of a relaxed problem in which the operations on every machine may overlap except for the machine with a given sequence of jobs. This relaxed problem is NP-hard in the ordinary sense, however it can be quickly solved via a decomposition into subset-sum problems. Both heuristic and branch-and-bound algorithm are proposed. Experimental results show that the heuristic is efficient for solving large-scaled problems, and the branch-and-bound algorithm performs well on small-scaled problems.Scope and purposeShop scheduling problems, widely used in the modeling of industrial production processes, are receiving an increasing amount of attention from researchers. To model practical production processes more closely, additional processing restrictions can be introduced, e.g., the resource constraints, the no-wait in process requirement, the precedence constraints, etc. This paper considers the total completion time open shop scheduling problem with a given sequence of jobs on one machine. This model belongs to a new class of shop scheduling problems under machine-dependent precedence constraints. This problem is NP-hard in the strong sense. A heuristic is proposed to efficiently solve large-scaled problems and a branch-and-bound algorithm is presented to optimally solve small-scaled problems. Computational experience is also reported.     

A Variational Maximum Principle for Classical Optimal Control Problems

A necessary condition of optimality—the variational maximum principle—for continuous dynamic optimization problems under linear unbounded control and trajectory terminal constraints is studied. It holds for optimal control problems, which are characterized by the commutativity of vector fields corresponding to the components of a linear control in the dynamic system (Frobenius-type condition). For these problems, the variational maximum principle, being a first-order necessary condition of optimality, is a stronger version of the Pontryagin maximum principle. Examples are given.     

混合优先约束下带模糊交货期的单机调度问题的研究

讨论了一类模糊交货期和混合优先约束下的单机调度问题．模糊交货期表示对任务完成时间的满意程度；混合优先约束包括普通优先关系和模糊优先关系，模糊优先关系反映了对任务间优先次序的满意程度．调度的目的是同时最大化模糊交货期和混合优先约束的最小满意程度．对于上述双目标函数调度问题，通过搜索非支配解，得到最优调度．