TAILIEUCHUNG - Độ phức tạp của một số vấn đề lịch biểu với công đoạn dương

Độ phức tạp của một số vấn đề lịch biểu với công đoạn dương Đo đường tương quan huỳnh quang của đơn phân tử chất màu phát quang, từ đó tính toán đặc trưng của hệ đo và thông số vật lý của chất màu như thời gian khuếch tán. - Đặc trưng quá trình tương tác giữa các đơn phân tử sinh học (ADN). | Tạp chí Tin học và Điều khiển học T. 16 2000 74-80 THE COMPLEXITY OF SOME FLOW-SHOP SCHEDULES WITH POSITIVE TASK-TIMES vu DINH HOA Abstract. The general flow-shop problem is known to be NP-complete. Solution have also been specified in several special cases. A j-maximal j-minimal flow-shop is a particular kind of flow-shop in which the j-th task of any job has the longest shortest execution time comparing to another tasks of this job. We prove in this paper that the problem to find an optimal schedule for three-stage j -maximal t-minimal i 7 2 flow-shop with positive task time is NP-complete. Tóm tắt. Bài toán lịch biểu tong quát vẫn được biết là bài toán NPC. Người ta xét và giải bài toán này trong nhiều lóp đặc biệt khác nhau. Một bài toán lịch biểu j-maximal -minimal là bài toán lịch biểu đặc biệt khi thời gian gia công ờ công đoạn thứ j là lớn nhất hoặc nhỏ nhất so vói thòi gian gia công ờ các công đoạn khác đối vói công việc đang tiến hành. Ta chứng minh trọng là vấn đề tìm lịch biểu tối ưu cho bài toán j-maximal i-minimal với 3 công đoạn i 7 2 với thời gian gia công mỗi công đoạn là đưo ng vẫn là NPC. 1. INTRODUCTION Flow-shop 5 consists of m 1 processors Pl p2 . Pm and n 1 jobs Ji J2 . Jn - Each processor Pj performs a different task and each job Ji has a chain of m tasks. With Tji we denote the j-th task of Ji on processor Pj with execution time tjj. Flow-shop with positive task time is one with tji 0 for all j and i. Furthermore each task Tji has to be processed on Pj and can only be executed after Ty-I j has been finished. A schedule for a flowshop is defined as a sequence of tasks to be executed by each processor. A schedule is called a permutation schedule if the schedule on each processor is the same. If we allow a task to be partitioned and done in several time intervals the schedule is called preemtive. In the following we only consider nonpreemptive schedules for which a processor cannot be interrupted in between once it has begun .

• Kĩ thuật Viễn thông
• vật lý toán
• điều khiển học
• nghiên cứu tin học
• Lý thuyết thuật toán
• tự động học
• khoa học điều khiển
• Chương trình đào tạo Vật lý lý thuyết
• Đào tạo tiến sĩ Vật lý lý thuyết
• Chuyên ngành Vật lý lý thuyết
• Đào tạo Vật lý toán
• Vật lý lý thuyết
• Luyện giải đề Vật lý
• Phương pháp giải bài toán Vật lý
• Bài toán Vật lý
• Giải bài toán Vật lý
• Trắc nghiệm Vật lý
• Đề thi Vật lý
• Đề thi Vật lý mẫu
• Giải các bài toán Vật lý sơ cấp
• Bài toán Vật lý sơ cấp
• Phương pháp giải toán Vật lý sơ cấp
• Vật lý sơ cấp
• Dao động cơ học
• Đề thi học kỳ
• Phương pháp toán cho Vật lý 1
• Vật lý 1
• Đề thi Phương pháp toán cho Vật lý 1
• Bài tập Phương pháp toán cho Vật lý 1
• Ôn tập Phương pháp toán cho Vật lý 1
• Đáp án đề thi
• Luận án Tiến sỹ Vật lý nguyên tử
• Vật lý nguyên tử
• Cấu trúc pha
• Đối xứng chiral
• Phương pháp Toán
• Đáp án đề thi Phương pháp Toán cho Vật lý
• Luận án Tiến sĩ Vật lý
• Phương pháp đạo hàm trung bình
• Phương pháp Richarson
• Phương pháp IAD
• Tuyển chọn bài toán Vật Lý
• Bài tập Vật lý
• Bài tập Vật lý tuyển chọn
• Luyện giải toán Vật lý
• Con lắc đơn
• Dao động tắt dần
• Giao thoa sóng cơ học
• Điện xoay chiều
• Phương pháp Toán cho Vật lý 2
• Vật lý 2
• Đề thi Phương pháp Toán cho Vật lý 2
• Bài tập Phương pháp Toán cho Vật lý 2
• Đề thi giữa học học kỳ II
• Phương pháp Toán cho Vật lý I
• Vật lý I
• Đề thi Phương pháp Toán cho Vật lý I
• Bài tập Phương pháp Toán cho Vật lý I
• công thức vật lí
• bài tập trắc nghiệm vật lí
• vật lí nâng cao
• kiến thức vật lý căn bản
• giáo án hình học nâng cao
• đố vui toán học
• số học
• hình học
• bài tập toán
• nghiên cứu khoa học
• chuyên đề vật lý
• luận văn khoa vật lý
• vật lý ứng dụng
• nghiên cứu vật lý
• Giản đồ FEYNMAN
• Luyện thi Vật lý
• Ôn thi THPT Quốc gia
• Ôn thi Vật lý
• Giải toán Vật lý
• Giải nhanh bài tập Vật lý
• Giải trắc nghiệm môn Vật lý
• Phương pháp giải bài tập Vật lý
• Giải bài tập Vật lý
• Bài tập trắc nghiệm Vật lý
• Kiến thức cơ bản Vật lý