Luận án Một số phương pháp gần đúng giải bài toán lập lịch với tài nguyên giới hạn

fơơn vị BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG 
VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ 
ĐẶNG QUỐC HỮU 
MỘT SỐ PHƯƠNG PHÁP GẦN ĐÚNG 
GIẢI BÀI TOÁN LẬP LỊCH VỚI TÀI NGUYÊN GIỚI HẠN 
LUẬN ÁN TIẾN SĨ TOÁN HỌC 
Hà Nội - 2021 
BỘ GIÁO DỤC VÀ ĐÀO TẠO BỘ QUỐC PHÒNG 
VIỆN KHOA HỌC VÀ CÔNG NGHỆ QUÂN SỰ 
ĐẶNG QUỐC HỮU 
MỘT SỐ PHƯƠNG PHÁP GẦN ĐÚNG 
GIẢI BÀI TOÁN LẬP LỊCH VỚI TÀI NGUYÊN GIỚI HẠN 
Chuyên ngành: Cơ sở toán học cho tin học 
Mã số: 9 46 01 10 
LUẬN ÁN TIẾN SĨ TOÁN HỌC 
NGƯỜI HƯỚNG DẪN KHOA HỌC: 
1. TS. Nguyễn Thế Lộc 
2. TS. Nguyễn Doãn Cường 
Hà Nội - 2021 
i 
LỜI CAM ĐOAN 
Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các số liệu, 
kết quả nghiên cứu được trình bày trong luận án là hoàn toàn trung thực và chưa 
từng được ai công bố trong bất kỳ công trình nào khác, các dữ liệu tham khảo 
được trích dẫn đầy đủ. 
Hà Nội, ngày tháng 08 năm 2021 
 Nghiên cứu sinh 
Đặng Quốc Hữu 
ii 
LỜI CẢM ƠN 
Luận án này được hoàn thành tại Viện Công nghệ thông tin - Viện Khoa 
học và Công nghệ quân sự và Trường Đại học Thương mại. 
Lời đầu tiên, nghiên cứu sinh bày tỏ lòng biết ơn sâu sắc tới tập thể giáo 
viên hướng dẫn: TS. Nguyễn Thế Lộc và TS. Nguyễn Doãn Cường đã trực tiếp 
giảng dạy và tận tình hướng dẫn, định hướng cho nghiên cứu sinh trong suốt 
quá trình thực hiện luận án này. 
Nghiên cứu sinh trân trọng gửi lời cảm ơn tới Thủ trưởng Viện Khoa học 
và Công nghệ quân sự, Phòng Đào tạo - Viện Khoa học và Công nghệ quân sự, 
Viện Công nghệ thông tin đã giúp đỡ tôi trong suốt thời gian học tập, nghiên 
cứu, thực hiện luận án. Cảm ơn các thầy cô tại Viện Khoa học và Công nghệ 
quân sự, Đại học Quốc gia Hà Nội, Đại học Sư phạm Hà Nội,... đã nhiệt tình 
hướng dẫn, giúp đỡ tôi hoàn thành các nội dung của chương trình tiến sĩ và 
đóng góp cho tôi những ý kiến quý báu về mặt nội dung khoa học và bố cục 
của luận án. 
Tôi xin trân trọng cảm ơn các thầy cô, các nhà khoa học, đồng nghiệp 
trong và ngoài Viện đã đọc, nhận xét luận án, đóng góp những ý kiến quý báu 
để nghiên cứu sinh hoàn thiện luận án này. 
Trân trọng cảm ơn Ban Giám hiệu trường Đại học Thương mại, các đồng 
nghiệp và gia đình đã động viên, chia sẻ và tạo điều kiện cho tôi trong suốt thời 
gian làm nghiên cứu sinh. 
 Nghiên cứu sinh 
