A new dynamic programming formulation for scheduling independent tasks with common due date on parallel machines

This paper deals with a scheduling problem of independent tasks with common due date where the objective is to minimize the total weighted tardiness. The problem is known to be ordinary NP-hard in the case of a single machine and a dynamic programming algorithm was presented in the seminal work of Lawler and Moore [E.L. Lawler, J.M. Moore, A functional equation and its application to resource allocation and sequencing problems, Management Science 16 (1969) 77–84]. In this paper, this algorithm is described and discussed. Then, a new dynamic programming algorithm is proposed for solving the single machine case. These methods are extended for solving the identical and uniform parallel-machine scheduling problems.     

Stochastic dual dynamic programming applied to nonconvex hydrothermal models

In this paper we apply stochastic dual dynamic programming decomposition to a nonconvex multistage stochastic hydrothermal model where the nonlinear water head effects on production and the nonlinear dependence between the reservoir head and the reservoir volume are modeled. The nonconvex constraints that represent the production function of a hydro plant are approximated by McCormick envelopes. These constraints are split into smaller regions and the McCormick envelopes are used for each region. We use binary variables for this disjunctive programming approach and solve the problem with a decomposition method. We resort to a variant of the L-shaped method for solving the MIP subproblem with binary variables at any stage inside the stochastic dual dynamic programming algorithm. A realistic large-scale case study is presented.     

工件优先级图为非连接图且含环的单机总加权拖期调度问题

为满足实际生产环境对工件加工顺序和工件到达时间的要求,提出了具有新特征的单机总加权拖期调度问题,其特点体现在:工件有动态到达时间,且由工件优先级关系构成的优先级图为非连接图且存在环的情况,对该问题建立数学规划模型,在扩展Tang和Xuan等的基础上,提出了结合双向动态规划的拉格朗日松弛算法求解该问题。在该算法的设计中,提出双向动态规划算法求解拉格朗日松弛问题,使得它可处理优先级图中一个工件可能有多个紧前或紧后工件的情况,采用次梯度算法更新拉格朗日乘子,基于拉格朗日松弛问题的解设计启发式算法构造可行解。实验测试结果显示,所设计的拉格朗日松弛算法能够在较短的运行时间内得到令人满意的近优解,为更复杂的调度问题的求解提供了思路。     

Optimum split trees

A split tree is a special kind of a binary search tree introduced by B. A. Sheil (Comm. ACM21 (1978), 947–958). He conjectured that constructing an optimum split tree is an intractable problem since there is a difficulty in applying the dynamic programming technique. It is realized that the difficulty arises since top down decisions are required while applying the bottom up dynamic programming technique. It is demonstrated that it is possible in this case to overcome such a difficulty, and a polynomial algorithm for constructing an optimum split tree is presented. This algorithm incorporates top down decisions into a dynamic programming procedure similar to D. E. Knuth's (Acta Inform. 1 (1971), 14–25) algorithm for constructing an optimum binary search tree. The probabilities of unsuccessful searches are taken into account. A modification for the case that equiprobable keys are permitted is discussed.     

One-level reformulation of the bilevel Knapsack problem using dynamic programming

In this paper, we consider the Bilevel Knapsack Problem (BKP), which is a hierarchical optimization problem in which the feasible set is determined by the set of optimal solutions for a parametric Knapsack Problem. We introduce a new reformulation of the BKP into a one-level integer programming problem using dynamic programming. We propose an algorithm that allows the BKP to be solved exactly in two steps. In the first step, a dynamic programming algorithm is used to compute the set of follower reactions to leader decisions. In the second step, an integer problem that is equivalent to the BKP is solved using a branch-and-bound algorithm. Numerical results are presented to show the performance of our method.     

A Note on a Two-dimensional Dynamic Programming Problem

A two-dimensional dynamic programming problem is posed. By relaxing some of the restraints on the problem it is reduced to a standard dynamic programming problem. Results are quoted from a particular case study.     

Dynamic Models for Sales Promotion Policies

This paper presents several models for decisions on budget and operational details (price-off and duration) of a sales promotion for consuLmer goods industries and retail sector. The solutions to the one-period problem are generalized using the dynamic programming methods to the more common case of a multi-period-situation. Several special cases of the general dynamic programming model are discussed along with numerical examples. Finally, the ways of utilizing historical data for an ongoing firm for estimating the parameters of the models are presented.     

