检索结果-内蒙古大学图书馆

Bi-criteria ant colony optimization algorithm for minimizing makespan and energy consumption on parallel batch machines

引用

APPLIED SOFT COMPUTING 2017年 55卷 226-237页

作者： Jia, Zhao-hong Zhang, Yu-lan Leung, Joseph Y. -T. Li, Kai Minist Educ Key Lab Intelligent Comp & Signal Proc Beijing Peoples R China Anhui Univ Sch Comp Sci & Technol Hefei 230039 Anhui Peoples R China Hefei Univ Technol Sch Management Hefei 230009 Anhui Peoples R China New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA

We investigate the problem of minimizing the makespan and the total electric power cost simultaneously on a set of parallel identical batch-processing machines, where the jobs with non-identical sizes dynamically arrive. To address the bi-criteria problem, a Pareto-based ant colony optimization (PACO) algorithm is proposed. Depending on whether the current batch being delayed after the job is added into, two candidate lists are constructed to narrow the search space. Moreover, heuristic information is designed for each candidate list to guide the search. In addition, the objective-oriented local optimization methods are applied to improve the solution quality. Finally, the proposed algorithm is compared with existing multi objective algorithms through extensive simulation experiments. The experimental results indicate that the proposed algorithm outperforms all of the compared algorithms, especially for large-scale problems. (c) 2017 Elsevier B.V. All rights reserved.

关键词： parallel batch machines Ant colony optimization algorithm Makespan Energy consumption Green manufacturing

来源：评论

学校读者我要写书评

暂无评论

Minimizing total completion time on non-identical parallel batch machines with arbitrary release times using ant colony optimization

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2023年第3期309卷 1024-1046页

作者： Zhang, Han Li, Kai Jia, Zhao -hong Chu, Chengbin Hefei Univ Technol Sch Management Hefei 230009 Peoples R China Minist Educ Key Lab Proc Optimizat & Intelligent Decis Making Hefei 230009 Peoples R China Anhui Univ Sch Comp Sci & Technol Hefei 230039 Peoples R China Fuzhou Univ Sch Econ & Management Fuzhou 350116 Peoples R China Univ Gustave Eiffel ESIEE Paris COSYS GRETTIA F-77454 Marne La Vallee France

This paper considers the problem of scheduling a group of jobs with arbitrary release times, non-identical sizes, and different processing times on non-identical parallel batch processing machines to minimize the total completion time. A mixed-integer programming (MIP) model is firstly constructed in this paper to solve this problem. Then since the studied problem is strongly NP-hard, a modified elite ant system algorithm with the local search (MEASL) is also proposed to solve it, which is compared with several meta-heuristic algorithms and the commercial optimization solver (Gurobi) through extensive simulation experiments. Finally, the experimental results verify the effectiveness of the proposed algorithm.(c) 2023 Elsevier B.V. All rights reserved.

关键词： Scheduling parallel batch machines Non-identical capacities Total completion time Ant colony optimization

来源：评论

学校读者我要写书评

暂无评论

A meta-heuristic to minimize makespan for parallel batch machines with arbitrary job sizes

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2015年第3期240卷 649-665页

作者： Jia, Zhao-hong Leung, Joseph Y. -T. Anhui Univ Minist Educ Key Lab Intelligent Comp & Signal Proc Hefei 230039 Anhui Peoples R China New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA

We consider the problem of scheduling a set of n jobs with arbitrary job sizes on a set of m identical and parallel batch machines so as to minimize the makespan. Motivated by the computational complexity of the problem, we propose a meta-heuristic based on the max-min ant system method. Computational experiments are performed with randomly generated test data. The results show that our algorithm outperforms several of the previously studied algorithms. (C) 2014 Elsevier B.V. All rights reserved.

关键词： Meta-heuristic parallel batch machines Max-min ant system NP-hard

来源：评论

学校读者我要写书评

暂无评论

An ACO algorithm for makespan minimization in parallel batch machines with non-identical job sizes and incompatible job families

引用

APPLIED SOFT COMPUTING 2016年 38卷 395-404页

作者： Jia, Zhao-hong Wang, Chao Leung, Joseph Y. -T. Minist Educ Key Lab Intelligent Comp & Signal Proc Beijing Peoples R China Anhui Univ Sch Comp Sci & Technol Hefei 230039 Anhui Peoples R China Hefei Univ Technol Sch Management Hefei 230009 Anhui Peoples R China New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA

