작업 종속 및 위치기반 선형학습효과를 갖는 2-에이전트 단일기계 스케줄링

• 영문명: Two-Agent Single-Machine Scheduling with Linear Job-Dependent Position-Based Learning Effects
• 발행기관: 한국산업경영시스템학회
• 저자명: 최진영(Jin Young Choi)
• 간행물 정보: 『산업경영시스템학회지』제38권 제3호, 169~180쪽, 전체 12쪽
• 주제분류: 경제경영 > 경영학
• 파일형태: PDF
• 발행일자: 2015.09.30

영문 초록

Recently, scheduling problems with position-dependent processing times have received considerable attention in the literature,where the processing times of jobs are dependent on the processing sequences. However, they did not consider cases in which each processed job has different learning or aging ratios. This means that the actual processing time for a job can be determined not only by the processing sequence, but also by the learning/aging ratio, which can reflect the degree of processing difficulties in subsequent jobs. Motivated by these remarks, in this paper, we consider a two-agent single-machine scheduling problem with linear job-dependent position-based learning effects, where two agents compete to use a common single machine and each job has a different learning ratio. Specifically, we take into account two different objective functions for two agents: one agent minimizes the total weighted completion time, and the other restricts the makespan to less than an upper bound. After formally defining the problem by developing a mixed integer non-linear programming formulation, we devise a branch-and-bound (B&B) algorithm to give optimal solutions by developing four dominance properties based on a pairwise interchange comparison and four properties regarding the feasibility of a considered sequence. We suggest a lower bound to speed up the search procedure in the B&B algorithm by fathoming any non-prominent nodes. As this problem is at least NP-hard, we suggest efficient genetic algorithms using different methods to generate the initial population and two crossover operations. Computational results show that the proposed algorithms are efficient to obtain near-optimal solutions.

목차

1. Introduction

2. Problem Definition and a Branchand-Bound Algorithm

3. An Efficient GA

4. Numerical Experiments

5. Conclusions

키워드

Two-Agent Single-Machine Scheduling Job-Dependent Position-Based Processing Time Total Weighted Completion Time Makespan Branch-and-Bound Algorithm Genetic Algorithm