tailieunhanh - Độ 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 .

TÀI LIỆU LIÊN QUAN
TỪ KHÓA LIÊN QUAN