We study the problem of scheduling a set of N jobs with non-identical job sizes from F different families on a set of M parallel batch machines;the objective is to minimize the makespan. The problem is known to be NP-hard. A meta-heuristic based on Max-Min Ant System (MMAS) is presented. The performance of the algorithm is compared with several previously studied algorithms by computational experiments. According to our results, the average distance between the solutions found by our proposed algorithm and the lower bounds is about 4% less than that of the best of all the compared algorithms, demonstrating that our algorithm outperforms the previously studied algorithms. (C) 2015 Elsevier B.V. All rights reserved.

关键词： parallel batch machines Max-Mm Ant System N- hard Incompatible job families Makespan

来源：评论

学校读者我要写书评

暂无评论

Effective heuristic for makespan minimization in parallel batch machines with non-identical capacities

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 2015年 169卷 1-10页

作者： Jia, Zhao-hong Li, Kai Leung, Joseph Y-T Anhui Univ Key Lab Intelligent Comp & Signal Proc Minist Educ Hefei 230039 Anhui Peoples R China Hefei Univ Technol Sch Management Hefei 230009 Anhui Peoples R China New Jersey Inst Technol Dept Comp Sci Newark NJ 07102 USA

We consider the problem of scheduling a set of n jobs with arbitrary job sizes on a set of m parallel batch machines with non-identical capacities;the objective is to minimize the makespan. The problem is known to be NP-hard. A heuristic based on the First-Fit-Decreasing (FFD) rule is presented as well as a meta-heuristic based on Max-Min Ant System (MMAS). The performances of the two heuristics are compared with a previously studied heuristic by computational experiments. The results show that both proposed algorithms outperform the previously studied heuristic. Moreover, the MMAS heuristic obtains better solutions compared with the FFD heuristic. (C) 2015 Elsevier B.V. All rights reserved.

关键词： parallel batch machines Heuristic Max-Min Ant System NP-hard Non-identical machine capacity Makespan

来源：评论

学校读者我要写书评

暂无评论

A best online algorithm for scheduling on two parallel batch machines

引用

THEORETICAL COMPUTER SCIENCE 2009年第21-23期410卷 2291-2294页

作者： Tian, Ji Fu, Ruyan Yuan, Jinjiang Zhengzhou Univ Dept Math Zhengzhou 450052 Henan Peoples R China

We consider the online scheduling on two parallel batch machines with infinite batch size to minimize makespan, where jobs arrive over time. That is, all information of a job is not available until it is released. For this online scheduling problem, Nong et al. [Q.Q. Nong. T.C.E. Cheng, C.T. Ng, An improved online algorithm for scheduling on two Unrestrictive parallel batch processing machines, Operations Research Letters, 36 (2008) 584-588] have provided an online algorithm with competitive ratio no greater than root 2. We show that this bound is tight for the problem. Furthermore we give a new best possible online algorithm with a tighter structure. (C) 2009 Elsevier B.V. All rights reserved.

关键词： Online scheduling parallel batch machines Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

A best possible deterministic on-line algorithm for minimizing makespan on parallel batch machines

引用

JOURNAL OF SCHEDULING 2012年第1期15卷 77-81页

作者： Liu, Peihai Lu, Xiwen Fang, Yang E China Univ Sci & Technol Sch Sci Shanghai 200237 Peoples R China

We study on-line scheduling on parallel batch machines. Jobs arrive over time. A batch processing machine can handle up to B jobs simultaneously. The jobs that are processed together form a batch and all jobs in a batch start and are completed at the same time. The processing time of a batch is given by the processing time of the longest job in the batch. The objective is to minimize the makespan. We deal with the unbounded model, where B is sufficiently large. We first show that no deterministic on-line algorithm can have a competitive ratio of less than 1 + (root m(2) + 4 - m)/2, where m is the number of parallel batch machines. We then present an on-line algorithm which is the one best possible for any specific values of m.

关键词： Scheduling parallel batch machines On-line

来源：评论

学校读者我要写书评

暂无评论

Fair scheduling on parallel batch machines with non-identical capacities

引用

ENGINEERING OPTIMIZATION 2024年

