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

Arc-flow approach for single batch-processing machine scheduling

COMPUTERS & OPERATIONS RESEARCH 2021年 134卷 105394-105394页

作者： Trindade, Renan Spencer Bassi de Araujo, Olinto Cesar Fampa, Marcia Ecole Polytech Inst Polytech Paris CNRS Lab Informat 1 Rue Honore Estienne dOrves F-91120 Palaiseau France Univ Fed Santa Maria Colegio Tecn Ind Santa Maria Ave Roraima 1000Predio 05 BR-97105900 Santa Maria RS Brazil Univ Fed Rio de Janeiro Inst Alberto Luiz Coimbra Posgrad & Pesquisa Engn Inst Matemat Caixa Postal 68511 BR-21941972 Rio De Janeiro RJ Brazil

We address the problem of scheduling jobs with non-identical sizes and distinct processing times on a single batch-processing machine, aiming at minimizing the makespan. The extensive literature on this NP-hard problem mostly focuses on heuristics. Using an arc-flow based optimization approach, we construct a novel formulation that represents it as a problem of determining flows in graphs. The size of the formulation increases with the machine capacity and with the number of distinct sizes and processing times among the jobs, but it does not increase with the number of jobs, which makes it very effective to solve large instances to optimality, especially when multiple jobs have equal size and processing time. We compare our model to other models from the literature, showing its clear superiority on benchmark instances and proving optimality of random instances with up to 100 million jobs.

关键词： Scheduling batch-processing machine Makespan Arc-flow Symmetry

来源：评论

学校读者我要写书评

暂无评论

A modified particle swarm optimization algorithm for a batch-processing machine scheduling problem with arbitrary release times and non-identical job sizes

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2018年 123卷 67-81页

作者： Zhou, Hongming Pang, Jihong Chen, Ping-Kuo Chou, Fuh-Der Wenzhou Univ Coll Mech & Elect Engn Wenzhou 325035 Zhejiang Peoples R China Wenzhou Business Coll Wenzhou 325035 Zhejiang Peoples R China

This paper presents a modified particle swarm optimization (MPSO) algorithm to minimize the maximum lateness for the single batch-processing machine problem with non-identical job sizes and release dates. The MPSO algorithm incorporated a diversification and a local search strategy into a basic particle swarm optimization algorithm. This incorporation enables the proposed algorithm to have a good balance between exploration and exploitation that yields high search efficiency. Additionally, a dynamic programming method is proposed to calculate a relevant value for each particle. The MPSO algorithm was tested in problems from the literature without release dates and newly generated problems with release dates. Computational results show the advantages of combining the diversification strategy, and local search methods. The performance of the proposed MPSO is competitive. For the problems without release dates, the MPSO algorithm could find 80 optimal solutions and improve 68 solutions for all benchmark instances. For the problems with job release dates, the MPSO algorithm also significantly outperformed the other two algorithms with respect to solution quality within the same computational time.

关键词： batch-processing machine Non-identical job sizes Scheduling Particle swarm optimization

来源：评论

学校读者我要写书评

暂无评论

An ACO-based intercell scheduling approach for job shop cells with multiple single processing machines and one batch processing machine

引用

JOURNAL OF INTELLIGENT MANUFACTURING 2016年第2期27卷 283-296页

作者： Li, Dongni Meng, Xianwen Li, Miao Tian, Yunna Beijing Inst Technol Sch Comp Sci Beijing Key Lab Intelligent Informat Technol Beijing 100081 Peoples R China

Intercell transfers are inevitable for the manufacturing of complicated products, which disrupts the philosophy of cellular manufacturing and leads new challenges to the field of production scheduling. The issue of intercell scheduling is analyzed in the context of a cellular manufacturing system consisting of multiple single-processing machines and one batch-processing machine, which is derived from the actual manufacturing of complicated assemblies in the equipment manufacturing industry. Since the two types of machines are different from, even contrary to, each other in some constraint conditions, a combinational ant colony optimization (CACO) approach is developed in this paper, which designs two structures for the single-processing machines and the batch-processing machine, respectively. By updating pheromone trails integratedly and scheduling the single-processing operations and the batch-processing operations simultaneously, cooperative optimization for the two types of machines is achieved in the CACO. Minimizing the maximum completion time is taken as the scheduling objectives. Computational results show that the CACO has significant advantages comparing with other approaches and the CPLEX, and is especially suitable for the large dimension problems.

关键词： Cellular manufacturing systems batch-processing machine Single processing machine Intercell scheduling Ant colony optimization

来源：评论

学校读者我要写书评

暂无评论

GRASP to minimize makespan for a capacitated batch-processing machine

