지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- 대한산업공학회 Industrial Engineering & Management Systems Industrial Engineering & Management Systems Vol.15 No.1
- 발행연도
- 2016.3
- 수록면
- 32 - 40 (9page)
이용수
초록· 키워드
오류제보하기
This paper considers a special case of a three machine flow shop scheduling problem in which operation processing time of each job is ordered such that machine 1 has the longest processing time, whereas machine 3, the shortest processing time. The objective of the problem is the minimization of the total completion time. Although the problem is simple, its complexity is yet to be established to our best knowledge. This paper first introduces the problem and presents some optimal properties of the problem. Then, it establishes several special cases in which a polynomial-time optimal solution procedure can be found. In addition, the paper proves that the recognition version of the problem is at least binary NP-complete. The complexity of the problem has been open despite its simple structure and this paper finally establishes its complexity. Finally, a simple and intuitive heuristic is developed and the tight worst case bound on relative error of 6/5 is established.
목차
ABSTRACT
1. INTRODUCTION
2. NOTATION
3. BASIC RESULTS
4. SPECIAL CASES
5. COMPLEXITY
6. HEURISTICS
7. A SUMMARY AND FUTURE RESEARCH
REFERENCES
참고문헌 (10)
참고문헌 신청
Baker, K. R. and Trietsch, D. (2009), Flow shop scheduling, Principles of sequencing and scheduling, John Wiley and Sons, 225-249.
Chen, B., Potts, C. N., and Woeginger, G. J. (1993), A review of machine scheduling: complexity, algorithms and approximability, Handbook of Combinatorial Optimization, Springer US, 1493-1641.
Garey, M. R. and Johnson, D. S. (1979), Computers and intractibility: a guide to the theory of NP-completeness, New York: W. H. Freeman and Co.
Garey, M. R., Johnson, D. S., and Sethi, R. (1976), The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1, 117-129.
Graham, R. L., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G. (1979), Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 287-326.
Chen, B., Potts, C. N., and Woeginger, G. J. (1993), A review of machine scheduling: complexity, algorithms and approximability, Handbook of Combinatorial Optimization, Springer US, 1493-1641.
Garey, M. R. and Johnson, D. S. (1979), Computers and intractibility: a guide to the theory of NP-completeness, New York: W. H. Freeman and Co.
Garey, M. R., Johnson, D. S., and Sethi, R. (1976), The complexity of flowshop and jobshop scheduling, Mathematics of Operations Research, 1, 117-129.
Graham, R. L., Lawler, E. L., Lenstra, J. K., and Rinnooy Kan, A. H. G. (1979), Optimization and approximation in deterministic sequencing and scheduling: a survey, Annals of Discrete Mathematics, 5, 287-326.
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
Hybrid Flow Shop with Parallel Machines at the First Stage and Dedicated Machines at the Second Stage
Industrial Engineering & Management Systems
2015 .03
-
Two-Agent Single-Machine Scheduling with Linear Job-Dependent Position-Based Learning Effects
산업경영시스템학회지
2015 .01
-
Robust single-machine scheduling with uncertain processing times
대한산업공학회 춘계공동학술대회 논문집
2017 .04
-
기계학습 기반 저 복잡도 긴장 상태 분류 모델
전기학회논문지
2017 .09
-
Parallel Machine Scheduling Considering the Moving Time of Multiple Servers
한국컴퓨터정보학회논문지
2017 .10
-
Predicting Machine Processing Time using Decision Tree
대한산업공학회 춘계공동학술대회 논문집
2017 .04
-
이종 병렬설비 공정의 납기지연시간 최소화를 위한유전 알고리즘
산업경영시스템학회지
2015 .01
-
A Heuristic Method for Solving Bi-Objective Two-Stage Hybrid Flow Shop Scheduling Problem
Industrial Engineering & Management Systems
2017 .06
-
Developing Visual Complexity Metrics for Automotive Human-Machine Interfaces
대한인간공학회지
2015 .06
-
Rescheduling a Single Machine with Various Objectives
Industrial Engineering & Management Systems
2018 .12
-
유전 알고리즘을 이용한 두 단계 이종병렬기계 시스템의 일정계획
대한산업공학회지
2021 .02
-
An Approximation Algorithm for A Proportionate Flow Shop Scheduling Problem with Machine Speeds
대한산업공학회 추계학술대회 논문집
2024 .10
-
강화학습을 활용한 작업 분할이 가능하고 설비 제약이 존재하는 동종 병렬 시스템의 총 납기 지연 최소화
대한산업공학회지
2023 .12
-
보완 다중 활동 분석표와 시뮬레이션을 이용한 작업자 운영 전략 분석
산업경영시스템학회지
2024 .03
-
A two-machine flow shop with storage under the dominant environment
대한산업공학회 춘계공동학술대회 논문집
2018 .04
-
A parallel machine scheduling problem with release dates, equal processing times, and eligibility constraints
대한산업공학회 추계학술대회 논문집
2017 .11
-
A Low-Complexity Synchronization Algorithm for LTE-based Machine-Type Communication
한국통신학회 학술대회논문집
2016 .06
-
대형기계 및 고출력기계의 소음 정보 데이터베이스
한국기계기술학회지
2018 .01
-
40m/min 이송속도를 가진 고속가공기의 모달해석
한국기계가공학회지
2023 .02
-
이종 장비에서의 학습모델 성능유지를 위한 방법론 제안
한국정밀공학회 학술발표대회 논문집
2023 .11
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2016-530-002732396