[논문]대안기계 스케쥴링 문제에 대한 라운딩 알고리듬

황학진

[국내논문] 대안기계 스케쥴링 문제에 대한 라운딩 알고리듬
A rounding algorithm for alternate machine scheduling 원문보기

經營科學 = Korean management science review, v.24 no.2, 2007년, pp.33 - 42

Abstract ▼ AI-Helper

In this paper we consider an alternate m machine scheduling problem in which each job having at most two eligible machines should be assigned with the objective of makespan minimization. For this problem. we propose a $O(m2^m)$ time rounding algorithm with performance ratio at most 1.5. For a little general problem where each job can be processed in at most three machines, we prove that a polynomial time algorithm does not exist with performance ratio less than 1.5.

Keyword

참고문헌 (25)

Azar, Y., J. Naor, and R. Rom, The competitiveness of On-Line Assignments, J. Algorithms, Vol.18(1995), pp.221-237

상세보기
Chang S.Y. and H.-C. Hwang, The worstcase analysis of the MULTIFIT algorithm for scheduling nonsimultaneous parallel machines, Discrete Applied Mathematics, Vol. 92(1999), pp.135-147

상세보기
Coffman Jr E.G., M.R. Garey, and D.S. Johnson, An application of bin-packing to multiprocessor scheduling, SIAM J. Comput., Vol.7(1978), pp.1-17

상세보기
Friesen D.K., Tighter bounds for the multi processor scheduling algorithm, SIAM J. of Comput., Vol.13(1984), pp.35-59
Garey M.R. and D.S. Johnson, Computers and Intractability：A Guide to the theory of NP-Completeness, Freeman, San Francisco, 1979
Graham R.L., Bounds on multiprocessor timing anomalies, SIAM J. Appl. Math., Vol. 17(1969), pp.263-269
Graham, R.L., E.L. Lawler, J.K. Lenstra, and A.H.G. Rinnooy Kan, Optimization and Approximation in Deterministic Machine Scheduling： A Survey, Annals of Discrete Mathematics, Vol.5(1979), pp.287-326
He Y., H. Kellerer, and V. Kotov, Linear Compound Algorithms for the Partitioning Problem, Naval Research Logistics, Vol.47 (2000), pp.593-601

상세보기
Hochbaum D.S. and D. Shmoys, Using dual approximation algorithms for scheduling problems： Theoretical and practical results, J. ACM, Vol.34(1987), pp.144-162

상세보기
Hochbaum D.S., Approximation Algorithms for NP-Hard Problems, PWS PUBLISHING COMPANY, Boston, (1997), 370-371
Hwang H.-C. and S.Y. Chang, Parallel machines scheduling with machine shutdowns, Computers and Mathematics with Applications, Vol.36(1998), pp.21-31
Hwang H.-C, A PTAS for nonsimultaneous parallel machine scheduling, Journal of the Korean Society of Maintenance Management, Vol.3(2003), pp.181-193
Hwang H.-C. and G. Kim, 2-Approximation Algorithm for Parallel Machine Scheduling with Consecutive Eligibility, KIIE, Vol.29(2003), pp.190-196
Hwang H.-C, LPT Scheduling for Multipurpose Machines, IE Interfaces, Vol.16(2003), pp.132-137

원문보기 상세보기
Hwang H.-C, K. Lee, and S.Y. Chang, Parallel machine scheduling under a grade of service provision, Computers & Operations Research, Vol.31(2004), pp.2055-2061

상세보기
Hwang H.-C, S.Y. Chang, and Y. Hong, The Posterior Competitiveness for List Scheduling Algorithm on Machines with Eligibility Constraints, Asia-Pacific Journal of Operational Research, Vol.1(2004), pp.1-9
Ibarra O.H. and C.E. Kim, Fast approximation algorithms for the knapsack and sum of subset problems, J. ACM, Vol.22 (1975), pp.463-468

상세보기
Kaplan R.S. and R. Cooper, Cost & Effect, Havard Business School Press, Boston, Massachusetts, 1997
Kellerer H., U. Pferschy, A New Fully Polynomial Approximation Scheme for the Knapsack Problem, Journal of Combinatorial Optimization, Vol.3(1999), pp.59-71
Lenstra J.K., D.B. Shmoys, and E. Tardos, Approximation Algorithms for Scheduling Unrelated Parallel Machines, Mathematical Programming, Vol.46(1990), pp.259-271

상세보기
Potts C.N., Analysis of a linear programming euristic for scheduling unrelated parallel machines, Discrete Appl. Math. Vol. 10(1985), pp.155-164

상세보기
Shchepinal E.V. and N. Vakhania, An optimal rounding gives a better approximation for scheduling unrelated machines, Operations Research Letters, Vol.33(2005), pp. 127-133

상세보기
Vairaktarakis, G.L. and X. Cai, The Value of Processing Flexibility in Multipurpose Machines, IIE Transactions, Vol.35(2003), pp.763-774

상세보기
Yu, L., Scheduling of unrelated parallel machines： an application to PWB manufacturing, IIE Transactions, Vol.34(2003), pp. 921-931
M. Yue, On the exact upper bound for the MULTIFIT processor scheduling algorithm, in Operations Research in China, M. Yue (ed.), of Annals of Operations Research, Baltzer, Basel, Switzerland, Vol.24(1990), pp. 233-259

상세보기

저자의 다른 논문 :

활용도 분석정보

상세보기

다운로드

내보내기

활용도 Top5 논문

해당 논문의 주제분야에서 활용도가 높은 상위 5개 콘텐츠를 보여줍니다.
더보기 버튼을 클릭하시면 더 많은 관련자료를 살펴볼 수 있습니다.

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증

[국내논문] 대안기계 스케쥴링 문제에 대한 라운딩 알고리듬
A rounding algorithm for alternate machine scheduling 원문보기

Abstract ▼ AI-Helper

Keyword

참고문헌 (25)

이 논문을 인용한 문헌

저자의 다른 논문 :

활용도 분석정보

활용도 Top5 논문

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

연합인증

[국내논문] 대안기계 스케쥴링 문제에 대한 라운딩 알고리듬 A rounding algorithm for alternate machine scheduling 원문보기

Abstract ▼ AI-Helper

Keyword

참고문헌 (25)

이 논문을 인용한 문헌

저자의 다른 논문 :

황학진 (6)

활용도 분석정보

활용도 Top5 논문 더보기

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

이 논문과 함께 이용한 콘텐츠

AI-Helper ※ AI-Helper는 오픈소스 모델을 사용합니다.

선택된 텍스트

[국내논문] 대안기계 스케쥴링 문제에 대한 라운딩 알고리듬
A rounding algorithm for alternate machine scheduling 원문보기

활용도 Top5 논문