引用

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY 2013年第1-4期68卷 407-414页

作者： Damodaran, Purushothaman Ghrayeb, Omar Guttikonda, Mallika Chowdary No Illinois Univ Dept Ind & Syst Engn De Kalb IL 60115 USA

This paper presents a Greedy Randomized Adaptive Search Procedure (GRASP) to minimize the makespan of a capacitated batch-processing machine. Given a set of jobs and their processing times and sizes, the objective is to group these jobs into batches and schedule the batches on a single batch-processing machine such that the time taken to complete the last batch of jobs (or makespan) is minimized. The batch-processing machine can process a batch of jobs simultaneously as long as the total size of all the jobs in that batch does not exceed the machine capacity. The batch-processing time is equal to the longest processing time for a job in the batch. It has been shown that the problem under study is non-deterministic polynomial-time hard. Consequently, a GRASP approach was developed. The solution quality of GRASP was compared to other solution approaches such as simulated annealing, genetic algorithm, and a commercial solver through an experimental study. The study helps to conclude that GRASP outperforms other solution approaches, especially on larger problem instances.

关键词： GRASP batch-processing machine Makespan Metaheuristics

来源：评论

学校读者我要写书评

暂无评论

Makespan minimization on single batch-processing machine via ant colony optimization

引用

COMPUTERS & OPERATIONS RESEARCH 2012年第3期39卷 582-593页

作者： Xu, Rui Chen, Huaping Li, Xueping Univ Tennessee Dept Ind & Informat Engn Knoxville TN 37996 USA Univ Sci & Technol China Sch Management Hefei 230026 Peoples R China

This paper investigates the problem of minimizing makespan on a single batch-processing machine, and the machine can process multiple jobs simultaneously. Each job is characterized by release time, processing time, and job size. We established a mixed integer programming model and proposed a valid lower bound for this problem. By introducing a definition of waste and idle space (WIS), this problem is proven to be equivalent to minimizing the WIS for the schedule. Since the problem is NP-hard, we proposed a heuristic and an ant colony optimization (ACO) algorithm based on the theorems presented. A candidate list strategy and a new method to construct heuristic information were introduced for the ACO approach to achieve a satisfactory solution in a reasonable computational time. Through extensive computational experiments, appropriate ACO parameter values were chosen and the effectiveness of the proposed algorithms was evaluated by solution quality and run time. The results showed that the ACO algorithm combined with the candidate list was more robust and consistently outperformed genetic algorithm (GA), CPLEX, and the other two heuristics, especially for large job instances. (C) 2011 Elsevier Ltd. All rights reserved.

关键词： Scheduling batch-processing machine Makespan (C-max) Ant colony optimization

来源：评论

学校读者我要写书评

暂无评论

A note on the algorithm LPT-FF for a flowshop scheduling with two batch-processing machines

引用

OPTIMIZATION LETTERS 2016年第1期10卷 109-118页

作者： Dong, Jianming Hu, Jueliang Lin, Guohui Zhejiang Sci Tech Univ Dept Math Hangzhou 310018 Zhejiang Peoples R China Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada

A flowshop scheduling problem with two batch-processing machines is investigated in this paper, with the optimization goal to minimize the makespan. When the job processing times on the two machines are positively correlated, a -approximation algorithm for this NP-hard problem was previously proposed. We show that this algorithm has a worst-case performance guarantee of .

关键词： Flowshop scheduling batch-processing machine Bin-packing Approximation algorithm Worst-case performance analysis

来源：评论

学校读者我要写书评

暂无评论

Solving single batch-processing machine problems using an iterated heuristic

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2011年第14期49卷 4245-4261页

作者： Wang, Hui-Mei Vanung Univ Dept Management & Informat Technol Tao Yuan Taiwan

This article considers the problem of minimising total weighted tardiness on a batch-processing machine with compatible product families, job release dates and non-identical job sizes. A batch-processing machine can process several jobs as long as the total size of jobs in the batch does not exceed the machine's capacity. All jobs in the batch are started and completed at the same time. batch processing time is equal to the longest job processing time among jobs in the batch. This article proposes a two-phase heuristic, in which a population-based reasoning approach is developed to determine the sequence of jobs based on their intensity values at positions in the first phase, and a dynamic programming algorithm to divide the ordered jobs into batches sequentially. An iterated heuristic is also proposed to improve solution quality further. Computational results show that high-quality solutions can be obtained by the proposed heuristic algorithms in a very short time.

关键词： batch-processing machine total weighted tardiness scheduling

来源：评论

学校读者我要写书评

暂无评论

A bi-objective scheduling problem on batch machines via a Pareto-based ant colony system

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 2013年第1期145卷 371-386页

