In this paper,we consider the problem of minimizing the total tardiness in a deterministic two-machine permutationflowshop scheduling problem subject to release dates of jobs and known unavailability periods of machin...In this paper,we consider the problem of minimizing the total tardiness in a deterministic two-machine permutationflowshop scheduling problem subject to release dates of jobs and known unavailability periods of machines.The theoretical and practical importance of minimizing tardiness inflowshop scheduling environment has motivated us to investigate and solve this interested two-machine scheduling problem.Methods that solve this important optimality criterion inflowshop environment are mainly heuristics.In fact,despite the N P-hardnessin the strong sense of the studied problem,to the best of our knowledge there are no approximate algorithms(constructive heuristics or metaheuristics)or an algorithm with worst case behavior bounds proposed to solve this problem.Thus,the design of new promising algorithms is desirable.We developfive metaheuristics for the problem under consideration.These metaheuristics are:the Particle Swarm Optimization(PSO),the Differential Evolution(DE),the Genetic Algorithm(GA),the Ant Colony Optimization(ACO)and the Imperialist Competitive Algorithm(ICA).All the proposed metaheuristics are population-based approaches.These metaheuristics have been improved by integrating different local search procedures in order to provide more satisfactory,especially in term of quality solutions.Computational experiments carried out on a large set of randomly generated instances provide evidence that the Imperialist Competitive Algorithm(ICA)records the best performances.展开更多
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.展开更多
To solve the NP-complete no-wait flowshop problems, objective increment properties are analyzed and proved for fundamental operations of heuristics. With these properties, whether a new generated schedule is better or...To solve the NP-complete no-wait flowshop problems, objective increment properties are analyzed and proved for fundamental operations of heuristics. With these properties, whether a new generated schedule is better or worse than the original one is only evaluated by objective increments, instead of completely calculating objective values as the traditional algorithms do, so that the computational time can be considerably reduced. An objective increment-based hybrid genetic algorithm （IGA） is proposed by integrating the genetic algorithm （GA） with an improved various neighborhood search （VNS）as a local search. An initial solution generation heuristic（ISG） is constructed to generate one individual of the initial population. An expectation value-based selection mechanism and a crossover operator are introduced to the mating process. The IGA is compared with the traditional GA and two best-so-far algorithms for the considered problem on 110 benchmark instances. An experimental results show that the IGA outperforms the others in effectiveness although with a little more time consumption.展开更多
文摘In this paper,we consider the problem of minimizing the total tardiness in a deterministic two-machine permutationflowshop scheduling problem subject to release dates of jobs and known unavailability periods of machines.The theoretical and practical importance of minimizing tardiness inflowshop scheduling environment has motivated us to investigate and solve this interested two-machine scheduling problem.Methods that solve this important optimality criterion inflowshop environment are mainly heuristics.In fact,despite the N P-hardnessin the strong sense of the studied problem,to the best of our knowledge there are no approximate algorithms(constructive heuristics or metaheuristics)or an algorithm with worst case behavior bounds proposed to solve this problem.Thus,the design of new promising algorithms is desirable.We developfive metaheuristics for the problem under consideration.These metaheuristics are:the Particle Swarm Optimization(PSO),the Differential Evolution(DE),the Genetic Algorithm(GA),the Ant Colony Optimization(ACO)and the Imperialist Competitive Algorithm(ICA).All the proposed metaheuristics are population-based approaches.These metaheuristics have been improved by integrating different local search procedures in order to provide more satisfactory,especially in term of quality solutions.Computational experiments carried out on a large set of randomly generated instances provide evidence that the Imperialist Competitive Algorithm(ICA)records the best performances.
文摘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.
基金The National Natural Science Foundation of China(No.60504029,60672092)the National High Technology Research and Development Program of China(863Program)(No.2008AA04Z103)
文摘To solve the NP-complete no-wait flowshop problems, objective increment properties are analyzed and proved for fundamental operations of heuristics. With these properties, whether a new generated schedule is better or worse than the original one is only evaluated by objective increments, instead of completely calculating objective values as the traditional algorithms do, so that the computational time can be considerably reduced. An objective increment-based hybrid genetic algorithm （IGA） is proposed by integrating the genetic algorithm （GA） with an improved various neighborhood search （VNS）as a local search. An initial solution generation heuristic（ISG） is constructed to generate one individual of the initial population. An expectation value-based selection mechanism and a crossover operator are introduced to the mating process. The IGA is compared with the traditional GA and two best-so-far algorithms for the considered problem on 110 benchmark instances. An experimental results show that the IGA outperforms the others in effectiveness although with a little more time consumption.
