$\require{mediawiki-texvc}$

연합인증

연합인증 가입 기관의 연구자들은 소속기관의 인증정보(ID와 암호)를 이용해 다른 대학, 연구기관, 서비스 공급자의 다양한 온라인 자원과 연구 데이터를 이용할 수 있습니다.

이는 여행자가 자국에서 발행 받은 여권으로 세계 각국을 자유롭게 여행할 수 있는 것과 같습니다.

연합인증으로 이용이 가능한 서비스는 NTIS, DataON, Edison, Kafe, Webinar 등이 있습니다.

한번의 인증절차만으로 연합인증 가입 서비스에 추가 로그인 없이 이용이 가능합니다.

다만, 연합인증을 위해서는 최초 1회만 인증 절차가 필요합니다. (회원이 아닐 경우 회원 가입이 필요합니다.)

연합인증 절차는 다음과 같습니다.

최초이용시에는
ScienceON에 로그인 → 연합인증 서비스 접속 → 로그인 (본인 확인 또는 회원가입) → 서비스 이용

그 이후에는
ScienceON 로그인 → 연합인증 서비스 접속 → 서비스 이용

연합인증을 활용하시면 KISTI가 제공하는 다양한 서비스를 편리하게 이용하실 수 있습니다.

병렬기계로 구성된 인쇄회로기판 제조공정에서의 스케쥴링에 관한 연구
Unrelated Parallel Machine Scheduling for PCB Manufacturing 원문보기

산업경영시스템학회지 = Journal of society of korea industrial and systems engineering, v.27 no.4, 2004년, pp.141 - 146  

김대철 (충북대학교 경영대학 경영학부)

Abstract ▼ AI-Helper 아이콘AI-Helper

This research considers the problem of scheduling jobs on unrelated parallel machines with a common due date. The objective is to minimize the total absolute deviation of job completion times about the common due date. This problem is motivated by the fact that a certain phase of printed circuit boa...

주제어

#unrelated parallel machine   #scheduling   #common due date   #PCB  

AI 본문요약
AI-Helper 아이콘 AI-Helper

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

  • 따라서 본 연구에서는 이러한 보다 현실적인 조건을 반영하기 위하여 이들 병렬기계들의 성능이 다르다는 가정 하에서의 MAD를 최소화하는 스케쥴링 문제에 대하여 연구하고자 한다.
  • 따라서, 본 연구에서는 PCB 생산에 있어서, 각 작업이 동일한 납기 일자를 가지고, 병목공정인 드릴링 공정이 각각의 성능에 차이가 있는 병렬 드릴링 기계들로 구성되어 있을 경우, 이들 병렬기계들에서의 MAD 값을 최소화하기위한 스케쥴링 문제를 다루고자 한다.
  • 본 문제의 최적 스케쥴들이 가지고 있는 2가지 특성들을 밝히고자 한다. 이 특성들을 밝히기 위하여 사용된 기호 [i,j]는 기계 i에서의 스케쥴에서 순서가 j번째인 작업을 나타낸다.
  • 이러한 현상에 대한 스케쥴링 문제는 모든 병렬기계들의 성능이 동일한 경우보다 더 현실을 반영한 모델이지만 문제의 복잡성 때문에 많이 연구되지 못한 것이 사실이다. 본 연구에서는 병렬기계들의 속도가 각 기계마다 서로 다른 병렬기 계 (unrelated parallel machines)일때 이들 공정에서의 스케쥴링 문제를 다루고자 한다.
  • 본 연구에서는 병렬기계에서의 스케쥴링에 관한 문제 들중에서 모든 작업들의 납기 일자가 동일한 경우의 문제를 다루었다. 납기 일자에 관련하여서는 납기 일자가 전체 작업들의 가공처리 시간의 합보다 작다는 제약을 지닌 경우와 각 작업들의 납기알자가 서로 다른 경우 등의 또 다른 유형의 스케쥴링 문제들이 존재한다.
  • 본 연구에서는 이 문제에 대한 정수계획모델을 제시하였고, 모든 최적 스케쥴의 각 작업들 사이에는 유휴시간이 존재하지 않는다는 것과, 최소한 하나의 최적 스케쥴은 납기 일자 d에서 정확히 끝내거나 시작하는 작업(job)을 가지고 있다는 특성들을 밝혔다. 또한, 이 특성들을 이용하면 이러한 복잡한 문제가 폴리노미얼 시간(polyno­ mial time)안에 최적해를 구할 수 있는 알고리즘이 존재하는 비대칭할당 문제로 전환할 수 있음을 밝혔다.
  • 본 연구에서는 인쇄회로기판(PCB : printed circuit board) 생산라인의 병목공정 (bottleneck operation) 에 대한 스케쥴링 문제를 다루고자 한다. PCB 생산라인은 기판에 회로를 각인하는 공정 등 여러 개의 공정으로 구성되어 있다 (Yu et al.

가설 설정

  • 증명. 한 최적 스케쥴 σ*의 기계 i에서의 작업 k와 k+1사이에 유휴시간이 존재한다고 가정하자.
본문요약 정보가 도움이 되었나요?

참고문헌 (9)

  1. Baker, K.R., Introduction to Sequencing and Scheduling, N.Y., John Wiley, 1974 

  2. Baker, K.R. and Scudder, G.D., 'Sequencing with Earliness and Tardiness Penalties: A Review.' Operations Research, 38, pp. 22-36, 1990 

  3. Bertsekas, D.P., Linear Network Optimization, Algorithms and Codes. MIT Press, Cambridge, Mass. 1991 

  4. Kanet, J.J., 'Minimizing the Average Deviation of Job Completion Times about a Common Due Date.' Naval Research Logistics Quarterly, 28, pp. 643-651, 1981 

  5. Kuhn, N.W., 'The Hungarian Method for the Assignment Problem.' Naval Research Logistics Quarterly, 2, pp. 83-97, 1955 

  6. Martello, S., Soumis, F. and Toth, P., 'Exact and approximation algorithms for makespan minimization on unrelated parallel machines,' Discrete Applied Mathematics, 75, pp. 169-188, 1977 

  7. Palekar, U.S., Rama, N. and Toaffe, K. 'Duality based relaxations for makespan minimization for unrelated parallel machines,' TIMS/ORSA Bulletin, 31(MC2.2), pp. 21, 1991 

  8. Piersma, N. and Van Dijk, W., 'A local search heuristics for unrelated parallel machine scheduling with efficient neighborhood search,' Mathematical Computer Modelling, 24(9), pp. 11-19, 1996 

  9. Yu, L., Smith, H.M., Pfund, M., Carlyle, W.M., and Fowler, J.W., 'Scheduling of unrelated parallel machines: an application to PWB manufacturing,' IIE Transactions, 34, pp. 921- 931, 2002 

관련 콘텐츠

저작권 관리 안내
섹션별 컨텐츠 바로가기

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

AI-Helper 아이콘
AI-Helper
안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

선택된 텍스트

맨위로