This paper proposes a heuristic algorithm, called list-based squeezing branch and bound algorithm, for solving a machine-fixed, machining-assembly flowshop scheduling problem to minimize makespan. The machine-fixed, m...This paper proposes a heuristic algorithm, called list-based squeezing branch and bound algorithm, for solving a machine-fixed, machining-assembly flowshop scheduling problem to minimize makespan. The machine-fixed, machining-assembly flowshop consists of some parallel two-machine flow lines at a machining stage and one robot at an assembly stage. Since an optimal schedule for this problem is not always a permutation schedule, the proposed algorithm first finds a promising permutation schedule, and then searches better non-permutation schedules near the promising permutation schedule in an enumerative manner by elaborating a branching procedure in a branch and bound algorithm. The results of numerical experiments show that the proposed algorithm can efficiently provide an optimal or a near-optimal schedule with high accuracy such as mean relative error being less than 0.2% and the maximum relative error being at most 3%.展开更多
This paper presents the two-machine flowshop group scheduling problem with the optimal objective of maximum lateness. A dominance rule within group and a dominance rule between groups are established. These dominance ...This paper presents the two-machine flowshop group scheduling problem with the optimal objective of maximum lateness. A dominance rule within group and a dominance rule between groups are established. These dominance rules along with a previously established dominance rule are used to develop a heuristic algorithm. Experimental results are given and analyzed.展开更多
Lot scheduling problem with idle time transfer between processes to minimize mean flow time is very important because to minimize mean flow time is to minimize work in process. But the problem is NP hard and no polyn...Lot scheduling problem with idle time transfer between processes to minimize mean flow time is very important because to minimize mean flow time is to minimize work in process. But the problem is NP hard and no polynomial algorithm exists to guarantee optimal solution. Based the analysis the mathematical structure of the problem, the paper presents a new heuristic algorithm. Computer simulation shows that the proposed heuristic algorithm performs well in terms of both quality of solution and execution speed.展开更多
This study examines the multicriteria scheduling problem on a single machine to minimize three criteria: the maximum cost function, denoted by maximum late work (V<sub>max</sub>), maximum tardy job, denote...This study examines the multicriteria scheduling problem on a single machine to minimize three criteria: the maximum cost function, denoted by maximum late work (V<sub>max</sub>), maximum tardy job, denoted by (T<sub>max</sub>), and maximum earliness (E<sub>max</sub>). We propose several algorithms based on types of objectives function to be optimized when dealing with simultaneous minimization problems with and without weight and hierarchical minimization problems. The proposed Algorithm (3) is to find the set of efficient solutions for 1//F (V<sub>max</sub>, T<sub>max</sub>, E<sub>max</sub>) and 1//(V<sub>max</sub> + T<sub>max</sub> + E<sub>max</sub>). The Local Search Heuristic Methods (Descent Method (DM), Simulated Annealing (SA), Genetic Algorithm (GA), and the Tree Type Heuristics Method (TTHM) are applied to solve all suggested problems. Finally, the experimental results of Algorithm (3) are compared with the results of the Branch and Bound (BAB) method for optimal and Pareto optimal solutions for smaller instance sizes and compared to the Local Search Heuristic Methods for large instance sizes. These results ensure the efficiency of Algorithm (3) in a reasonable time.展开更多
Aiming at the flexible flowshop group scheduling problem,taking sequence dependent setup time and machine skipping into account, a mathematical model for minimizing makespan is established,and a hybrid differential ev...Aiming at the flexible flowshop group scheduling problem,taking sequence dependent setup time and machine skipping into account, a mathematical model for minimizing makespan is established,and a hybrid differential evolution( HDE) algorithm based on greedy constructive procedure( GCP) is proposed,which combines differential evolution( DE) with tabu search( TS). DE is applied to generating the elite individuals of population,while TS is used for finding the optimal value by making perturbation in selected elite individuals. A lower bounding technique is developed to evaluate the quality of proposed algorithm. Experimental results verify the effectiveness and feasibility of proposed algorithm.展开更多
This paper deals with the problem of project scheduling subject to multiple execution modes with non-renewable resources, and a model that handles some of monetary issues in real world applications.The objective is to...This paper deals with the problem of project scheduling subject to multiple execution modes with non-renewable resources, and a model that handles some of monetary issues in real world applications.The objective is to schedule the activities to maximize the expected net present value(NPV) of the project, taking into account the activity costs, the activity durations, and the cash flows generated by successfully completing an activity.Owing to the combinatorial nature of this problem, the current study develops a hybrid of branch-and-bound procedure and memetic algorithm to enhance both mode assignment and activity scheduling.Modifications for the makespan minimization problem have been made through a set of benchmark problem instances.Algorithmic performance is rated on the maximization of the project NPV and computational results show that the two-phase hybrid metaheuristic performs competitively for all instances of different problem sizes.展开更多
A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet...A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet assignment, subject to the constraints of coverage, aircraft flow balance, fleet size, aircraft availability, aircraft usage, flight restriction, aircraft seat capacity, and stopover. Then the branch-and-bound algorithm based on special ordered set was applied to solve the model. At last, a real- wofld case study on an airline with 5 fleets, 48 aircrafts and 1 786 flight legs indicated that the profit increase was ￥ 1 591276 one week and the running time was no more than 4 rain, which shows that the model and algorithm are fairly good for domestic airline.展开更多
This article investigates identical parallel machines scheduling with family setup times. The objective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a co...This article investigates identical parallel machines scheduling with family setup times. The objective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.展开更多
文摘This paper proposes a heuristic algorithm, called list-based squeezing branch and bound algorithm, for solving a machine-fixed, machining-assembly flowshop scheduling problem to minimize makespan. The machine-fixed, machining-assembly flowshop consists of some parallel two-machine flow lines at a machining stage and one robot at an assembly stage. Since an optimal schedule for this problem is not always a permutation schedule, the proposed algorithm first finds a promising permutation schedule, and then searches better non-permutation schedules near the promising permutation schedule in an enumerative manner by elaborating a branching procedure in a branch and bound algorithm. The results of numerical experiments show that the proposed algorithm can efficiently provide an optimal or a near-optimal schedule with high accuracy such as mean relative error being less than 0.2% and the maximum relative error being at most 3%.
文摘This paper presents the two-machine flowshop group scheduling problem with the optimal objective of maximum lateness. A dominance rule within group and a dominance rule between groups are established. These dominance rules along with a previously established dominance rule are used to develop a heuristic algorithm. Experimental results are given and analyzed.
文摘Lot scheduling problem with idle time transfer between processes to minimize mean flow time is very important because to minimize mean flow time is to minimize work in process. But the problem is NP hard and no polynomial algorithm exists to guarantee optimal solution. Based the analysis the mathematical structure of the problem, the paper presents a new heuristic algorithm. Computer simulation shows that the proposed heuristic algorithm performs well in terms of both quality of solution and execution speed.
文摘This study examines the multicriteria scheduling problem on a single machine to minimize three criteria: the maximum cost function, denoted by maximum late work (V<sub>max</sub>), maximum tardy job, denoted by (T<sub>max</sub>), and maximum earliness (E<sub>max</sub>). We propose several algorithms based on types of objectives function to be optimized when dealing with simultaneous minimization problems with and without weight and hierarchical minimization problems. The proposed Algorithm (3) is to find the set of efficient solutions for 1//F (V<sub>max</sub>, T<sub>max</sub>, E<sub>max</sub>) and 1//(V<sub>max</sub> + T<sub>max</sub> + E<sub>max</sub>). The Local Search Heuristic Methods (Descent Method (DM), Simulated Annealing (SA), Genetic Algorithm (GA), and the Tree Type Heuristics Method (TTHM) are applied to solve all suggested problems. Finally, the experimental results of Algorithm (3) are compared with the results of the Branch and Bound (BAB) method for optimal and Pareto optimal solutions for smaller instance sizes and compared to the Local Search Heuristic Methods for large instance sizes. These results ensure the efficiency of Algorithm (3) in a reasonable time.
基金Shanghai Municipal Natural Science Foundation of China(No.10ZR1431700)
文摘Aiming at the flexible flowshop group scheduling problem,taking sequence dependent setup time and machine skipping into account, a mathematical model for minimizing makespan is established,and a hybrid differential evolution( HDE) algorithm based on greedy constructive procedure( GCP) is proposed,which combines differential evolution( DE) with tabu search( TS). DE is applied to generating the elite individuals of population,while TS is used for finding the optimal value by making perturbation in selected elite individuals. A lower bounding technique is developed to evaluate the quality of proposed algorithm. Experimental results verify the effectiveness and feasibility of proposed algorithm.
文摘This paper deals with the problem of project scheduling subject to multiple execution modes with non-renewable resources, and a model that handles some of monetary issues in real world applications.The objective is to schedule the activities to maximize the expected net present value(NPV) of the project, taking into account the activity costs, the activity durations, and the cash flows generated by successfully completing an activity.Owing to the combinatorial nature of this problem, the current study develops a hybrid of branch-and-bound procedure and memetic algorithm to enhance both mode assignment and activity scheduling.Modifications for the makespan minimization problem have been made through a set of benchmark problem instances.Algorithmic performance is rated on the maximization of the project NPV and computational results show that the two-phase hybrid metaheuristic performs competitively for all instances of different problem sizes.
基金The National Natural Science Foundationof China (70473037)
文摘A 0-1 integer programming model for weekly fleet assignment was put forward based on linear network and weekly flight scheduling in China. In this model, the objective function is to maximize the total profit of fleet assignment, subject to the constraints of coverage, aircraft flow balance, fleet size, aircraft availability, aircraft usage, flight restriction, aircraft seat capacity, and stopover. Then the branch-and-bound algorithm based on special ordered set was applied to solve the model. At last, a real- wofld case study on an airline with 5 fleets, 48 aircrafts and 1 786 flight legs indicated that the profit increase was ￥ 1 591276 one week and the running time was no more than 4 rain, which shows that the model and algorithm are fairly good for domestic airline.
基金supported in part by Regional Council of Champagne-Ardenne(France).
文摘This article investigates identical parallel machines scheduling with family setup times. The objective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.
