RISS 검색 - 국내학술지논문 상세보기

다국어 초록 (Multilingual Abstract)

Given machines of identical performance or quad-core processor working on jobs of different processing time, the economic profit and job efficiency will be maximized only if makespan could be minimized with polynomial time complexity. In spite of a handful of researches on makespan minimization, no unique, universally applicable, and generalized polynomial time algorithm has been developed. This paper therefore proposed a simple polynomial-time algorithm by which unassigned job is first assigned machines of the minimum process time and jobs are swapped between different machines until the processing time is nearly equalized. When applied to various experimental data, the proposed algorithm has successfully minimized the makespan.

국문 초록 (Abstract)

처리시간이 각기 다른 개의 작업에 대해 대의 동일한 성능을 가진 기계나 컴퓨터의 4중 프로세서 가 동시에 작업을 수행할 때, 총 작업 소요(종료) 시간을 최소화 시키도록 작업을 완료할 수 ...

처리시간이 각기 다른 개의 작업에 대해 대의 동일한 성능을 가진 기계나 컴퓨터의 4중 프로세서 가 동시에 작업을 수행할 때, 총 작업 소요(종료) 시간을 최소화 시키도록 작업을 완료할 수 있다면 작업 효율성 측면과 경제적 이득을 극대화 시킬 수 있을 것이다. 총 작업종료시간 최소화에 대한 연구는 있어 왔지만 간단하면서도 다양한 사례에 적합한 일반화된 단일의 다항시간 알고리즘이 존재하지 않고 있다. 본 논문은 처리시간이 최소인 기계에 미배정된 작업을 우선 배정하는 방법을 적용하고, 처리시간이 거의 동일하도록 기계간에 작업을 교환하는 방법을 제안하였다. 다양한 실험 데이터들에 제안된 알고리즘을 적용한 결과 총 작업종료시간을 최소화 시켰다. 제안된 알고리즘은 간단하면서도 다항시간으로 최적 해를 찾을 수 있었다.

참고문헌 (Reference)

1 이상운, "생산공정 일정계획 알고리즘" 한국정보기술학회 11 (11): 157-166, 2013

2 E. Mokotoff, "Scheduling to Minimize the Makespan on Identical Parallel Machines : An LP-Based Algorithm" 8 (8): 97-107, 1999

3 J. C. Ho, "Minimizing Total Weighted Flowtime Subject to Minimum Makespan on Two Identical Parallel Machines" 22 (22): 179-190, 2011

4 J. N. D. Gupta, "Minimizing Makespan Subject to Minimum Total Flow-time on Identical Parallel Machines" 125 (125): 370-380, 2000

5 J. N. D. Gupta, "Minimizing Makespan Subject to Minimum Flowtime on Two Identical Parallel Machines" 28 (28): 705-717, 2001

6 J. N. D. Gupta, "Minimizing Flowtime Subject to Optimal Makespan on Two Identical Parallel Machines" 20 (20): 5-17, 2000

7 J. N. D. Gupta, "Makespan Minimization on Identical Parallel Machines Subject to Minimum Total Flow-Time" 21 (21): 220-229, 2004

8 C-H. Lin, "Makespan Minimization Subject to Flowtime Optimality on Identical Parallel" 31 (31): 1655-1666, 2004

9 M. Sevkli, "A Modified Variable Neighborhood Search for Minimizing the Makespan on Identical Parallel Machines" 108-111, 2009

10 L. Min, "A Genetic Algorithm for Minimizing the Makespan in the case of Scheduling Identical Parallel Machines" 13 (13): 399-403, 1999