作者： Xu, Rui Chen, Huaping Li, Xueping Univ Sci & Technol China Sch Comp Sci & Technol Hefei 230026 Peoples R China Univ Tennessee Dept Ind & Syst Engn Knoxville TN 37996 USA

This research aims to minimize the bi-criteria of makespan and maximum tardiness on a set of identical batch-processing machines arranged in parallel. Each machine can process multiple jobs simultaneously as long as the machine capacity is not exceeded. Each job is defined by its processing time, ready time, due date, and size. The processing time and ready time of a batch are represented by the largest processing time and release time among all jobs in the batch, respectively. For this problem, a scheduling algorithm based on the framework of a multi-objective ant colony optimization (MOACO) approach called a Pareto-based ant colony system (PACS) was developed. Based on the constructive characteristics of PACS, a new mechanism of solution construction was introduced so that the proposed algorithm had the ability to explore the entire solution space. Moreover, corresponding to the new construction mechanism, a candidate list strategy and a form of dynamic heuristic information were developed to reduce the search space and direct the search toward the promising regions, respectively. Through extensive computational experiments with various problem instances, the effectiveness of the proposed algorithm was evaluated by measuring the computational efficiency and solution quality. The experiment results demonstrated that PACS had a superior performance compared to other benchmark algorithms, especially for large job instances. (C) 2013 Elsevier B.V. All rights reserved.

关键词： Scheduling batch-processing machine Makespan Maximum tardiness Multi-objective ant colony optimization

来源：评论

学校读者我要写书评

暂无评论

Scheduling a single batch-processing machine with arbitrary job sizes and incompatible job families: An ant colony framework

引用

JOURNAL OF THE OPERATIONAL RESEARCH SOCIETY 2008年第9期59卷 1269-1280页

作者： Kashan, A. H. Karimi, B. Amir Kabir Univ Technol Dept Ind Engn Tehran *** Iran

This paper investigates the first attempt on the batch-processing machine scheduling problem, where the machine can process multiple jobs simultaneously, using an ant colony optimization metaheuristic. We consider the scheduling problem of a single batch-processing machine with incompatible job families and the performance measure of minimizing total weighted completion time. Jobs of a given family have an identical processing time and are characterized by arbitrary sizes and weights. Based on a number of developed heuristic approaches, we propose an ant colony framework (ACF) in two versions, which are distinguished by the type of embedded heuristic information. Each version is also investigated in two formats, that is the pure ACF and the hybridized ACF. To verify the performance of our framework, comparisons are made based on using a set of well-known existing heuristic and meta-heuristic algorithms taken from the literature, on a diverse set of artificially generated test problem instances. Computational results show the high performance of the proposed framework and signify its ability to outperform the comparator algorithms in most cases as the problem size increases.

关键词： scheduling batch-processing machine total weighted completion time ant colony optimization

来源：评论

学校读者我要写书评

暂无评论

Effective hybrid genetic algorithm for minimizing makespan on a single-batch-processing machine with non-identical job sizes

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2006年第12期44卷 2337-2360页

作者： Kashan, A. H. Karimi, B. Jolai, F. Amirkabir Univ Technol Dept Ind Engn Tehran Iran Univ Tehran Fac Engn Dept Ind Engn Tehran Iran

The paper addresses minimizing makespan by a genetic algorithm (GA) for scheduling jobs with non-identical sizes on a single-batch-processing machine. A batch-processing machine can process up to B jobs simultaneously. The processing time of a batch is equal to the longest processing time among all jobs in the batch. Two different GAs are proposed based on different encoding schemes. The first is a sequence-based GA (SGA) that generates random sequences of jobs using GA operators and applies the batch first fit heuristic to group the jobs. The second is a batch-based hybrid GA (BHGA) that generates random batches of jobs using GA operators and ensures feasibility by using knowledge of the problem based on a heuristic procedure. A greedy local search heuristic based on the problem characteristics is hybridized with a BHGA that has the ability of steering efficiently the search toward the optimal or near-optimal schedules. The performance of proposed GAs is compared with a simulated annealing (SA) approach proposed by Melouk et al. (Melouk, S., Damodaran, P. and Chang, P.Y., Minimizing makespan for single machine batch processing with non-identical job sizes using simulated annealing. Int. J. Prod. Econ., 2004, 87, 141-147) and also against a modified lower bound proposed for the problem. Computational results show that BHGA performs considerably well compared with the modified lower bound and significantly outperforms the SGA and SA in terms of both quality of solutions and required runtimes.

关键词： scheduling batch-processing machine makespan genetic algorithm simulated annealing

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：