PSO algorithm for a scheduling parallel unit batch process with batching

ABSTRACT

In this paper, a parallel unit batch process scheduling problem (PBPSP) integrating batching decision is investigated. The batch scheduling problem is to convert the demands for products into sets of batches and schedule these batches on the units such that makespan is minimized. We propose a Particle Swarm Optimization (PSO) algorithm to solve this problem where a novel particle solution representation is designed for representing a batching scheme for PBPSP and a scale-based repair procedure is introduced to make particles feasible. In addition, the proposed PSO is combined with a relatively current evolutionary algorithm known as Differential Evolution (DE) for enhance the performance of PSO. A mixed integer linear programming (MILP) formulation is also given and used to calculate a lower bound for comparison with the PSO solutions. Computational results indicated the validity and effectiveness of the proposed PSO.

REFERENCES

• 1: Grunow, M., Günther, H., and Lehmann, M. 2002. Campaign planning for multi-stage batch processes in the chemical industry. OR. Spec. 24, 281--314.
• 2: Méndez, C. A., Cerdá, J., Grossmann, I. E., Harjunkoski, I., and Fahl, M. 2006. State-of-the-art review of optimization methods for short-term scheduling of batch processes. Comput. Chem. Eng. 30 (No.6-7), 913---946.
• 3: Kallrath, J. 2002. Planning and scheduling in the process industry. OR. Spec. 24, 219--250.
• 4: Floudas, C. A., and Lin, X. 2004. Continuous-time versus discrete-time approaches for scheduling of chemical processes: a review. Comput. Chem. Eng. 28 (No.11), 2109--2129.
• 5: Kennedy, J., and Eberhart, R. 1995. Particle swarm optimization. Proceedings of IEEE-ICNN, Piscataway, NJ, 1942--1948.
• 6: Abido, M. A. 2002. Optimal power flow using particle swarm optimization. Electr. Power Energy Syst. 24, 563--571.
• 7: Brandstatter, B., and Baumgartner, U. 2002. Particle swarm optimization: mass-spring system analogon. IEEE Trans. Magn. 38, 997--1000.
• 8: Salman, A., Ahmad, I., and Al-Madani, S. 2003. Particle swarm optimization for task assignment problem. Microprocessors Microsyst. 26, 363--371.
• 9: Clerc, M. 2004. Discrete particle swarm optimization, Illustrated by the travelling salesman problem. New Optimization Techniques in Engineering, Springer: Heidelberg, Germany, 219--239.
• 10: Eberhart, R. C., and Shi, Y. H. 1998. Evolving artificial neural networks. Proceedings of ICNNB, Beijing, P.R. China, 5--13.
• 11: Rainer Storn , Kenneth Price, Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, v.11 n.4, p.341-359, December 1997 [doi>10.1023/A:1008202821328]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

Additional Classification:
  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Global optimization; Integer programming

General Terms:
Algorithms

Keywords:
MILP, batching, differential evolution, particle swarm optimization, scheduling