A Bi-criterion Simulated Annealing Method for a Single Batch-processing Machine Scheduling Problem with Dynamic Job Release Times

Ya-Chih TSAI, Hui-Mei WANG, Fuh-Der CHOU


This paper is motivated by a sterilization operation in a professional waste disposal services, and models the operation as the problem of single batch-processing machine (BPM) scheduling with the objectives of minimizing the makespan and the total weighted number of tardy orders that has not been considered in the literature. The considered problem is NP-hard such that two simulated annealing algorithms (SA1 and SA2) are developed in this work. SA1 uses multi-search directions to find Pareto-optimal solutions by eleven combinations of weights, as to SA2 applied the SMOSA of Suman to solve the considered problem. A computational experiment is conducted and the solutions for each instance obtained by SA1 and SA2 respectively are compared. Computational results reveal that SA1 is significantly better than SA2 because SA1 changes different search directions by two parameters.


Single batch-processing machine, Simulated annealing, Sterilization operation, Scheduling


Full Text:



  • There are currently no refbacks.