본문 바로가기
KERD
논문KCI 등재

충분히 이른 작업의 수를 최대화시키는 확률적 스케줄링 문제

Stochastic Scheduling Problems for Maximizing the Number of Early Enough Jobs

0

조회

0

다운로드

0

인용

0

참고문헌

키워드

주제분류산업공학

초록

이 논문에서는 작업의 처리시간이 임의의 확률분포를 따르고 작업의 납기일이 작업마다 별개인 상황에서의 단일기계 스케줄링문제에 관하여 살펴본다. 이 때 충분히 이른 작업의 수를 최대화시키는 데에 관심을 둔다. 이러한 스케줄링문제를 풀기 위한 두 가지 알고리즘, 즉 이진정수계획모형과 스케줄링 규칙을 제안한다. 여기서 제안하는 스케줄링 규칙은 처리시간과 납기일이 확정적인 경우에 지연작업의 수를 최소화시켜주는 스케줄링을 제공하는 기존알고리즘을 처리시간과 납기일이 확률적인 경우로 확장한 것이다. 다음으로 이진정수계획모형과 스케줄링규칙을 성과측면에서 비교한다. 그 결과 대부분의 경우에 스케줄링 규칙이 이진정수계획모형과 거의 같은 스케줄을 제공할뿐만 아니라 컴퓨터자원을 매우 적게 소모한다.

참고문헌 (11)

  1. Balut, S. J., "Scheduling to Minimize the Number of Late Jobs When Set-Up and Processing Times are Uncertain", Management Science, 19, pp.1283~1288 (1973)
  2. Chang, C. -S., "Stochastic Convexity and Stochastic Majorization" (1994), Stochastic Modeling and Analysis of Manufacturing Systems, Springer-Verlag
  3. 최재영, "A Review on Scheduling Problems for Minimizing the Number of Late Jobs", 한국생산관리학회지, 22(2), pp.159~175 (2011), 한국생산관리학회
  4. Scheduling a Production Line to Minimize Maximum Tardiness, "Jackson, J. R.", UCLA, ~, pp.Research Report, 43 (1955)
  5. Katoh, N., "A Polynomial Time Algorithm for A Chance-Constrained Single Machine Scheduling Problem", Operations Research Letters, 2, pp.62~65 (1983)
  6. Kise, H., "On Balut’s Algorithm and NP-Completeness for a Chance-Constrained Scheduling Problem", Management Science, 29, pp.384~388 (1983)
  7. Kise, H., "An Efficient Algorithm for a Chance-Constrained Scheduling Problem", J. Operations Res. Soc, 25, pp.193~203 (1982)
  8. Moore, M. J., "An N Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs", Management Science, 15, pp.102~109 (1968)
  9. Nemhauser, G. L., "A Note on the Generalized Lagrange Multiplier Solution to an Integer Programming Problem", Operations Research, 16, pp.450~453 (1968)
  10. Ross, S. M., "Stochastic Processes" (1996), John Wiley & Sons
  11. Sterna, M., "Late work scheduling in shop systems" (2006), Publishing House of Poznan University of Technology

관련 논문AI추천

이 간행물의 다른 논문 (28건)