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

서지정보

ㆍ발행기관 : 한국산업경영시스템학회 ㆍ수록지정보 : 산업경영시스템학회지 / 38권 / 3호
ㆍ저자명 : 최진영

목차

1. Introduction
2. Problem Definition and a Branchand-Bound Algorithm
2.1 Problem Definition
2.2 Properties for Dominance and Feasibility
2.3 Branch-and-Bound Algorithm
3. An Efficient GA
4. Numerical Experiments
4.1 Experimental Design
4.2 Experimental Results and Assessment
5. Conclusions
References

영어 초록

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.

참고 자료

없음