Đặng Quốc Hữu 
iii 
MỤC LỤC 
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT ....................................................... v 
DANH MỤC CÁC BẢNG ....................................................................................... vii 
DANH MỤC CÁC HÌNH VẼ....................................................................................ix 
MỞ ĐẦU ..................................................................................................................... 1 
CHƯƠNG 1: TỔNG QUAN VỀ BÀI TOÁN MS-RCPSP ........................................ 8 
1.1. Bài toán MS-RCPSP ......................................................................................... 9 
1.1.1. Mô tả bài toán ................................................................................................... 9 
1.1.2. Một số ứng dụng thực tế của bài toán MS-RCPSP ......................................... 15 
1.1.3. Những nghiên cứu liên quan ........................................................................... 19 
1.2. Một số thuật toán metaheuristic tìm nghiệm gần đúng ................................... 24 
1.2.1. Thuật toán PSO ............................................................................................... 25 
1.2.2. Thuật toán PSO kết hợp với tìm kiếm lân cận ................................................ 27 
1.2.3. Thuật toán DE ................................................................................................. 31 
1.2.4. Thuật toán Cuckoo Search .............................................................................. 33 
Kết luận chương 1 ..................................................................................................... 42 
CHƯƠNG 2: GIẢI BÀI TOÁN MS-RCPSP BẰNG PHƯƠNG PHÁP TỐI ƯU 
BẦY ĐÀN VÀ PHƯƠNG PHÁP TIẾN HÓA VI PHÂN ........................................ 43 
2.1. Phương pháp biểu diễn cá thể ......................................................................... 44 
2.2. Thang đo độ chênh của cá thể ......................................................................... 45 
2.3. Đề xuất thuật toán M-PSO .............................................................................. 50 
2.3.1. Kỹ thuật Di cư ................................................................................................. 51 
2.3.2. Thuật toán M-PSO .......................................................................................... 54 
2.3.3. Thực nghiệm ................................................................................................... 56 
2.3.4. Đánh giá chất lượng lời giải của thuật toán .................................................... 61 
2.3.5. Hình ảnh so sánh M-PSO và GA-M ............................................................... 63 
2.4. Đề xuất thuật toán DEM ................................................................................. 64 
2.4.1. Phương pháp tái thiết lập tài nguyên thực hiện .............................................. 64 
2.4.2. Thuật toán ....................................................................................................... 70 
2.4.3. Kết quả thực nghiệm ....................................................................................... 70 
2.4.4. Đánh giá chất lượng lời giải của thuật toán .................................................... 74 
2.4.5. Hình ảnh so sánh DEM với thuật toán GA-M ................................................ 77 
Kết luận chương 2 ..................................................................................................... 79 
CHƯƠNG 3: BÀI TOÁN REAL-RCPSP ................................................................ 80 
3.1. Bài toán Real-RCPSP ..................................................................................... 80 
iv 
3.1.1. Phát biểu bài toán ............................................................................................ 81 
3.1.2. Những ứng dụng thực tế của bài toán Real-RCPSP ....................................... 82 
3.2. Xếp loại bài toán Real-RCPSP thông qua phân loại Graham ......................... 83 
Kết luận chương 3 ..................................................................................................... 88 
CHƯƠNG 4: GIẢI BÀI TOÁN REAL-RCPSP BẰNG PHƯƠNG PHÁP TIẾN 
HÓA VI PHÂN VÀ PHƯƠNG PHÁP CUCKOO SEARCH .................................. 89 
4.1. Phương pháp biểu diễn cá thể ......................................................................... 90 
4.2. Đề xuất thuật toán A-DEM ............................................................................. 92 
4.2.1. Phương pháp thích nghi .................................................................................. 93 
4.2.2. Thuật toán A-DEM ......................................................................................... 97 
4.2.3. Thực nghiệm ................................................................................................... 99 
4.2.4. Đánh giá chất lượng lời giải của thuật toán .................................................. 104 
4.2.5. Hình ảnh so sánh A-DEM và GA-M ............................................................ 105 
4.3. Đề xuất thuật toán R-CSM ............................................................................ 106 
4.3.1. Thuật toán ..................................................................................................... 107 
4.3.2. Kết quả thực nghiệm ..................................................................................... 109 
4.3.3. Đánh giá chất lượng lời giải của thuật toán .................................................. 110 
4.3.4. Hình ảnh so sánh R-CSM với thuật toán GA-M ........................................... 111 
4.4. Đề xuất thuật toán RR-CSM ......................................................................... 112 
4.4.1. Phương pháp Rotate ...................................................................................... 113 
4.4.2. Thuật toán ..................................................................................................... 117 
4.4.3. Kết quả thực nghiệm ..................................................................................... 119 
4.4.4. Đánh giá chất lượng lời giải của thuật toán .................................................. 120 
4.4.5. Hình ảnh so sánh RR-CSM với thuật toán GA-M ........................................ 122 
Kết luận chương 4 ................................................................................................... 124 
KẾT LUẬN ............................................................................................................. 125 
DANH MỤC CÁC CÔNG TRÌNH KHOA HỌC ĐÃ CÔNG BỐ ........................ 127 
TÀI LIỆU THAM KHẢO ....................................................................................... 129 
v 
DANH MỤC CÁC KÝ HIỆU, CHỮ VIẾT TẮT 
Ci Tập tác vụ (task) cần thực hiện trước tác vụ i 
L Tập các tài nguyên; 
Li Tập tài nguyên có thể thực hiện tác vụ i, Li L 
Li Tài nguyên thứ i 
P Một lịch biểu khả thi của bài toán; 
Pall Tập tất cả các lịch biểu 
S Tập tất các các kỹ năng của các tài nguyên; 
Si Tập các kỹ năng của tài nguyên i, Si S 
W Tập các tác vụ của dự án 
Wi Tập các tác vụ có thể thực hiện bởi tài nguyên i, Wi W 
Wi Tác vụ thứ i 
Algorithm Thuật toán, mô tả bằng mã giả của một thuật toán 
A-DEM Thuật toán mới A-DEM (Adaptive DEM) 
AVG Giá trị trung bình (Average) 
BEST Giá trị tốt nhất (BEST) 
CR Xác suất lai ghép (Crossover Probability ) 
CS Thuật toán Cuckoo Search (Cuckoo Search) 
CSM Thuật toán CS áp dụng giải bài toán MS-RCPSP (CS for 
MS-RCPSP) 
DE Thuật toán tiến hóa vi phân (Differential Evolution) 
DEM Thuật toán đề xuất DEM áp dụng giải bài toán MS-RCPSP 
(DE for MS-RCPSP) 
Fitness Giá trị tốt nhất của một cá thể trong quần thể từ thế hệ đầu 
tiên cho đến thế hệ hiện tại. 
GA Thuật toán di truyền (Genetic Algorithms) 
GRASP Thuật toán lai giữa Greedy và Adative(Greedy Randomized 
vi 
Adaptive Search Procedure) 
GreedyDO Thuật toán tham lam nhằm tối ưu thời gian thực hiện 
(Greedy algorithm for Duration Optimization) 
GS Kỹ thuật tìm kiếm toàn cục (Global Search) 
HAntCO Thuật toán tối ưu đàn kiến lai (Hybrid Ant Colony 
Optimization) 
iMOPSE Bộ dữ liệu chuẩn iMOPSE (iMOPSE dataset) 
LS Kỹ thuật tìm kiếm cục bộ (Local Search) 
Makespan Thời gian tối thiểu để hoàn thành dự án 
M-PSO Thuật toán đề xuất M-PSO (Migration PSO) 
MS-RCPSP Bài toán lập lịch với tài nguyên giới hạn và đa kỹ năng 
(Multi skill - RCPSP) 
PSO Thuật toán tối ưu bầy đàn (Particle Swarm Optimization) 
RCPSP Bài toán lập lịch thực hiện dự án với tài nguyên giới hạn -
sau này viết gọn là: bài toán lập lịch với tài nguyên giới hạn 
(Resource-Constrained Project Scheduling Problem) ... dering learning effect.", Journal of 
Modelling in Management, 10, 2019. 
130 
[8]. Alswaitti Mohammed, M. Albughdadi, N.A.M Isa, "Variance-based 
differential evolution algorithm with an optional crossover for data 
clustering.", Applied Soft Computing, 80, pp. 1-17, 2019. 
[9]. B. Veltman, B. J. Lageweg, and J. K. Lenstra, “Multiprocessor scheduling 
with communication delays”, Parallel Computing, Vol. 16, No. 2-3, pp. 
173-182, 1990. 
[10]. D. Gnad, J. Hoffmann, "Star-topology decoupled state space 
search.", Artificial Intelligence, 257, pp. 24-60,2018. 
[11]. F. Black, and M. Scholes, “The pricing of options and corporate 
liabilities”, Journal of Political Economy, 81, pp. 637-654, 1973 
[12]. G. Che, L. Liu, Z. Yu, "An improved ant colony optimization algorithm 
based on particle swarm optimization algorithm for path planning of 
autonomous underwater vehicle.", Journal of Ambient Intelligence and 
Humanized Computing, 11.8,pp. 3349-3354,2020 
[13]. G. Parlier, “Transforming U.S.Army logistics: A strategic “supply chain” 
approach for inventory management”, The Land Warfare Papers, The 
Institute of Land Warfare, 2005. 
[14]. H. Cheng, N. Xiong, A.V. Vasilakos, L.T. Yang, G. Chen, X. Zhuang, 
“Nodes organization for channel assignment with topology preservation 
in multi-radio wireless mesh networks”, Ad Hoc Networks, vol. 10(5), pp. 
760-773, 2012. 
[15]. H. Dai, W. Cheng, “A Memetic Algorithm for Multiskill Resource-
Constrained Project Scheduling Problem under Linear 
Deterioration”, Mathematical Problems in Engineering, 6. 2019. 
[16]. H. H. Hoos, T. Stutzle, Stochastic Local Search: Foundations and 
Applications, Morgan Kaufmann, 2005 
[17]. H. Li, K. Womer, “Stochastic Resource-Constrained Project Scheduling 
and Its Military Applications”, IEEE Trans Computer, 65(12), pp. 3702–
131 
3712, 2016. 
[18]. H. Li, K. Womer, "A Decomposition Approach for Shipboard Manpower 
Scheduling", Military Operations Research, 14, no. 3, pp. 1-24,2009. 
[19]. H. Liu, A. Abraham, C. Grosan, “A Novel Variable Neighborhood 
Particle Swarm Optimization for Multi-objective Flexible Job-Shop 
Scheduling Problems”, Proc. of 2nd International Conference on Digital 
Information Management (ICDIM '07), Volume 1, pages 138 - 145, 2007. 
[20]. H. Maghsoudlou, B. Afshar-Nadjafi, S.T.A Niaki, "Multi-skilled project 
scheduling with level-dependent rework risk; three multi-objective 
mechanisms based on cuckoo search.", Applied Soft Computing, 54,pp. 
46-61, 2017. 
[21]. H. Najafzad, H. Davari-Ardakani, R. Nemati-Lafmejani, "Multi-skill 
project scheduling problem under time-of-use electricity tariffs and shift 
differential payments.", Energy Journal, vol. 168, pp. 619-636, 
Elsevier,2019. 
[22]. J. Błazewicz, J.K.Lenstra, A.H.G.Rinnooy Kan, “Scheduling subject to 
resource constraints: classification and complexity”, Discrete Appl.Math, 
5, pp. 11-24, 1983. 
[23]. J. Kennedy, R. Eberhart, "Particle Swarm Optimization", IEEE 
International Conference on Neural Networks, 1995. 
[24]. J. Lin, L. Zhu, K. Gao, "A genetic programming hyper-heuristic approach 
for the multi-skill resource constrained project scheduling 
problem.", Expert Systems with Applications, 140, 112915, 2020. 
[25]. K. Bibiks, Y.F. Hu, J.P. Li, P. Pillai, A. Smit, "Improved discrete cuckoo 
search for the resource-constrained project scheduling problem.", Applied 
Soft Computing 69, pp. 493-503, 2018 
[26]. K. Price, R. Storn, J. Lampinen, "Differential Evolution - A Practical 
Approach to Global Optimization,", Springer, Berlin, Germany, 2005. 
132 
[27]. Karl Pearson, "The problem of the random walk.", Nature 72.1867, pp. 
342-342, 1905. 
[28]. L. Sahawneh, R.W. Beard, S. Avadhanam, H. Bai, "Chain-based Collision 
Avoidance for UAS Sense-and-Avoid Systems", AIAA Guidance, 
Navigation, and Control Conference, Boston, 8.2013. 
[29]. L. Zhu, J. Lin, Z.J Wang, "A discrete oppositional multi-verse 
optimization algorithm for multi-skill resource constrained project 
scheduling problem.", Applied Soft Computing, 85, 105805, 2019. 
[30]. L.M. Verburgt, "The First Random Walk: A Note on John Venn’s 
Graph.", The Mathematical Intelligencer, 1-5, 2020. 
[31]. M. Skowroński, P.B. Myszkowski, P. Kwiatek, M. Adamski, "Tabu 
Search approach for Multi–Skill Resource–Constrained Project 
Scheduling Problem", Annals of Computer Science and Information 
Systems, Volume 1, Proceedings of the 2013 Federated Conference on 
Computer Science and Information Systems, pp. 153-158, 2013. 
[32]. M. Verma, N. Bhardwaj, A.K.Yadav, “Real Time Efficient Scheduling 
Algorithm for Load Balancing in Fog Computing Environment”, 
Information Technology and Computer Science, 4, pp. 1-10, 2016 
[33]. M.A. Adnan, M.A. Razzaque, “A comparative study of particle swarm 
optimization and Cuckoo search techniques through problem-specific 
distance function”, International Conference on Information and 
Communication Technology (ICoICT), Indonesia, 2013 
[34]. M.A. Mujtaba, H.H. Masjuki, M.A. Kalam, H.C. Ong, M. Gul, M. Farooq, 
M.E. Soudagar, W. Ahmed, M.H. Harith, M.N. Yusoff, "Ultrasound-
assisted process optimization and tribological characteristics of biodiesel 
from palm-sesame oil via response surface methodology and extreme 
learning machine-Cuckoo search.", Renewable Energy, 158, pp. 202-214, 
2020. 
133 
[35]. M.E. Haque, M.F.M. Zain, M.A. Hannan, M. Jamil, H. Johari, "Loss 
monitoring of star topology sensor network based on scheduling algorithm 
for assessing structural health information.", American Journal of Applied 
Sciences, 10.12, pp. 1484-1491, 2013. 
[36]. M.I. Solihin, M.F. Zanil, “Performance comparison of Cuckoo search and 
differential evolution algorithm for constrained optimization”, 
International Engineering Research and Innovation Symposium (IRIS), 
vol. 160(1), pp. 1-7, 2016. 
[37]. M.L. Pinedo, “Scheduling Theory, Algorithms, and Systems”, Springer, 
2012. 
[38]. M.T. Younis, S. Yang. "Hybrid meta-heuristic algorithms for independent 
job scheduling in grid computing", Applied soft computing, 72, pp. 498-
517, 2018. 
[39]. O. Sinnen, “Task scheduling for parallel systems”, Published by 
JohnWiley & Sons, Inc., Hoboken, New Jersey, Vol 60, 2007. 
[40]. O.P. Mejia, M.C. Anselmet, C. Artigues, P. Lopez, "A new RCPSP variant 
to schedule research activities in a nuclear laboratory.", 47th International 
Conference on Computers and Industrial Engineering (CIE47), 2017. 
[41]. P. Stodola, "Hybrid ant colony optimization algorithm applied to the 
multi-depot vehicle routing problem.", Natural Computing, 19, no. 2, pp. 
463-475, 2020. 
[42]. P.B. Myszkowski, M. Laszczyk, I. Nikulin, M. Skowro, “iMOPSE: a 
library for bicriteria optimization in Multi-Skill Resource-Constrained 
Project Scheduling Problem”, Soft Computing Journal, 23: 32397, 2019. 
[43]. P.B. Myszkowski, M. Skowroński, "Specialized genetic operators for 
Multi–Skill Resource–Constrained Project Scheduling Problem", 19th 
International Conference on Soft Computing – Mendel 2013, pp. 57-62, 
2013. 
134 
[44]. P.B. Myszkowski, M. Skowroński, L. Olech, K. Oślizło, "Hybrid Ant 
Colony Optimization in solving Multi–Skill Resource–Constrained 
Project Scheduling Problem", Soft Computing Journal, Volume 19, Issue 
12, pp.3599–3619, 2015. 
[45]. P.B. Myszkowski, M.E. Skowronski, K.Sikora, “A new benchmark 
dataset for Multi-Skill Resource-Constrained Project Scheduling 
Problem”, Computer Science and Information Systems, ACSIS, Vol. 5, 
pp. 129–138, 2015. DOI: 10.15439/2015F273. 
[46]. R. Klein: “Scheduling of Resource-Constrained Projects”, Springer 
Science & Business Media, Vol. 10, 2012. 
[47]. R. Kolisch, A. Sprecher, “PSPLIB-a project scheduling problem library: 
OR software-ORSEP operations research software exchange 
program.”, European journal of operational research, 96(1), pp.205-216, 
1997. 
[48]. R. Nemati-Lafmejani, H. Davari-Ardakani, H. Najafzad. "Multi-mode 
resource constrained project scheduling and contractor selection: 
Mathematical formulation and metaheuristic algorithms", Applied Soft 
Computing, 81,105533,2019. 
[49]. R. Wan, N. Xiong, N.T. Loc, “An energy-efficient sleep scheduling 
mechanism with similarity measure for wireless sensor networks”, 
Human-centric Computing and Information Sciences, vol. 8, 18 2018 
[50]. R.L. Graham, E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan. 
“Optimization and approximation in deterministic sequencing and 
scheduling : a survey”, Annals of Discrete Mathematics, Vol. 5, pp. 287-
326, 1979. 
[51]. S. Javanmard, B. Afshar-Nadjafi, S.T. Niaki, "Preemptive multi-skilled 
resource investment project scheduling problem: Mathematical modeling 
and solution approaches.", Computers & Chemical Engineering, 96, pp. 
135 
55-68, 2017. 
[52]. S. Kavitha, P. Venkumar, "A vibrant crossbreed social spider optimization 
with genetic algorithm tactic for flexible job shop scheduling 
problem.", Measurement and Control, Vol 53, Issue 1-2, 2020. 
[53]. S. Li, S. Han, L. Zhao, C. Gong, X. Liu, "New dandelion algorithm 
optimizes extreme learning machine for biomedical classification 
problems", Computational intelligence and neuroscience, vol. 2017, Sep. 
2017. 
[54]. TNG Investment and Trading Joint Stock Company, 434/1 Bac Kan street 
- Thai Nguyen city, Viet Nam; Website  
[55]. W. Deng, J. Xu, H. Zhao. "An improved ant colony optimization 
algorithm based on hybrid strategies for scheduling problem.", IEEE 
Access, 7, pp. 20281-20292, 2019. 
[56]. W. Guo, J.H. Park, L.T. Yang, A.V. Vasilakos, N. Xiong, G. Chen, 
"Design and Analysis of a MST-Based Topology Control Scheme with 
PSO for Wireless Sensor Networks,", 2011 IEEE Asia-Pacific Services 
Computing Conference, Jeju Island, pp. 360-367, 2011. doi: 
10.1109/APSCC.2011.20. 
[57]. W.Guo, N. Xiong, A. Vasilakos, “Distributed k-connected fault-tolerant 
topology control algorithms with PSO in future autonomic sensor 
systems”, International Journal of Sensor Networks, 12(1), pp. 53-62, 
2012. 
[58]. X. Chen, “American option pricing formula for uncertain financial 
market”, International Journal of Operations Research, Vol. 8, No. 2, pp. 
32–37, 2011 
[59]. X. Zhuang, H. Cheng, N. Xiong, L.T. Yang, "Channel Assignment in 
Multi-Radio Wireless Networks Based on PSO Algorithm,", 2010 5th 
International Conference on Future Information Technology, Busan, pp. 
136 
1-6, 2010. doi: 10.1109/FUTURETECH.2010.5482773. 
[60]. X.S. Yang, “Nature-Inspired Metaheuristic Algorithms”, Luniver Press, 
ISBN-13: 978-1-905986-28-6, 2010. 
[61]. X.S. Yang, S. Deb, “Cuckoo search via Lévy flights”, Proc. of World 
Congress on Nature & Biologically Inspired Computing (NaBIC 2009), 
India. IEEE Publications, USA, pp. 210-214, 2009. 
[62]. Y. Gao, “Uncertain models for single facility location problems on 
networks”, Applied Mathematical Modelling, Vol. 36, No. 6, pp. 2592–
2599, 2012. 
[63]. Website: https://en.wikipedia.org/wiki/Brownian_motion