Đề tài nghiên cứu cơ bản do Quỹ Phát triển khoa học và công nghệ Quốc gia tài trợ năm 2015 (NAFOSTED)

Tên đề tài: Phân chia tài nguyên: Độ phức tạp và Thuật toán xấp xỉChủ nhiệm: TS Nguyễn Trung Thành, Khoa Toán – Trường ĐH Hải PhòngThời gian thực hiện: 24 tháng (2016-2017)Tóm tắt vấn đề nghiên cứu: Phân chia tài nguyên (resource allocation) là một trong những bài toán cơ bản nhưng có vai trò đặc biệt quan trọng trong Toán học, Khoa học máy tính, Khoa học xã hội, và Kinh tế học. Các ứng dụng nổi bật của bài toán này bao gồm: tối ưu hoá trong sản xuất và lập kế hoạch (manufacturing and scheduling), quản lý khủng hoảng (crisis management), quản lý giao thông hàng không (airport traffic management), vận tải (logistic), giao thông công cộng (public transport), vệ tinh quan sát trái đất (Earth Observation Satellites), đấu giá tổ hợp (combinatorial auction), smart grid (lưới thông minh). Bài toán phân chia tài nguyên có thể phát biểu đơn giản như sau: cho trước m món hàng hoá khác nhau và n khách hàng (khách hàng ở đây có thể là các cá nhân, công ty, hay tập thể nào đó); cần phân chia các món hàng hoá này cho các khách hàng theo một tiêu chí nào đó, với các ràng buộc cho trước đối với tập các món hàng. Ở đây, ta giải thiết rằng mỗi khách hàng có đánh giá riêng đối với các món hàng hoá mà họ có thể được nhận. Các đánh giá này có thể được biểu thị bằng nhiều cách khách nhau. Chẳng hạn, mỗi khách hàng có thể sắp xếp các món hàng hoá từ thấp đến cao theo mức độ ưa thích của họ; hay sử dụng một hàm số (tuyến tính hay phi tuyến) m biến số để định lượng giá trị cụ thể của các món hàng hoá. Về mặt toán học, một dạng cơ bản của bài toán phân chia tài nguyên có thể được mô hình hoá như sau:

Bài toán phân chia tài nguyên là một bài toán tối ưu rời rạc (hoặc liên tục) thuộc lớp NP-khó (tức là hầu như không thể tìm được lời giải tối ưu trong “thời gian đa thức”). Do đó, các hướng nghiên cứu hiện nay đều tập trung vào việc tìm kiếm các lời giải xấp xỉ với sai số nhỏ chấp nhận được.Mục đích của đề tài: Đề tài tập trung nghiên cứu độ phức tạp tính toán và lời giải xấp xỉ cho một lớp các biến thể của bài toán phân chia tài nguyên, dựa trên cách mà mỗi khách hàng biểu thị sự ưa thích của họ đối với tập món hàng.Danh sách thành viên:

TT	Họ và tên	Đơn vị	Nhiệm vụ
1	TS. Nguyễn Trung Thành	Khoa Toán - ĐH Hải Phòng	Chủ nhiệm đề tài
2	TS. Lê Đắc Nhường	Khoa CNTT - ĐH Hải Phòng	Nghiên cứu viên chính
3	TS. Nguyễn Gia Như	Phòng sau đại học - ĐH Duy Tân	Thư kí
4	TS. Lê Đăng Nguyên	Phòng Khảo thí - ĐH Hải Phòng	Nghiên cứu viên
5	ThS. Nguyễn Ngọc Khương	Khoa CNTT - ĐH Hải Phòng	Kĩ thuật viên