Book review of advances in gabor analysis,applied and numerical harmonic analysis,Hans G. Feichtinger and Thomas Strohmer (Eds.), Birkhäuser,Boston-Basel-Berlin, 2002, 356 pages. ISBN 0-8176-4239-0

In some recent publications it was shown that certain stationary stochastic dynamic programming problems with general state and action spaces can be solved by generalized linear programming. It Is the main aim of the present paper to demonstrate that a similar linear programming approach is feasible even in the non-stationary case. For this end, we formulate a programming problem (D^?) and show that (D^?) is equivalent to the problem of finding a p=optimal policy for the stochastic dynamic program, whereas a modification of (D^?) turns out to be the dual program of a pair of general linear programs.     

Single vehicle routing with a predefined customer sequence and multiple depot returns

The optimal routing of a single vehicle with limited capacity that delivers one product to n clients according to a predefined client sequence can be determined using dynamic programming. In the present paper we propose and investigate three practical variations of this problem: (i) the case of multiple-product deliveries when each product is stored in its own compartment in the vehicle, (ii) the case of multiple-product deliveries when all products are stored together in the vehicle’s single compartment, and (iii) the case in which the vehicle picks up from and delivers a single product to each customer. Suitable dynamic programming algorithms that find the optimal routing of the vehicle are developed for each case. The efficiency of the algorithms is studied by solving large problem sets.     

Batch Delivery Scheduling on a Single Machine

The problem of partitioning a set of independent and simultaneously available jobs into batches and sequencing them for processing on a single machine is presented. Jobs in the same batch are to be delivered together, upon completion of the last job in the batch. Jobs finished before this time have to wait until delivery. There are a delivery cost depending on the number of batches formed and an earliness cost for jobs finished before delivery. The dynamic programming approach to minimizing the total cost is considered, yielding two pseudopolynomial algorithms when the number of batches has a fixed upper bound. A polynomial algorithm for a special case of the problem is also presented.     

Solving a multiobjective traveling salesman problem by dynamic programming

In this paper Klötzler's method of multiobjective dynamic programming is applied to the solution of a two-dimensional traveling salesman problem. In this way Bellman's and Held/Karp's dynamic programming approach to one-dimensional traveling salesman problems is extended to the multiobjective case.     

The geometric generalized minimum spanning tree problem with grid clustering

This paper is concerned with a special case of the generalized minimum spanning tree problem. The problem is defined on an undirected graph, where the vertex set is partitioned into clusters, and non-negative costs are associated with the edges. The problem is to find a tree of minimum cost containing at least one vertex in each cluster. We consider a geometric case of the problem where the graph is complete, all vertices are situated in the plane, and Euclidean distance defines the edge cost. We prove that the problem is strongly -hard even in the case of a special structure of the clustering called grid clustering. We construct an exact exponential time dynamic programming algorithm and, based on this dynamic programming algorithm, we develop a polynomial time approximation scheme for the problem with grid clustering.     

Dynamic programming and minimum risk paths

This paper addresses the problem of computing minimum risk paths by taking as objective the expected accident cost. The computation is based on a dynamic programming formulation which can be considered an extension of usual dynamic programming models: path costs are recursively computed via functions which are assumed to be monotonic. A large part of the paper is devoted to analyze in detail this formulation and provide some new results. Based on the dynamic programming model a linear programming model is also presented to compute minimum risk paths. This formulation turns out to be useful in solving a biobjective version of the problem, in which also expected travel length is taken into consideration. This leads to define nondominated mixed strategies. Finally it is shown how to extend the basic updating device of dynamic programming in order to enumerate all nondominated paths.     

Solution procedures for sizing of warehouses

In the past, researchers presented a linear programming formulation for the economic sizing of warehouses when demand is highly seasonal and public warehouse space is available on a monthly basis. The static model was extended for the dynamic sizing problem in which the warehouse size is allowed to change over time. By applying simplex routine, the optimal size of the warehouse to be constructed could be determined. In this paper, an alternative and simple method of arriving at an optimal solution for the static problem is given. Three extensions of the static model are given. These extensions involve costs varying over time, economies of scale in capital expenditure and/or operating cost and stochastic version. The dynamic warehouse sizing problem is shown to be a network flow problem which could be solved by using network flow algorithms. The structure of an optimal solution is also given. The concave cost version of the dynamic warehouse sizing problem is also discussed and it is shown that this problem can be solved efficiently using dynamic programming.     

Scheduling with batch setup times and earliness-tardiness penalties

