단방향 이동조건을 가지는 정수 선형 계획법에 의한 드롭렛 및 세척 드롭렛 스케줄
A Droplet and Wash Droplet Scheduling for DMFBs
- 주제(키워드) 정수 선형 계획법 , 바이오칩
- 발행기관 서강대학교 일반대학원
- 지도교수 임종석
- 발행년도 2012
- 학위수여년월 2012. 2
- 학위명 석사
- 학과 및 전공 일반대학원 컴퓨터공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000047227
- 본문언어 한국어
- 저작권 서강대학교 논문은 저작원 보호를 받습니다.
초록/요약
디지털 미세유체 바이오칩은 소량의 유체 시료가 이동하면서 바이오칩내의 각종 생물분자나 센서와의 반응 양상을 분석할 수 있는 장치이다. 바이오칩에서 소량의 유체를 드롭렛이라 하고 모든 드롭렛이 이동을 완료하는데 걸리는 시간을 최대 운송 시간이라 한다. 드롭렛의 최대 운송 시간이 길어지면 측정 결과의 정확성이 떨어질 수 있다. 따라서 바이오칩에서 드롭렛 최대 운송 시간을 최소화 하는 것이 중요하다. 본 논문에서는 드롭렛 최대 운송 시간 최소화를 목적으로 갖는 드롭렛 스케줄 문제를 다룬다. 기존 정수 선형 계획법에 의한 드롭렛 스케줄 방법은 가능 해가 많아 실제 문제에 적용하는데 어려움이 있다. 단방향 이동조건에 의해 가능 해를 줄이고 시간 제약에 의해 변수 개수를 줄여 최적 해를 찾는 속도를 개선한다. 드롭렛들은 이동 중에 잔여물을 셀에 남겨 오염지역을 만드는데 그 오염지역을 다른 드롭렛이 지나면 측정 결과의 정확성을 떨어뜨릴 수 있다. 이 때문에 세척 드롭렛이 도입되었다. 세척 드롭렛은 오염지역을 비오염지역으로 만든다. 세척 드롭렛을 포함하여 스케줄을 구할 때 최대 운송 시간을 최소화하는 것이 중요하다. 본 논문에서는 정수 선형 계획법을 이용하여 드롭렛과 세척 드롭렛의 최대 운송 시간을 최소화하는 스케줄을 구하는 방법을 제안한다. 드롭렛 스케줄 실험 결과에서는 기존의 정수 선형 계획법보다 제시된 방법이 최적 해를 찾는 속도가 약 25% ~ 93% 개선되었다. 세척 드롭렛 스케줄 실험 결과에서는 정수 선형 계획법에 의해 세척 드롭렛 문제를 해결할 수 있음을 보였다.
more초록/요약
Digital microfluidic biochips(DMFBs) are able to manipulate nanoliter liquids and analyze both the sensor response and the biomolecule reaction. In DMFBs, a nanoliter liquid is called a droplet. Droplet maximum transportation time is the time to route all droplets. Longer droplet maximum transportation time is hard to maintain the integrity of bioassay execution. Therefore, it is an important objective to shorten droplet maximum transportation time. In this paper, we address droplet scheduling by integer linear programming. The optimization objective is to minimize maximum transportation time. To speed up finding optimal slolution, we reduce the feasible solution space by integer linear programming with unidirectional constraints. In addition, different droplets being transported and manipulated on the DMFBs may introduce the contamination problem caused by liquid residue between different droplets. To overcome this problem, a wash droplet is introduced to clean the contaminations on the surface of the microfluidic array. It is an important objective to minimize droplet and wash droplet transportation time. We propose a wash droplet scheduling by integer linear programming(ILP). The optimization objective is to minimize droplet maximum transportation time including wash droplet. Experimental results show that our droplet scheduling improve the runtime by about 25% ~ 93% and our wash droplet scheduling by ILP can solve the wash droplet scheduling problems.
more