This paper considers a project scheduling problem with the objective of minimizing resource availability costs appealed to finish al activities before the deadline. There are finish-start type precedence relations amo...This paper considers a project scheduling problem with the objective of minimizing resource availability costs appealed to finish al activities before the deadline. There are finish-start type precedence relations among the activities which require some kinds of renewable resources. We predigest the process of sol-ving the resource availability cost problem (RACP) by using start time of each activity to code the schedule. Then, a novel heuris-tic algorithm is proposed to make the process of looking for the best solution efficiently. And then pseudo particle swarm optimiza-tion (PPSO) combined with PSO and path relinking procedure is presented to solve the RACP. Final y, comparative computational experiments are designed and the computational results show that the proposed method is very effective to solve RACP.展开更多
The bottleneck analysis of the minimum coat problem for the generalized netwok(MCPGN) is discussed.The analysis is based on the network simplex algorithm,which gains negative cost graphs by constructing augmented fore...The bottleneck analysis of the minimum coat problem for the generalized netwok(MCPGN) is discussed.The analysis is based on the network simplex algorithm,which gains negative cost graphs by constructing augmented forest structure,then augments flows on the negative cost graphs until the optimal revolution is gained Bottleneck structure is presented after analyzing the augmented forest structure.The negative cost augmented graphs are constructed with the bottleneck structure.The arcs that block the negative cost augmented graph are the elements of the bottleneck.The bottleneck analysis for the generalized circulation problem,the minimum circulation problem and the circulation problem are discussed respectively as the basal problems,then that for MCPGN is achieved.An example is presented at the end.展开更多
This paper proposes a nonmonotonic backtracking trust region algorithm via bilevel linear programming for solving the general multicommodity minimal cost flow problems.Using the duality theory of the linear programmin...This paper proposes a nonmonotonic backtracking trust region algorithm via bilevel linear programming for solving the general multicommodity minimal cost flow problems.Using the duality theory of the linear programming and convex theory,the generalized directional derivative of the general multicommodity minimal cost flow problems is derived.The global convergence and superlinear convergence rate of the proposed algorithm are established under some mild conditions.展开更多
In this paper, two new sandwich algorithms for the convex curve approximation are introduced. The proofs of the linear convergence property of the first method and the quadratic convergence property of the second meth...In this paper, two new sandwich algorithms for the convex curve approximation are introduced. The proofs of the linear convergence property of the first method and the quadratic convergence property of the second method are given. The methods are applied to approximate the efficient frontier of the stochastic minimum cost flow problem with the moment bicriterion. Two numerical examples including the comparison of the proposed algorithms with two other literature derivative free methods are given.展开更多
This paper concerns optimal investment problem with proportional transaction costs and finite time horizon based on exponential utility function. Using a partial differential equation approach, we reveal that the prob...This paper concerns optimal investment problem with proportional transaction costs and finite time horizon based on exponential utility function. Using a partial differential equation approach, we reveal that the problem is equivalent to a parabolic double obstacle problem involving two free boundaries that correspond to the optimal buying and selling policies. Numerical examples are obtained by the binomial method.展开更多
In this paper,a new price is given to the online decision maker at the beginning of each day.The trader must decide how many items to purchase according to the current price.We present three variants and an online alg...In this paper,a new price is given to the online decision maker at the beginning of each day.The trader must decide how many items to purchase according to the current price.We present three variants and an online algorithm based on cost function.The competitive ratio of the online algorithm is given for each variant,which is a performance measure of an online algorithm.More importantly,we show that the online algorithm is optimal.展开更多
Petrol is a kind of strategic natural resources. Provide legitimate transportation plans for the petrol secondary distribution are the key links to guarantee the petrol provision. If the total supply is insufficient, ...Petrol is a kind of strategic natural resources. Provide legitimate transportation plans for the petrol secondary distribution are the key links to guarantee the petrol provision. If the total supply is insufficient, some petrol stations can’t avoid shortage because their demands could not be met. So the shortage cost will appear. This paper studies the problem of how to arrange the transportation plan in order to minimize the total cost when the total volume of supply is insufficient. Given the storage volume, the sales rate and the unit shortage cost of every petrol station, considering the full loading constraints of the compartment vehicle, a mixed integer programming model for minimizing the total cost of petrol secondary distribution is established. A Lingo program is compiled for solving the model. Finally, simulation on an example has been done and a reasonable transportation plan is obtained. The model and algorithm in this paper can provide a theoretical basis for dispatching department to make transportation plan.展开更多
We reduce lot sizing problem with (a) Set Up, Production, Shortage and Inventory Costs to lot sizing problem with (b) Set Up, Production, and Inventory Costs. For lot sizing problem (as in (b)), Pochet and Wolsey [1] ...We reduce lot sizing problem with (a) Set Up, Production, Shortage and Inventory Costs to lot sizing problem with (b) Set Up, Production, and Inventory Costs. For lot sizing problem (as in (b)), Pochet and Wolsey [1] have given already integral polyhedral with polynomial separation where a linear program yield “integer” solutions. Thus problem (b) which we have created can be more easily solved by methods available in literature. Also with the removal of shortage variables is an additional computational advantage.展开更多
The minimum cost of capacity expansion for time-limited transportation problem on-demand (MCCETLTPD) is to find such a practicable capacity expansion transportation scheme satisfying the time-limited T along with all ...The minimum cost of capacity expansion for time-limited transportation problem on-demand (MCCETLTPD) is to find such a practicable capacity expansion transportation scheme satisfying the time-limited T along with all origins’ supply and all destinations’ demands as well as the expanding cost is minimum. Actually, MCCETLTPD is a balance transportation problem and a variant problem of minimum cost maximum flow problem. In this paper, by creating a mathematical model and constructing a network with lower and upper arc capacities, MCCETLTPD is transformed into searching feasible flow in the constructed network, and consequently, an algorithm MCCETLTPD-A is developed as MCCETLTPD’s solution method basing minimum cost maximum flow algorithm. Computational study validates that the MCCETLTPD-A algorithm is an efficient approach to solving the MCCETLTPD.展开更多
The delay constrained least cost path problem with imprecise delay information is discussed, and a distributed heuristic algorithm without any assumption of imprecise state information is presented. The algorithm empl...The delay constrained least cost path problem with imprecise delay information is discussed, and a distributed heuristic algorithm without any assumption of imprecise state information is presented. The algorithm employs mobile agents to search feasible paths in parallel and requires limited network state information kept at each node. The simulations indicate that the presented solution provides better call acceptance probability and better fairness between short paths and long paths. And the algorithm can tolerate high degree of delay imprecision.展开更多
基金supported by the National Natural Science Foundation of China(7120116671201170)
文摘This paper considers a project scheduling problem with the objective of minimizing resource availability costs appealed to finish al activities before the deadline. There are finish-start type precedence relations among the activities which require some kinds of renewable resources. We predigest the process of sol-ving the resource availability cost problem (RACP) by using start time of each activity to code the schedule. Then, a novel heuris-tic algorithm is proposed to make the process of looking for the best solution efficiently. And then pseudo particle swarm optimiza-tion (PPSO) combined with PSO and path relinking procedure is presented to solve the RACP. Final y, comparative computational experiments are designed and the computational results show that the proposed method is very effective to solve RACP.
基金Supported by the National Natural Science Foundation of China (No. 60174046).
文摘The bottleneck analysis of the minimum coat problem for the generalized netwok(MCPGN) is discussed.The analysis is based on the network simplex algorithm,which gains negative cost graphs by constructing augmented forest structure,then augments flows on the negative cost graphs until the optimal revolution is gained Bottleneck structure is presented after analyzing the augmented forest structure.The negative cost augmented graphs are constructed with the bottleneck structure.The arcs that block the negative cost augmented graph are the elements of the bottleneck.The bottleneck analysis for the generalized circulation problem,the minimum circulation problem and the circulation problem are discussed respectively as the basal problems,then that for MCPGN is achieved.An example is presented at the end.
基金the National Natural Science Foundation of China ( 1 0 4 71 0 94) ,the ScienceFoundation of Shanghai Technical Sciences Committee ( 0 2 ZA1 40 70 ) and the Science Foundation ofShanghai Education Committee( 0 2 DK0 6)
文摘This paper proposes a nonmonotonic backtracking trust region algorithm via bilevel linear programming for solving the general multicommodity minimal cost flow problems.Using the duality theory of the linear programming and convex theory,the generalized directional derivative of the general multicommodity minimal cost flow problems is derived.The global convergence and superlinear convergence rate of the proposed algorithm are established under some mild conditions.
文摘In this paper, two new sandwich algorithms for the convex curve approximation are introduced. The proofs of the linear convergence property of the first method and the quadratic convergence property of the second method are given. The methods are applied to approximate the efficient frontier of the stochastic minimum cost flow problem with the moment bicriterion. Two numerical examples including the comparison of the proposed algorithms with two other literature derivative free methods are given.
基金Supported by the Key Grant Project of Chinese Ministry of Education (NO.309018)National Natural Science Foundation of China (NO.70973104,NO.11171304)Zhejiang Provincial Natural Science Foundation of China (NO.Y6110023)
文摘This paper concerns optimal investment problem with proportional transaction costs and finite time horizon based on exponential utility function. Using a partial differential equation approach, we reveal that the problem is equivalent to a parabolic double obstacle problem involving two free boundaries that correspond to the optimal buying and selling policies. Numerical examples are obtained by the binomial method.
基金Supported by the Natural Science Foundation of China(11201428,11471286,11701518)the Natural Science Foundation of Zhejiang Province(Y6110091)the Graduate Innovation Project of Zhejiang Sci-Tech University(YCX12001,YCX13005)
文摘In this paper,a new price is given to the online decision maker at the beginning of each day.The trader must decide how many items to purchase according to the current price.We present three variants and an online algorithm based on cost function.The competitive ratio of the online algorithm is given for each variant,which is a performance measure of an online algorithm.More importantly,we show that the online algorithm is optimal.
文摘Petrol is a kind of strategic natural resources. Provide legitimate transportation plans for the petrol secondary distribution are the key links to guarantee the petrol provision. If the total supply is insufficient, some petrol stations can’t avoid shortage because their demands could not be met. So the shortage cost will appear. This paper studies the problem of how to arrange the transportation plan in order to minimize the total cost when the total volume of supply is insufficient. Given the storage volume, the sales rate and the unit shortage cost of every petrol station, considering the full loading constraints of the compartment vehicle, a mixed integer programming model for minimizing the total cost of petrol secondary distribution is established. A Lingo program is compiled for solving the model. Finally, simulation on an example has been done and a reasonable transportation plan is obtained. The model and algorithm in this paper can provide a theoretical basis for dispatching department to make transportation plan.
文摘We reduce lot sizing problem with (a) Set Up, Production, Shortage and Inventory Costs to lot sizing problem with (b) Set Up, Production, and Inventory Costs. For lot sizing problem (as in (b)), Pochet and Wolsey [1] have given already integral polyhedral with polynomial separation where a linear program yield “integer” solutions. Thus problem (b) which we have created can be more easily solved by methods available in literature. Also with the removal of shortage variables is an additional computational advantage.
文摘The minimum cost of capacity expansion for time-limited transportation problem on-demand (MCCETLTPD) is to find such a practicable capacity expansion transportation scheme satisfying the time-limited T along with all origins’ supply and all destinations’ demands as well as the expanding cost is minimum. Actually, MCCETLTPD is a balance transportation problem and a variant problem of minimum cost maximum flow problem. In this paper, by creating a mathematical model and constructing a network with lower and upper arc capacities, MCCETLTPD is transformed into searching feasible flow in the constructed network, and consequently, an algorithm MCCETLTPD-A is developed as MCCETLTPD’s solution method basing minimum cost maximum flow algorithm. Computational study validates that the MCCETLTPD-A algorithm is an efficient approach to solving the MCCETLTPD.
文摘The delay constrained least cost path problem with imprecise delay information is discussed, and a distributed heuristic algorithm without any assumption of imprecise state information is presented. The algorithm employs mobile agents to search feasible paths in parallel and requires limited network state information kept at each node. The simulations indicate that the presented solution provides better call acceptance probability and better fairness between short paths and long paths. And the algorithm can tolerate high degree of delay imprecision.