Multi-Objective Optimization Methods For Multi-Customer Batch Processing Machines

The scheduling problem on batch processing machine (BPM) is an important problem in the research of scheduling problem. Different from the classic scheduling problem, the BPM is capable of processing several jobs simultaneously in a batch. The problems studied in this paper have two customers, each with a set of jobs, the customers have to schedule their jobs on a common batch processing resource, and each customer wishes to minimize an objective function which depends on its own jobs’completion times. In multi-customer batch scheduling problem, a variety of scheduling schemes can be generated based on different priorities. Therefore, not only arranging the jobs from different customers into batches, but also determining the processing sequence of batches on the machines should be considered.The research focuses on the two-customer batch scheduling with non-identical Jobs and designing of efficient algorithms to search for the Pareto optimal solutions, some multi-objective optimization algorithms for solving different types of two-customer batch processing machine problems were proposed. Specifically, the main researches include:(1) Two-customer batch scheduling with non-identical job sizes and identical objective functions was considered on a single machine. The mathematic model of the problem was constructed. Three heuristic rules used to determine the processing sequence of batches were proposed according to three different optimization objectives, minimize makespan, minimize the maximum tardiness and minimize the total completion time. For the case that the objective functions of two customers are both minimize makespan, a multi-objective ant colony optimization (MOACO) approach guided by heuristic information that was constructed considering the waste of time and space was presented. An external set (ES) used to store the non-dominated solutions was proposed to update the Pheromone Trail and ensure the efficiency. Two well-known multi-objective optimization approaches, namely, Non-dominated sorting genetic algorithm-Ⅱ (NSGA-Ⅱ) and strength Pareto evolutionary algorithm2(SPEA2) based evolutionary algorithms were both proposed to compare with MOACO by computational experiments.(2) Two-customer batch scheduling with non-identical job sizes and non-identical objective functions was considered on a single machine. The mathematic model of the problem was established. A two-set earliest due date (TSEDD) heuristic rule was next proposed to determine the processing sequence of batches, then a heuristics algorithm and a constructive based MOACO were further presented using TSEDD to minimize the makespan for the first customer and minimize the maximum lateness for the second one. Both two approaches were compare with NSGA-II based evolutionary algorithm by computational experiments in Pareto solution quality, solution variety and time consuming.(3) Two-customer batch scheduling with non-identical job sizes and non-identical objective functions was considered on a parallel machine environment. The mathematic model of the problem was given. A heuristic rule was proposed to determine the processing sequence of batches. Three multi-objective optimization approaches, namely, MOACO, NSGA-II and SPEA2based evolutionary algorithms were proposed and compared using different performance metrics.