焼きなまし法を用いたジョブショップスケジユーリングにおける高効率化法の検討

摘要

消費者ニーズの多様化により，少品種大量生産から多品種少量生産への移行が進んでいる.これにともなって，ジョブショップスケジューリングが活発に論じられている.この問題はNP (Non-deterministic Polynomial time)困難であることが知られており，現実規模の問題に対して適正なスケジュールを短時間で求める手法が必要とされている.そのためのアプローチとしてメタヒューリスティタスに注目が寄せられている.%Diversification of customers' needs has caused transition from low-mix high volume manufacturing to high-mix low-volume manufacturing. This transition has increased importance of job-shop scheduling. Because job-shop scheduling problem (JSP) is non-deterministic polynomial time hard, approximate optimization based on meta-heuristics have been actively discussed, and methods using simulated annealing (SA) have been proposed. SA has a disadvantage that good solutions cannot be obtained efficiently if the initial solution is not given appropriately. Methods for solving this problem have been proposed for JSPs aiming at minimizing makespan. In high-mix low-volume manufacturing, it is important to minimize average lead time in addition to makespan. For this reason, this research deals with development of an efficient method using SA for JSPs aiming at minimizing average lead time. A method of neighborhood limitation for reducing average lead time was developed by focusing on waiting time of operations, and an improved SA in wnich the neighborhood limitation method is used with a given probability was proposed. Effectiveness of the proposed method was shown by numerical examples.