A hybrid simulated annealing for the single-machine capacitated lot-sizing and scheduling problem with sequence-dependent setup times and costs and dynamic release of jobs

作者：Mirabi Mohammad^*

来源：International Journal of Advanced Manufacturing Technology, 2011, 54(9-12): 1109-1119.

DOI：10.1007/s00170-010-2988-5

• Lot sizing
• Scheduling
• Sequence dependent
• Market price
• Directed graph
• Hybrid simulated annealing

Single-machine capacitated lot-sizing and scheduling problem (SMCLSP) is one of the most famous fields of research in scheduling area. What makes this problem particularly difficult to solve in many real situations is large and sequence-dependent setups and also multiple criterions that must be considered. In this paper, such a problem is formulated and a hybrid simulated annealing for this problem is presented. Also, lower bounds are obtained from solving the problem relaxation, and they are compared with the optimal solutions to estimate the goodness of them. As decision criteria, all of important costs imposed by the solution are considered and also infeasible sequences are mentioned. There is a ceiling value for the manufacturer's cost of each job and according to it, some sequences between jobs are maybe infeasible. It showed the superiority of hybrid simulated annealing (HSA) compared with one of the efficient recent heuristics. The average deviation of the HSA from the corresponding optimal solution for small-size problems ranges from 0% to 10% and from the corresponding lower bound ranges for large-size problems ranges from 11% to 21%. The presented HSA is capable to solve large instances that are mostly compatible with the real-world problems.

• 出版日期2011-6