Rate-Modifying 활동이 있는 병렬기계의 Makespan 최소화를 위한 일정 계획 = Parallel Machines Scheduling with Rate-Modifying Activities to Minimize Makespan

다국어 초록 (Multilingual Abstract)

  This paper deals with the problem of scheduling jobs and rate-modifying activities on parallel machines. A rate-modifying activity is an activity that changes the production rate of equipment such as maintenance and readjustment. If a job is scheduled after the rate-modifying activity, then the processing time varies depending on the modifying rate of the activity. In this study, we extend the single machine problem to parallel machines problem and propose algorithms is to schedule the rate-modifying activities and jobs to minimize the makespan on parallel machines which is NP-hard. We propose a branch and bound algorithm with three lower bounds to solve medium size problems optimally. Also we develop three heuristics, Modified Longest Processing Time, Modified MULTIFIT and Modified COMBINE algorithms to solve large size problems. The test results show that branch and bound algorithm finds the optimal solution in a reasonable time for medium size problems (up to 15 jobs and 5 machines). For large size problem, Modified COMBINE and Modified MULTIFIT algorithms outperform Modified LPT algorithm in terms of solution quality.

목차 (Table of Contents)

• 1. 서론
  2. 문제 정의
  3. 제안 알고리듬
  4. 실험 결과
  5. 결론
  참고문헌
  

참고문헌 (Reference)

• 1 Lee, "Single-Machine Scheduling with maintenance and repair rate-modifying activities" 135 : 493-513, 2001
• 2 Pinedo, "Scheduling：Theory Algorithms and Systems 2nd Edition" Prentice-Hall 2002
• 3 Lee, "Scheduling of Jobs and Maintenance Activities on Parallel Machines" 47 : 145-165, 2000
• 4 Graves, "Scheduling Maintenance and Semi-resumable Jobs on a Single Machine" 46 : 845-863, 1999
• 5 Ho, "Makespan Minimization for m Parallel Identical Processors" 42 : 935-948, 1995
• 6 Liao, "Makespan Minimization for Two Parallel Machines with an Availability Constraint" 160 : 445-456, 2005
• 7 Lee, "Machine Scheduling with a Rate-Modifying Activity" 128 : 119-128, 2001
• 8 Ethel Mokotoff, "An Exact Algorithm for the Identical Parallel Machine Scheduling Problem" 152 : 758-769, 2004
• 9 Graham, "; “Bounds on Multiprocessing Timing Anomalies ” SIAM Journal on Applied mathematics" 416-429, 1969
• 10 Coffman Jr, "; “An Application of Bin-Packing to Multiprocessor Scheduling ” SIAM Journal on Computing" 1-17, 1978
• 11 Baker, "; Introduction to Sequencing and Scheduling" John Wiley & Sons Inc 1943∼1974