We consider a scheduling model in which several batches of jobs need to be processed by a single machine. During processing, a setup time is incurred whenever there is a switch from processing a job in one batch to a job in another batch. All the jobs in the same batch have a common due date that is either externally given as an input data or internally determined as a decision variable. Two problems are investigated. One problem is to minimize the total earliness and tardiness penalties provided that each due date is externally given. We show that this problem is NP-hard even when there are only two batches of jobs and the two due dates are unrestrictively large. The other problem is to minimize the total earliness and tardiness penalties plus the total due date penalty provided that each due date is a decision variable. We give some optimality properties for this problem with the general case and propose a polynomial dynamic programming algorithm for solving this problem with two batches of jobs. We also consider a special case for both of the problems when the common due dates for different batches are all equal. Under this special case, we give a dynamic programming algorithm for solving the first problem with an unrestrictively large due date and for solving the second problem. This algorithm has a running time polynomial in the number of jobs but exponential in the number of batches.     

Dynamic Programming State-Space Relaxation for Single-Machine Scheduling

The problem of sequencing jobs on a single machine to minimize total cost is considered. Machine capacity constraints require that, at any time, at most one job is processed. Also, no machine idle-time between processing jobs is allowed. In contrast to most research, it is not assumed that the cost is a non-decreasing function of completion time. A dynamic programming formulation of the problem is presented. Since the number of states required by this formulation is prohibitively large, the possibilities for branch and bound algorithms are explored. It is shown that the dynamic programming formulation can be relaxed by mapping the state-space onto a smaller state-space and performing the recursion on this smaller state-space, thereby giving a lower bound. Techniques for improving this lower bound through the use of penalties and through the use of state-space modifiers are discussed. Computational results are presented for the problem in which each job has a due date, and the objective is to minimize the sum of holding costs for jobs completed before their due date and tardiness costs for jobs completed after their due date.     

Identical parallel-machine scheduling under availability constraints to minimize the sum of completion times

In this paper, we study the identical parallel machine scheduling problem with a planned maintenance period on each machine to minimize the sum of completion times. This paper is a first approach for this problem. We propose three exact methods to solve the problem at hand: mixed integer linear programming methods, a dynamic programming based method and a branch-and-bound method. Several constructive heuristics are proposed. A lower bound, dominance properties and two branching schemes for the branch-and-bound method are presented. Experimental results show that the methods can give satisfactory solutions.     

A dynamic approach to multiple-objective resource allocation problem

A new approach using dynamic programming is developed for solving the multiple-objective resource allocation problem. There are two key issues being addressed in this approach. The first one is to develop a methodology of fuzzy evaluation and fuzzy optimization for multiple-objective systems. The procedure of getting the marginal evaluation for each objective and aggregating them synthetically into a global evaluation is presented in this paper. The second one is to design a dynamic optimization algorithm by incorporating the method of fuzzy evaluation and fuzzy optimization with the conventional dynamic programming technique. A characteristic feature of the approach presented is that various objectives are synthetically considered by the fuzzy systematic technique instead of the frequently employed weighted-average method. Numeric examples are also given to clarify the developed approach and to demonstrate its effectiveness.     

Lower bound on size of branch-and-bound trees for solving lot-sizing problem

We show that there exists a family of instances of the lot-sizing problem, such that any branch-and-bound tree that solves them requires an exponential number of nodes, even in the case when the branchings are performed on general split disjunctions. This result is of interest since there exists dynamic programming algorithm that solves lot-sizing in polynomial-time. To the best of our knowledge, this is the first study that shows that dynamic programming can be exponentially faster than branch-and-bound.     

Dynamic programming based metaheuristics for the dial-a-ride problem

The organization of a specialized transportation system to perform transports for elderly and handicapped people is usually modeled as dial-a-ride problem. Users place transportation requests with specified pickup and delivery locations and times. The requests have to be completed under user inconvenience considerations by a specified fleet of vehicles. In the dial-a-ride problem, the aim is to minimize the total travel times respecting the given time windows, the maximum user ride times, and the vehicle restrictions. This paper introduces a dynamic programming algorithm for the dial-a-ride problem and demonstrates its effective application in (hybrid) metaheuristic approaches. Compared to most of the works presented in literature, this approach does not make use of any (commercial) solver. We present an exact dynamic programming algorithm and a dynamic programming based metaheuristic, which restricts the considered solution space. Then, we propose a hybrid metaheuristic algorithm which integrates the dynamic programming based algorithms into a large neighborhood framework. The algorithms are tested on a given set of benchmark instances from the literature and compared to a state-of-the-art hybrid large neighborhood search approach.