tailieunhanh - Thuật toán nhanh để tìm thời gian biểu với số lượng tùy ý các công việc đúng hạn và thời gian xử lý ít nhất.

Thuật toán nhanh để tìm thời gian biểu với số lượng tùy ý các công việc đúng hạn và thời gian xử lý ít nhất. Đã biểu hiện và tinh chế, xác định đặc tính của 2 conotoxin tái tổ hợp dạng dung hợp với thioredoxin Trx-CTX ( -CTX với thioredoxin) và Trx-µO-CTX (µO-CTX với thioredoxin). Đã hoàn thiện quy trình biểu hiện và tinh chế protein dung hợp Trx-CTX tái tổ hợp ở E. coli với hiệu suất 60 mg/L và xây dựng các tiêu chuẩn cơ sở cho protein này | Tạp chí Tin học và Điều khiển học T. 17 s. 1 2001 21-30 THE FAST ALGORITHM FOR FOUNDING NONPREEMPTIVE SCHEDULE WITH SOME ON-TIME JOBS IN MINIMAL PROCESSING TIME TRINH NHAT TIEN Abstract. In 2 we presented an o n2 .logn algorithm to determine a schedule with maximal number of on-time jobs in minimal processing time for problem 1 ry 152 Uj in the case that release dates and due dates are satisfied II - I2 ỉn where ly ry dy . ry dj dk . In this paper we would extend the above algorithm to determine a schedule of the same problem but with any number of on-time jobs in minimal processing time. The time for this problem is O . Tóm tắt. Trong 2 chúng tôi đã trình bày thuật toán ỡ để xác định thò i gian biểu vó i số hrọTig ló n nhất các công việc đúng hạn và thòi gian xứ lý ít nhất cho vấn đề 1 ry I 52 Uj trong đó Ij rj dyj mà ry dj dfe. Trong bài báo này chúng tôi mà rộng kết quả cda thuật toán trên cho bài toán xây dựng thò i gian biểu cứa cùng vấn đề nhung số lu crng công việc đúng hạn là tùy ý nhưng thò i gian xú lý là ít nhất. 1. SOME BASIC CONCEPTS Some conceptions in the paper are presented in 2 . Now we would remind some concepts and notations related to job realization and schedule . The following data can be specified for each job u - ru is a release date on which u becomes available for processing - du is a due date by which u should ideally be completed - tu is a processing time or length of u. We assume that the above data are nonnegative integers and are regarded as parameters of job u. For convenience we will also use a concept pre-job u it is a pair I L tu where Iu ru du is its active area. A pre-job u such that tu du ru is said to be a job. Ru u cu ỉ u is a starting time C L is a completion time is said to be a realization of job u on machine. A job u is said to be completed on time or a on-time job if cu du otherwise a job u is said to be late. Let li ry dj j and ly ry dy be active areas of corresponding jobs i and j respectively. Then