RISS 학술연구정보서비스

검색
다국어 입력

http://chineseinput.net/에서 pinyin(병음)방식으로 중국어를 변환할 수 있습니다.

변환된 중국어를 복사하여 사용하시면 됩니다.

예시)
  • 中文 을 입력하시려면 zhongwen을 입력하시고 space를누르시면됩니다.
  • 北京 을 입력하시려면 beijing을 입력하시고 space를 누르시면 됩니다.
닫기
    인기검색어 순위 펼치기

    RISS 인기검색어

      KCI등재

      A Heuristic Algorithm to Minimize Mean Squared Deviation of Completion Times

      한글로보기

      https://www.riss.kr/link?id=A76597957

      • 0

        상세조회
      • 0

        다운로드
      서지정보 열기
      • 내보내기
      • 내책장담기
      • 공유하기
      • 오류접수

      부가정보

      국문 초록 (Abstract)

      이 논문은 비제약적인 경우에 공통의 납기로부터 완료간의 평균제곱편차(MSD)를 최소화하는 문제를 연구한다. 비제약적 MSD 문제는 NP-complete이며 스케쥴 생성과 개선 두 단계로 구성된 자기발견적 알고리즘이 제안된다. 스케쥴 생성 단계에서는 모의뜨임 기법과 균형된 V형태 스케쥴을 사용하여 좋은 초기 해를 생성한다. 그리고 개선 단계에서는 better dual과 better pair의 개념에 기초하여 해의 질을 제고한다. 개발된 두 단계는 평균제곱편차를 최소화하는 문제의 해를 찾기 위하여 순차적으로 적용된다. 첫 번째 단계가 여러 가지 아이디어를 이용하여 좋은 초기해를 발견하는데 초점을 둔다면 두 번째 단계는 계량적 방법을 이용하여 해의 질을 증진하는 것에 초점을 맞춘다.
      비제약적 MSD 문제에서 최고의 자기발견적 알고리즘은 Ventura and Weng(1995)이 제시하였으며, Gupta et al.(1990)이 제안한 자기발견적 알고리즘은 Ventura and Weng의 알고리즘에 비해 훨씬 적은 시간에 비교적 좋은 해를 제공한다. 본 연구에서 제안된 자기발견적 알고리즘은 Elion and Chowdhury(1977)와 Gupta et al.(1990)의 논문에 있는 모든 예제의 최적해를 Ventura and Weng(1990)의 자기발견적 알고리즘보다 훨씬 적은 시간에 발견한다. 작업의 수가 많을 때 제안된 자기발견적 알고리즘의 성과를 검증하기 위하여 여러 개의 예제를 개발하였다. 계산 결과를 보면 거의 모든 예제에서 Gupta 등이 개발한 자기발견적 알고리즘보다 본 연구에서 제안된 자기발견적 알고리즘이 같거나 더 좋은 해를 찾는다.
      번역하기

      이 논문은 비제약적인 경우에 공통의 납기로부터 완료간의 평균제곱편차(MSD)를 최소화하는 문제를 연구한다. 비제약적 MSD 문제는 NP-complete이며 스케쥴 생성과 개선 두 단계로 구성된 자기발...

      이 논문은 비제약적인 경우에 공통의 납기로부터 완료간의 평균제곱편차(MSD)를 최소화하는 문제를 연구한다. 비제약적 MSD 문제는 NP-complete이며 스케쥴 생성과 개선 두 단계로 구성된 자기발견적 알고리즘이 제안된다. 스케쥴 생성 단계에서는 모의뜨임 기법과 균형된 V형태 스케쥴을 사용하여 좋은 초기 해를 생성한다. 그리고 개선 단계에서는 better dual과 better pair의 개념에 기초하여 해의 질을 제고한다. 개발된 두 단계는 평균제곱편차를 최소화하는 문제의 해를 찾기 위하여 순차적으로 적용된다. 첫 번째 단계가 여러 가지 아이디어를 이용하여 좋은 초기해를 발견하는데 초점을 둔다면 두 번째 단계는 계량적 방법을 이용하여 해의 질을 증진하는 것에 초점을 맞춘다.
      비제약적 MSD 문제에서 최고의 자기발견적 알고리즘은 Ventura and Weng(1995)이 제시하였으며, Gupta et al.(1990)이 제안한 자기발견적 알고리즘은 Ventura and Weng의 알고리즘에 비해 훨씬 적은 시간에 비교적 좋은 해를 제공한다. 본 연구에서 제안된 자기발견적 알고리즘은 Elion and Chowdhury(1977)와 Gupta et al.(1990)의 논문에 있는 모든 예제의 최적해를 Ventura and Weng(1990)의 자기발견적 알고리즘보다 훨씬 적은 시간에 발견한다. 작업의 수가 많을 때 제안된 자기발견적 알고리즘의 성과를 검증하기 위하여 여러 개의 예제를 개발하였다. 계산 결과를 보면 거의 모든 예제에서 Gupta 등이 개발한 자기발견적 알고리즘보다 본 연구에서 제안된 자기발견적 알고리즘이 같거나 더 좋은 해를 찾는다.

      더보기

      다국어 초록 (Multilingual Abstract)

      This paper addresses the problem of minimizing the mean squared deviation(MSD) of completion times from a common due date in unconstrained case. The unconstrained MSD is known to be NP-complete and a heuristic algorithm which consists of two phases(schedule construction and improvement) is proposed. In the schedule construction phase, by using the simulated annealing technique and balanced V-shape schedule, good initial solutions are constructed. Then, the improvement phase enhances the quality of solution based on the concepts of both better dual and better pair. The developed two phases are serially employed to obtain the schedule of minimizing MSD problem. The first phase focuses on the finding of good initial solution and the second phase stresses on the improvement of solution quality.
      For the unconstrained MSD problem, the best known heuristic the algorithm is in Ventura and Weng(1995) and the algorithm in Gupta et al.(1990) finds fairly good solutions with much less computational time than one in Ventura and Weng(1995). The proposed heuristic finds all optimal solutions of the test problems in Eilon and Chowdhury(1977) and Gupta et al.(1990) with much less computational time compared with the heuristic in Ventura and Weng(1995). In order to show the performance of proposed heuristic in detail when job sizes are large, several test problems are generated. The computational results show that it provides better or same solutions for almost all test problems than the heuristic in Gupta et al.(1990).
      번역하기

      This paper addresses the problem of minimizing the mean squared deviation(MSD) of completion times from a common due date in unconstrained case. The unconstrained MSD is known to be NP-complete and a heuristic algorithm which consists of two phases(sc...

      This paper addresses the problem of minimizing the mean squared deviation(MSD) of completion times from a common due date in unconstrained case. The unconstrained MSD is known to be NP-complete and a heuristic algorithm which consists of two phases(schedule construction and improvement) is proposed. In the schedule construction phase, by using the simulated annealing technique and balanced V-shape schedule, good initial solutions are constructed. Then, the improvement phase enhances the quality of solution based on the concepts of both better dual and better pair. The developed two phases are serially employed to obtain the schedule of minimizing MSD problem. The first phase focuses on the finding of good initial solution and the second phase stresses on the improvement of solution quality.
      For the unconstrained MSD problem, the best known heuristic the algorithm is in Ventura and Weng(1995) and the algorithm in Gupta et al.(1990) finds fairly good solutions with much less computational time than one in Ventura and Weng(1995). The proposed heuristic finds all optimal solutions of the test problems in Eilon and Chowdhury(1977) and Gupta et al.(1990) with much less computational time compared with the heuristic in Ventura and Weng(1995). In order to show the performance of proposed heuristic in detail when job sizes are large, several test problems are generated. The computational results show that it provides better or same solutions for almost all test problems than the heuristic in Gupta et al.(1990).

      더보기

      목차 (Table of Contents)

      • Abstract
      • Ⅰ. INTRODUCTION
      • Ⅱ. LITERATURE REVIEW
      • Ⅲ. SOLUTION APPROACH
      • Ⅳ. CONCLUSION
      • Abstract
      • Ⅰ. INTRODUCTION
      • Ⅱ. LITERATURE REVIEW
      • Ⅲ. SOLUTION APPROACH
      • Ⅳ. CONCLUSION
      • REFERENCES
      • 요약
      더보기

      참고문헌 (Reference)

      1 Merten, Alan G, "Variance Minimization in Single Machine Sequencing Problems" 18 : 518-528, 1972

      2 Bonomi, E, "The N-city Traveling Salesman Problem: Statistical Mechanics and Metropolis Algorithm" 26 : 551-568, 1983

      3 Baker, Kenneth R, "Sequencing with Earliness and Tardiness Penalties: A Review" 38 : 22-36, 1990

      4 Hall, Nicholas G, "Proof of a Conjecture of Schrage about the Completion Time Variance Problem" 10 : 467-472, 1991

      5 Kirkpatrick, S, "Optimization by Simulated Annealing" 220 : 671-680, 1983

      6 Sidney,Jeffrey B, "Optimal Single Machine Scheduling with Earliness and Tardiness Penalties" 25 : 62-69, 1977

      7 De, Prabuddha, "On the Minimization of Completion Time Variance with a Bicriteria Extension" 40 : 1148-1155, 1992

      8 Schrage,Linus, "Minimizing the Time in System Variance for a Finite Job Set" 21 : 540-543, 1975

      9 Kim, C, "Minimizing the Mean Squared Deviation from a Common Due Date: Unconstrained and Constrained Cases" 7 : 492-502, 1996

      10 Gupta, M. G, "Minimizing the Flow Time Variance in the Single Machine Systems" 41 : 767-779, 1990

      1 Merten, Alan G, "Variance Minimization in Single Machine Sequencing Problems" 18 : 518-528, 1972

      2 Bonomi, E, "The N-city Traveling Salesman Problem: Statistical Mechanics and Metropolis Algorithm" 26 : 551-568, 1983

      3 Baker, Kenneth R, "Sequencing with Earliness and Tardiness Penalties: A Review" 38 : 22-36, 1990

      4 Hall, Nicholas G, "Proof of a Conjecture of Schrage about the Completion Time Variance Problem" 10 : 467-472, 1991

      5 Kirkpatrick, S, "Optimization by Simulated Annealing" 220 : 671-680, 1983

      6 Sidney,Jeffrey B, "Optimal Single Machine Scheduling with Earliness and Tardiness Penalties" 25 : 62-69, 1977

      7 De, Prabuddha, "On the Minimization of Completion Time Variance with a Bicriteria Extension" 40 : 1148-1155, 1992

      8 Schrage,Linus, "Minimizing the Time in System Variance for a Finite Job Set" 21 : 540-543, 1975

      9 Kim, C, "Minimizing the Mean Squared Deviation from a Common Due Date: Unconstrained and Constrained Cases" 7 : 492-502, 1996

      10 Gupta, M. G, "Minimizing the Flow Time Variance in the Single Machine Systems" 41 : 767-779, 1990

      11 Eilon, Samuel, "Minimizing Waiting Time Variance in the Single Machine Problem" 23 : 567-575, 1977

      12 Kanet,John J, "Minimizing Variation of Flow Time in Single Machine Systems" 27 : 1453-1459, 1991

      13 Ventura, Jose A, "Minimizing Single Machine Completion Time Variance" 41 : 1448-1455, 1995

      14 Bagchi, Uttaraya, "Minimizing Mean Squared Deviation of Completion Times about a Common Due Date" 33 : 894-906, 1987

      15 Laarhoven, P. J, "Job Shop Scheduling by Simulated Annealing" 40 : 113-125, 1992

      16 유승억, "JIT실행과 비전통적 성과측정 및 보상시스템 속성의 관련성에 관한 연구" 한국산업경영학회 20 (20): 291-317, 2005

      17 Vani, Vina, "Deterministic and Random Single Machine Sequencing with Variance Minimization" 35 : 111-120, 1987

      18 Kuiak,W, "Completion Time Variance Minimization on a Single Machine is Difficult" 14 : 49-59, 1993

      19 Kim, C, "Assignment Problem in Single Row and Double Rows Machine Layouts During Slow and Peak Period" 30 : 411-422, 1996

      20 Connolly,David T, "An Improved Annealing Scheme for the QAP" 46 : 93-100, 1990

      21 김수행, "AHP를 이용한 도요타 생산시스템 평가항목의 중요도 분석 - 공급사슬망 위치에 따른 비교" 한국산업경영학회 23 (23): 137-161, 2008

      22 Raghavachari,M, "A V-shaped Property of Optimal Schedule of Jobs about a Common Due Date" 23 : 401-402, 1986

      23 Burkard, R. E, "A Thermodynamically Motivated Simulation Procedure for Combinatorial Optimization Problems" 17 : 169-174, 1984

      24 Kouvelis, P, "A Simulated Annealing Procedure for Single Row Layout Problems in Flexible Manufacturing Systems" 30 : 717-732, 1992

      더보기

      동일학술지(권/호) 다른 논문

      동일학술지 더보기

      더보기

      분석정보

      View

      상세정보조회

      0

      Usage

      원문다운로드

      0

      대출신청

      0

      복사신청

      0

      EDDS신청

      0

      동일 주제 내 활용도 TOP

      더보기

      주제

      연도별 연구동향

      연도별 활용동향

      연관논문

      연구자 네트워크맵

      공동연구자 (7)

      유사연구자 (20) 활용도상위20명

      인용정보 인용지수 설명보기

      학술지 이력

      학술지 이력
      연월일 이력구분 이력상세 등재구분
      2026 평가예정 재인증평가 신청대상 (재인증)
      2020-01-01 평가 등재학술지 유지 (재인증) KCI등재
      2017-01-01 평가 등재학술지 유지 (계속평가) KCI등재
      2013-01-01 평가 등재학술지 유지 (등재유지) KCI등재
      2010-01-01 평가 등재학술지 유지 (등재유지) KCI등재
      2008-01-01 평가 등재학술지 유지 (등재유지) KCI등재
      2006-01-01 평가 등재학술지 유지 (등재유지) KCI등재
      2003-01-01 평가 등재학술지 선정 (등재후보2차) KCI등재
      2002-01-01 평가 등재후보 1차 PASS (등재후보1차) KCI등재후보
      2000-07-01 평가 등재후보학술지 선정 (신규평가) KCI등재후보
      더보기

      학술지 인용정보

      학술지 인용정보
      기준연도 WOS-KCI 통합IF(2년) KCIF(2년) KCIF(3년)
      2016 0.6 0.6 0.71
      KCIF(4년) KCIF(5년) 중심성지수(3년) 즉시성지수
      0.75 0.75 1 0.2
      더보기

      이 자료와 함께 이용한 RISS 자료

      나만을 위한 추천자료

      해외이동버튼