A Neighborhood Limitation Method for Job-Shop Scheduling Based on Simulated Annealing

DOI Web Site Web Site 被引用文献1件 参考文献6件

この論文をさがす

抄録

<p>Because of non-deterministic polynomial time hardness of job-shop scheduling problem (JSP), approximate optimization based on meta-heuristics has been actively discussed. Considering position of planners in production sites, it is desirable to develop a method in which their know-how is respected. An approach for meeting this requirement is to set the schedule generated by a planner as the initial solution and then gradually improve the solution by repeating a search in its neighborhood so that he/she can follow and thoroughly examine the improved solution. For this reason, this research is focused on scheduling using simulated annealing (SA). Because SA has a disadvantage that good solutions cannot be obtained efficiently if the initial solution has not been given appropriately, methods for solving this problem have been proposed for JSPs aiming at minimizing makespan. In high-mix low-volume manufacturing, it is also important to minimize production lead time to reduce work-in-process inventory. This research takes up production lead time defined as the time between the starting and the finishing times of a job considering strong constraint on places for putting works-in-process in production of large equipment, and deals with development of an efficient method using SA for JSPs aiming at minimizing the average value of the production lead times. Two methods of neighborhood limitation in SA for reducing the evaluation value were developed by focusing on waiting time of operations. It was proven that using one of the proposed methods in SA with appropriate probabilities is effective to JSPs of a certain size by numerical examples.</p>

収録刊行物

被引用文献 (1)*注記

もっと見る

参考文献 (6)*注記

もっと見る

キーワード

詳細情報 詳細情報について

問題の指摘

ページトップへ