作者： Zhang, Cui-Lin Fan, Guo-Qiang Wang, Jun-Qiang Xian Aeronaut Univ Sch Econ & Management Xian Peoples R China Xidian Univ Sch Econ & Management Xian Peoples R China Northwestern Polytech Univ Performance Anal Ctr Prod & Operat Syst PacPos Xian Peoples R China Northwestern Polytech Univ Dept Ind Engn Xian Peoples R China

The fairness of jobs from agents is considered in an advanced manufacturing factory and the fair scheduling of jobs on parallel batch machines is studied for two competing agents. Each agent and the system aim to minimize the makespan of their own jobs and the weighted sum makespans of the two agents, respectively. A modified full-batch longest processing time (MFBLPT) algorithm is proposed to minimize the makespan, and a Kalai-Smorodinsky fairness (KSF) algorithm is proposed to obtain fair schedules. These algorithms are analysed based on worst-case ratios, and the results show that these ratios are related to the workloads and importance of agents. Computational experiments are conducted to compare the performance of algorithm KSF with that of machine-centric and agent-centric algorithms. The results show that the pursuance of fairness leads to interest losses of a system, and that a proper preference of an agent leads to good performance of algorithm KSF.

关键词： Fair scheduling parallel batch machines approximation algorithm worst-case ratio

来源：评论

学校读者我要写书评

暂无评论

A multi-objective co-evolutionary algorithm of scheduling on parallel non-identical batch machines

引用

EXPERT SYSTEMS WITH APPLICATIONS 2021年 167卷 114145-114145页

作者： Wang, Yan Jia, Zhao-hong Li, Kai Anhui Univ Key Lab Intelligent Comp & Signal Proc Minist Educ Hefei 230601 Anhui Peoples R China Anhui Univ Sch Comp Sci & Technol Hefei 230039 Anhui Peoples R China Hefei Univ Technol Sch Management Hefei 230009 Anhui Peoples R China

This paper investigates the problem scheduling a set of jobs on parallel batch processing machines with different capacities and non-identical processing powers for minimizing the makespan and the total energy consumption, where the jobs have non-identical sizes, dynamical arrival time and different processing time. To address the bi-objective optimization problem, a three-populations co-evolutionary algorithm is proposed, which is based on exploration and coordination searches among three colonies. For guaranteeing the diversity of solutions, an adaptive search strategy based on the largest angle among adjacent solutions is designed, and a new method is proposed to select ants to update pheromone trails for improving the convergence of solutions. Finally, the proposed algorithm is compared with the existing multi-objective algorithms through extensive simulated experiments, and the simulated results are statistically analyzed. And the experimental results show that the proposed algorithm outperforms all the compared algorithms, which verify the validity of the algorithm proposed in this paper.

关键词： Co-evolution parallel batch machines Adaptive search Makespan Total energy consumption

来源：评论

学校读者我要写书评

暂无评论

An ant colony-based algorithm for integrated scheduling on batch machines with non-identical capacities

引用

APPLIED INTELLIGENCE 2022年第2期52卷 1752-1769页

作者： Jia, Zhao-hong Cui, Yu-fei Li, Kai Minist Educ Key Lab Intelligent Comp & Signal Proc Hefei Peoples R China Anhui Univ Sch Comp Sci & Technol Hefei 230039 Peoples R China Hefei Univ Technol Sch Management Hefei 230009 Peoples R China

In this paper, a production-distribution scheduling problem with non-identical batch machines and multiple vehicles is considered. In the production stage, n jobs are grouped into batches, which are processed on m parallel non-identical batch machines. In the distribution stage, there are multiple vehicles with identical capacities to deliver jobs to customers after the jobs are processed. The objective is to minimize the total weighted tardiness of the jobs. Considering the NP-hardness of the studied problem, an algorithm based on ant colony optimization is presented. A new local optimization strategy called LOC is proposed to improve the local exploitation ability of the algorithm and further search the neighborhood solution to improve the quality of the solution. Moreover, two interval candidate lists are proposed to reduce the search for the feasible solution space and improve the search speed. Furthermore, three objective-oriented heuristics are developed to accelerate the convergence of the algorithm. To verify the performance of the proposed algorithm, extensive experiments are carried out. The experimental results demonstrate that the proposed algorithm can provide better solutions than the state-of-the-art algorithms within a reasonable time.

关键词： parallel batch machines Non-identical machine capacities Production and distribution Ant colony optimization algorithm Total weighted tardiness

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：