병렬기계에서의 스케쥴링에 관한 연구 = Uniform Parallel Machine Scheduling

다국어 초록 (Multilingual Abstract)

This study considers the problem of scheduling jobs on uniform 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 board manufacturing is bottleneck and the processing speeds of parallel machines in this phase are uniformly different for all jobs. Optimal properties are proved and a simple polynomial time optimal algorithm is developed.

목차 (Table of Contents)

• 영어 초록
• 1. 서론
• 2. Proof of Optimality
• 3. 알고리즘
• 4. 결론
• 참고문헌

참고문헌 (Reference)

1 "Single- and Multi-Processor Models for Minimizing Completion Time Variance" 49-54, 1986

2 "Sequencing with Earliness and Tardiness Penalties" 22-36, 1990

3 "Scheduling: Theory, Algorithm, and Systems" Prentice Hall 1995

4 "Scheduling of unrelated parallel machines: an application to PWB manufacturing" 34 : 921-931, 2002

5 "Scheduling of unrelated parallel machines: an application to PWB manufacturing" 34 : 921-931, 2002

6 "Parallel machine scheduling with earliness-tardiness penalties and additional resource constraints" 2003

7 "Parallel Machine Scheduling about an Unrestricted Due Date and Resource Constraints" 32 (32): 147-153, 2000

8 "Minimizing the Sum of Lateness in Single-Machine and Multimachine Scheduling" 325-333, 1984

9 "Minimizing the Average Deviation of Job Completion Times about a Common Due Date" 643-651, 1981

10 "Introduction to Sequencing and Scheduling" 1974

11 "Exact and approximation algorithms for makespan minimization on unrelated parallel machines" 169-188, 1977

12 "Duality based relaxations for makespan minimization for unrelated parallel machines" 1991

13 "A state-of-the-art review of parallel-machine scheduling research European Journal of Operational Research" 271-292, 1990

14 "A local search heuristics for unrelated parallel machine scheduling with efficient neighborhood search" 24 (24): 11-19, 1996