서지주요정보
One-machine scheduling problem with deadlines to minimize total weighted completion times = 납기제약하에서 총가중완성시간을 최소화하는 단일기계 일정계획 문제
서명 / 저자 One-machine scheduling problem with deadlines to minimize total weighted completion times = 납기제약하에서 총가중완성시간을 최소화하는 단일기계 일정계획 문제 / Seong-Soo Song.
저자명 Song, Seong-Soo ; 송성수
발행사항 [대전 : 한국과학기술원, 1992].
Online Access 제한공개(로그인 후 원문보기 가능)원문

소장정보

등록번호

8002702

소장위치/청구기호

학술문화관(문화관) 보존서고

MMGS 92026

SMS전송

도서상태

이용가능

대출가능

반납예정일

초록정보

In this thesis, the dominance relations among several lower and upper bounds are represented clearly by schedule graphs. An existing decomposition rule is computationally experimented. Based on the observation, blockwise heuristics are devised to improve the efficiency of branch and bound algorithm for large problems. Finally, we show that a branch and bound algorithm may be improved by excluding some of the popular precedence conditions and incorporating a dominance property between nodes."

본 논문은 각 작업에 작업중요도에 따른 가중치와 납기가 주어졌을 때, 납기를 준수하면서 총가중완성시간을 최소화하는 단일기계의 일정계획에 관한 연구이다. 이 문제는 NP-complete임이 증명되었는 바, 대부분의 연구들은 분지한계법하에서 하한의 개선과 우선조건의 발견에 집중되어왔다. 본 논문에서는 여러 하한 및 상한들간의 우월관계를 그래프를 이용하여 명확하게 표현하였다. 그리고 기존의 분해규칙의 실제적 유효성에 대한 실험을 하였으며, 그 결과를 기초로 대규모 문제에서 분지한계법의 효율성을 제고할 수 있는 blockwise heuristic을 고안하였다. 마지막으로 분지한계법에 이용되는 우선조건들중에 비효과적인 것들을 제거하고, 마디(node)간 우월조건을 효율적으로 구현함으로써 분지한계법의 효율성이 향상됨을 보이고 있다.

서지기타정보

서지기타정보
청구기호 {MMGS 92026
형태사항 v, 65 p. : 삽도 ; 26 cm
언어 영어
일반주기 Appendix : 1, Types of time interval by procedure LB. - 2, Blockwise heuristic. - 3, Branch and bound algorithm source code
저자명의 한글표기 : 송성수
지도교수의 영문표기 : In-Soo Lee
지도교수의 한글표기 : 이인수
학위논문 학위논문(석사) - 한국과학기술원 : 경영과학과,
서지주기 Reference : p. 64-65
주제 Operations research.
일정 계획. --과학기술용어시소러스
오퍼레이션 리서치. --과학기술용어시소러스
Scheduling.
QR CODE qr code