작업 스케쥴링 문제 해결을 위한 Branch & Bound 해법의 비교분석 Heuristic Aspects of the Branch and Bound Procedure for a Job Scheduling Problem

This article evaluates the efficiency of three branch-and-bound heuristics for a job scheduling problem that minimizes the sum of absolute deviations of completion times from a common due date. To improve the performance of the branch-and-bound procedure, Algorithm SA is presented for the initial feasible schedule and three heuristics : breadth-first, depth-first and best-first search are investigated depending on the candidate selection procedure. For the three heuristics the CPU time, memory space, and the number of nodes generated are computed and tested with nine small examples (6≤n≤4). Medium sized random problems (10≤n≤30) are also generated and examined. The computational results are compared and discussed for the three heuristics.
Publisher
대한산업공학회
Issue Date
1992
Language
KOR
Citation

JOURNAL OF THE KOREAN INSTITUTE OF INDUSTRIAL ENGINEERINGS, v.18, no.2, pp.141 - 147

ISSN
1225-0988
URI
http://hdl.handle.net/10203/65908
Appears in Collection
IE-Journal Papers(저널논문)
Files in This Item
There are no files associated with this item.
  • Hit : 160
  • Download : 0
  • Cited 0 times in thomson ci

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0