A Heuristic Algorithm to Minimize Total Holding Cost of Completed and Processing Production Job-Shop Scheduling Subject to No Tardy Jobs

DOI Web Site 9 References

Bibliographic Information

Other Title
  • 製品と仕掛り品の総在庫コスト最小化の納期厳守型ジョブショップスケジューリングの近似解法
  • セイヒン ト シカカリヒン ノ ソウ ザイコ コスト サイショウカ ノ ノウキ ゲンシュガタ ジョブショップスケジューリング ノ キンジカイホウ

Search this article

Description

This paper considers the job-shop scheduling problem of minimizing the total holding cost of completed and processing products subject to no tardy jobs since meeting due dates is the most important goal of scheduling if the due date of each job has been promised to its customer. A heuristic algorithm based on the shifting bottleneck procedure is proposed for solving the minimum total holding cost problem subject to no tardy jobs. The purpose of this paper is that larger size problems, for example a problem comprising 15 jobs and 15 machines, and more severe due dates problems can be effectively solved. The proposed algorithm decomposes the job shop problem into a number of single-machine problems with ready time and due time constraints. Each decomposed problem is strictly solved by a branch and bound algorithm using new due dates for each operation decided by considering to meet prespecified due dates and minimizing objective functions, simultaneously. We used an elimination method adapted for a single-machine problem at any node to directly select some disjunctions or at least to determine whether or not a potentially optimum solution can be obtained. In this way, the branch and bound tree is trimmed efficiently. Some benchmark problems used by job-shop scheduling to minimize makespan are solved by the proposed algorithm and the results are reported.

Journal

References(9)*help

See more

Keywords

Details 詳細情報について

Report a problem

Back to top