A particle swarm optimization algorithm to minimize the makespan of non-identical parallel batch processing machines.

摘要

Batch processing machines are commonly found in metal working, electronics manufacturing, and chemical processing--to name a few. Scheduling batch processing machines is not trivial even for makespan objective. This research is aimed at minimizing the makespan of a set of non-identical batch processing machines. The processing time and size of each job is known. The batch processing machine can process a batch of jobs as long as the total size of all the jobs in a batch does not exceed the machine capacity. The capacity of each machine is non-identical. Once the jobs are batched, the batch processing time is equal to the longest processing time of all the jobs in the batch.;The problem under study is NP-hard. The computational time required to solve mathematical formulations of the problem under study is prohibitively long for even modest size instances (i.e. with 20 jobs or more). In order to solve large problem instances effectively and efficiently, a Particle Swarm Optimization (PSO) solution approach is developed and implemented in MATLAB.;The solution obtained from PSO is compared to a commercial solver used to solve the mathematical formulation developed for the problem under study. A thorough experimental study was conducted to evaluate the solution quality of PSO. For smaller problem instances (i.e., with 10 jobs) the solution from PSO and the commercial solver are identical. However, for larger problem instances (i.e., 50 jobs or more) the solution quality of PSO is better than the commercial solver. Additionally, the computation time required by PSO is very short compared to the commercial solver.;The experimental study conducted indicates that PSO can prescribe good quality solutions in less time. This solution approach is feasible for practical implementations. PSO also requires fewer parameters to tune compared to other meta-heuristics. The proposed solution approach can help schedulers to schedule the batch processing machines more efficiently.