[논문]An FPTAS for the parallel two-stage flowshop problem

Dong, J.; Tong, W.; Luo, T.; Wang, X.; Hu, J.; Xu, Y.; Lin, G.

doi:10.1016/j.tcs.2016.04.046

An FPTAS for the parallel two-stage flowshop problem 원문보기

Theoretical computer science, v.657 pt.A, 2017년, pp.64 - 72

Dong, J. , Tong, W. , Luo, T. , Wang, X. , Hu, J. , Xu, Y. , Lin, G.

Abstract ▼ AI-Helper

We consider the NP-hard m-parallel two-stage flowshop problem, abbreviated as the (m,2)-PFS problem, where we need to schedule n jobs to m parallel identical two-stage flowshops in order to minimize the makespan, i.e. the maximum completion time of all the jobs on the m flowshops. The (m,2)-PFS problem can be decomposed into two subproblems: to assign the n jobs to the m parallel flowshops, and for each flowshop to schedule the jobs assigned to the flowshop. We first present a pseudo-polynomial time dynamic programming algorithm to solve the (m,2)-PFS problem optimally, for any fixed m, based on an earlier idea for solving the (2,2)-PFS problem. Using the dynamic programming algorithm as a subroutine, we design a fully polynomial-time approximation scheme (FPTAS) for the (m,2)-PFS problem.

주제어

참고문헌 (23)

J. Oper. Res. Soc. Chen 46 234 1995 10.1057/jors.1995.28 Analysis of classes of heuristics for scheduling a two-stage flow shop with parallel machines at one stage

상세보기
Oper. Res. Chen 44 891 1996 10.1287/opre.44.6.891 A new heuristic for three-machine flow shop scheduling

상세보기
Conway 1967 Theory of Scheduling
Garey 1979 Computers and Intractability: A Guide to the Theory of NP-Completeness
Math. Oper. Res. Garey 1 117 1976 10.1287/moor.1.2.117 The complexity of flowshop and jobshop scheduling

상세보기
Oper. Res. Gonzalez 26 36 1978 10.1287/opre.26.1.36 Flowshop and jobshop schedules: complexity and approximation

상세보기
J. Oper. Res. Soc. Gupta 39 359 1988 10.1057/jors.1988.63 Two-stage, hybrid flowshop scheduling problem

상세보기
Ann. Oper. Res. Gupta 69 171 1997 10.1023/A:1018976827443 Scheduling a two-stage hybrid flow shop with parallel machines at the first stage
Int. J. Prod. Res. Gupta 29 1489 1991 10.1080/00207549108948025 Schedules for a two-stage hybrid flowshop with parallel machines at the second stage

상세보기
Math. Program. Hall 82 175 1998 10.1007/BF01585870 Approximability of flow shop scheduling

상세보기
IIE Trans. He 28 129 1996 10.1080/07408179608966258 A scheduling problem in glass manufacturing

상세보기
J. ACM Hochbaum 34 144 1987 10.1145/7531.7535 Using dual approximation algorithms for scheduling problems theoretical and practical results

상세보기
European J. Oper. Res. Hoogeveen 89 172 1996 10.1016/0377-2217(94)00235-5 Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard
Jansen vol. 1770 455 2000 STACS Polynomial time approximation schemes for the multiprocessor open and flow shop scheduling problem
Nav. Res. Logist. Q. Johnson 1 61 1954 10.1002/nav.3800010110 Optimal two- and three-stage production schedules with setup times included

상세보기
Oper. Res. Lett. Lee 16 149 1994 10.1016/0167-6377(94)90026-4 Minimizing makespan in hybrid flowshops

상세보기
European J. Oper. Res. Ruiz 205 1 2010 10.1016/j.ejor.2009.09.024 The hybrid flow shop scheduling problem

상세보기
J. ACM Sahni 23 116 1976 10.1145/321921.321934 Algorithms for scheduling independent tasks

상세보기
Theoret. Comput. Sci. Schuurman 237 105 2000 10.1016/S0304-3975(98)00157-1 A polynomial time approximation scheme for the two-stage multiprocessor flow shop problem

상세보기
IIE Trans. Vairaktarakis 32 687 2000 10.1080/07408170008967427 The use of flowlines to simplify routing complexity in two-stage flowshops

상세보기
Expert Syst. Wang 22 78 2005 10.1111/j.1468-0394.2005.00297.x Flexible flow shop scheduling: optimum, heuristics and artificial intelligence solutions

상세보기
Oper. Res. Williamson 45 288 1997 10.1287/opre.45.2.288 Short shop schedules

상세보기
European J. Oper. Res. Zhang 216 544 2012 10.1016/j.ejor.2011.08.007 Approximation algorithms for the parallel flow shop problem

상세보기

원문 보기

AccessON 원문보기

원문 URL 링크

DOI : 10.1016/j.tcs.2016.04.046 [무료]
Elsevier : 저널 > 논문 [무료]
AccessON : 저널

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

오픈액세스(OA) 유형

GOLD(Hybrid)

저자가 APC(Article Processing Charge)를 지불한 논문에 한하여 자유로운 이용이 가능한, hybrid 저널에 출판된 논문

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

[논문] 부품 생산과 조립으로 구성된 2단계 조립 일정계획의 Flowtime 최소화 연구

저작권 관리 안내

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

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

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증

An FPTAS for the parallel two-stage flowshop problem 원문보기

Abstract ▼ AI-Helper

주제어

참고문헌 (23)

이 논문을 인용한 문헌

관련 콘텐츠

원문 보기

원문 URL 링크

오픈액세스(OA) 유형

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

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

선택된 텍스트

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, 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