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

identical parallel machine scheduling with assurance of maximum waiting time for an emergency job

COMPUTERS & OPERATIONS RESEARCH 2020年 118卷 104918-104918页

作者： Wang, Shijin Wu, Ruochen Chu, Feng Yu, Jianbo Tongji Univ Sch Econ & Management Shanghai 200092 Peoples R China Univ Paris Saclay Univ Evry Lab IBISC Evry 91025 France Fuzhou Univ Sch Econ & Management Fuzhou 350116 Peoples R China Tongji Univ Sch Mech Engn Shanghai 710049 Peoples R China

Currently, customer satisfaction is playing an increasingly vital role in both manufacturing and service industries. Assuring an acceptable waiting time to customers is considered as an effective approach to improve customer satisfaction. In this study, an identical parallel machine scheduling problem assuring the maximum waiting time for an emergency job which arrives at any time is investigated. A mixed integer programming model is formulated, based on which a variant formulation is generated. The formulations are further enhanced by various techniques, which forms two formulation-based methods. Two objectives, makespan and total completion time, are considered separately. Regarding the makespan, the worst-case approximation ratios of the classical heuristic rules are deduced. For the total completion time, efficient bounds are provided and the NP-hardness of the problem is proved. Heuristic methods based on the classical dispatch rules are developed, for both the cases. Extensive computational experiments are conducted, based on which the performances of the formulation-based methods and heuristics are compared, the relationship between the objective values and the assured maximum waiting time for an emergency job is explored, and a few observations and managerial insights are obtained. (C) 2020 Elsevier Ltd. All rights reserved.

关键词： identical parallel machine scheduling Emergency job Maximum waiting time Makespan Total completion time

来源：评论

学校读者我要写书评

暂无评论

identical parallel machine scheduling to minimise makespan and total weighted completion time: a column generation approach

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2013年第23-24期51卷 7091-7104页

作者： Xu, Jingyang Nagi, Rakesh SUNY Coll Buffalo Dept Ind & Syst Engn Buffalo NY 14222 USA

In this paper, we consider an identical parallel machine scheduling problem with the objective to minimise the sum of weighted completion time and makespan, which is denoted as P-m parallel to Sigma w(j)C(j)+C-max, w(j) >= 0. We formulate the problem as a mixed integer programming (MIP) problem based on the properties of an optimal schedule. Leveraging the Dantzig-Wolfe decomposition method, the problem is solved in a Column Generation (CG) framework with a master problem and an NP-hard pricing problem. With derived lower bounds, we are able to solve the problems to near optimality in a short time. The CG procedure is also used in the special conditions when P-m parallel to Sigma w(j)C(j)+C-max becomes P-m parallel to Sigma w(j)C(j) or P-m parallel to C-max. Comparison experiments between the CG procedure and CPLEX are carried out for a set of synthetically generated scenarios. Computational experiments demonstrate that our CG procedure provides near-optimal solutions in a short time.

关键词： identical parallel machine scheduling makespan weighted completion time column generation branch-and-price

来源：评论

学校读者我要写书评

暂无评论

A genetic algorithm for fuzzy identical parallel machine scheduling of minimising total weighted tardiness under resource constraint

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2024年第21期62卷 7619-7643页

作者： Li, Kai Xu, Liping Zhang, Han Chen, Jianfu Hefei Univ Technol Sch Management Hefei Anhui Peoples R China Minist Educ Key Lab Proc Optimizat & Intelligent Decis Making Hefei Anhui Peoples R China Anhui Normal Univ Sch Econ & Management Wuhu Anhui Peoples R China Hefei Univ Technol Sch Management Hefei 230009 Anhui Peoples R China

Due to the severity of resource consumption and uncertainty in orders, new challenges have arisen for production scheduling in enterprises. This paper studies the scheduling problem of minimising the total weighted tardiness for jobs with fuzzy processing times and due dates on identical parallel machines with resource constraint. To address this research problem, we first propose methods to calculate the upper bound of resource consumption and the maximum number of machines that can be used, effectively reducing the search space and improving the algorithm's efficiency. Secondly, a local search algorithm based on job swapping is proposed to enhance the algorithm's performance. Then, repair algorithms based on job removal and job swapping are designed to repair infeasible solutions. Finally, we propose a fuzzy genetic algorithm (FGALS) to solve the problem based on the above elements. Through extensive simulation experiments, the effectiveness and efficiency of the FGALS algorithm are verified by comparing it with commercial solver Gurobi and several meta-heuristic algorithms.

关键词： Resource constraint total weighted tardiness fuzzy scheduling identical parallel machine scheduling genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Approximation algorithms for the min-max regret identical parallel machine scheduling problem with outsourcing and uncertain processing time

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2021年第15期59卷 4579-4592页

作者： Wang, Shijin Cui, Wenli Tongji Univ Sch Econ & Management Shanghai Peoples R China

We consider the robust (min-max regret) version of identical parallel machine scheduling problem, in which jobs may be outsourced to balance total cost against production efficiency. The total cost is measured in terms of the total completion time of jobs processed in-house and the cost of outsourcing the rest. Processing times of in-house jobs are uncertain and they are described as two types of scenarios: discrete and interval. The objective is to obtain a robust (min-max regret) decision that minimises the absolute deviation of total cost from the optimal solution under the worst-case scenario. We first prove the worst-case scenario for any feasible solution. For the interval scenario, we further prove that the maximum regret value can be obtained in polynomial time for any feasible schedule. We also prove that for any discrete scenario, the minimum total cost can be obtained in polynomial time. Since the problem with the interval scenario is strongly NP-hard, we then transform the problem into an equivalent robust single machine scheduling problem. Finally, we develop 2-approximation algorithms for the problem with discrete and interval scenarios, respectively. These results are helpful for bridging the scheduling theory and practice in identical parallel machining environments with outsourcing and uncertain processing times.

关键词： identical parallel machine scheduling min-max regret uncertainty approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Minimising total tardiness for the identical parallel machine scheduling problem with splitting jobs and sequence-dependent setup times

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2020年第6期58卷 1628-1643页

作者： Kim, Jae-Gon Song, Seokwoo Jeong, BongJoo Incheon Natl Univ Dept Ind & Management Engn Incheon South Korea Weber State Univ Dept Supply Chain & Management Informat Syst Ogden UT 84408 USA Hannam Univ Dept Ind & Management Engn Daejeon South Korea

This paper focuses on an identical parallel machine scheduling problem with minimising total tardiness of jobs. There are two major issues involved in this scheduling problem;(1) jobs which can be split into multiple sub-jobs for being processed on parallel machines independently and (2) sequence-dependent setup times between the jobs with different part types. We present a novel mathematical model with meta-heuristic approaches to solve the problem. We propose two encoding schemes for meta-heuristic solutions and three decoding methods for obtaining a schedule from the meta-heuristic solutions. Six different simulated annealing algorithms and genetic algorithms, respectively, are developed with six combinations of two encoding schemes and three decoding methods. Computational experiments are performed to find the best combination from those encoding schemes and decoding methods. Our findings show that the suggested algorithm provides not only better solution quality, but also less computation time required than the commercial optimisation solvers.

关键词： identical parallel machine scheduling total tardiness job splitting sequence-dependent setup time solution encoding and decoding simulated annealing genetic algorithm

来源：评论

学校读者我要写书评

暂无评论

Bi-objective identical parallel machine scheduling to minimize total energy consumption and makespan

引用

JOURNAL OF CLEANER PRODUCTION 2018年 193卷 424-440页

作者： Wang, Shijin Wang, Xiaodong Yu, Jianbo Ma, Shuan Liu, Ming Tongji Univ Sch Econ & Management Dept Management Sci & Engn Shanghai 200029 Peoples R China Tongji Univ Sch Mech Engn Dept Ind Engn Shanghai 200029 Peoples R China

Currently, energy consumption reduction is playing a more and more important role in production and manufacturing, especially for energy-intensive industries. An optimal production scheduling can help reduce unnecessary energy consumption. This paper considers an identical parallel machine scheduling problem to minimize simultaneously two objectives: the total energy consumption (TEC) and the makespan. To tackle this NP-hard problem, an augmented c-constraint method is applied to obtain an optimal Pareto front for small-scale instances. For medium-and large-scale instances, a constructive heuristic method with a local search strategy is proposed and the NSGA-Il algorithm is applied to obtain good approximate Pareto fronts. Extensive computational experiments on randomly generated data and a real-world case study are conducted. The result shows the efficiency and effectiveness of the proposed methods. (C) 2018 Elsevier Ltd. All rights reserved.

关键词： identical parallel machine scheduling Makespan Total energy consumption Augmented epsilon-constraint method Constructive heuristic NSGA-II

来源：评论

学校读者我要写书评

暂无评论

A note on exact and heuristic algorithms for the identical parallel machine scheduling problem

引用

JOURNAL OF HEURISTICS 2012年第6期18卷 939-942页

作者： Dell'Amico, Mauro Iori, Manuel Martello, Silvano Monaci, Michele Univ Bologna DEIS I-40136 Bologna Italy Univ Modena & Reggio Emilia DISMI I-42122 Reggio Emilia Italy Univ Padua DEI I-35131 Padua Italy

A recent paper (Davidovic et al., J. Heuristics, 18:549-569, 2012) presented a bee colony metaheuristic for scheduling independent tasks to identical processors, evaluating its performance on a benchmark set of instances from the literature. We examine two exact algorithms from the literature, the former published in 1995, the latter in 2008 (and not cited by the authors). We show that both such algorithms solve to proven optimality all the considered instances in a computing time that is several orders of magnitude smaller than the time taken by the new algorithm to produce an approximate solution.

关键词： identical parallel machine scheduling Exact algorithms Metaheuristic algorithms

来源：评论

学校读者我要写书评

暂无评论

Bi-objective Optimization in identical parallel machine scheduling Problem

Bi-objective Optimization in Identical Parallel Machine Sche...

引用

4th International Conference on Swarm, Evolutionary, and Memetic Computing (SEMCCO)

作者： Bathrinath, Sankaranarayanan Sankar, S. Saravana Ponnambalam, S. G. Kannan, B. K. V. Kalasalingam Univ Krishanankoil Tamil Nadu India Monash Univ Dept Mech Petaling Jaya Malaysia Theni Kammavar Sangam Coll Technol Theni Tamil Nadu India

ISBN: (纸本)9783319037530;9783319037523

This paper presents bi-objective identical parallel machine scheduling problem with minimization of weighted sum of makespan and number of tardy jobs simultaneously. It is a known fact that identical parallel machine scheduling problem with makespan and number of tardy jobs based criteria is NP hard. Metaheuristics has become most important choice for solving NP hard problems because of their multi-solution and strong neighborhood search capabilities in a reasonable time. In this work Simulated Annealing Algorithm (SA) and Genetic Algorithm (GA) has been proposed to optimize two different objectives namely (i) minimization of make span (ii) minimization of number of tardy jobs using combined objective function (COF). The effectiveness of the proposed algorithm have been analyzed by means of benchmark problem taken from the literatures and relative performance measures for the algorithm have also been computed and analyzed. Computational results show that GA outperforms SA by a considerable margin.

关键词： identical parallel machine scheduling Genetic Algorithm Simulated Annealing Algorithm make span number of tardy jobs

来源：评论

学校读者我要写书评

暂无评论

An exact algorithm for identical parallel machine scheduling under scenarios 3

An exact algorithm for identical parallel machine scheduling...

引用

3rd World Conference on Mechanical Engineering and Intelligent Manufacturing (WCMEIM)

作者： Xie Han-Xin Wang Bing Shanghai Univ Sch Mechatron Engn & Automat Shanghai Peoples R China

ISBN: (纸本)9781665441094

This paper discusses an uncertain identical parallel machine scheduling problem. Discrete scenario set is used to describe the uncertain processing times in actual production conditions. Objective of this problem is to minimize the mean makespan among all scenarios, which reflects solution optimality in uncertain environment. The concept of mean scenario is defined in this paper and is used to transform the model of mean makespan under scenarios into traditional deterministic identical parallel machine problem. The cutting plane algorithm is used on the basis of the mean scenario to solve the problem. The developed algorithm was applied in extensive test cases, involving different sizes and parameters. The computational results show that this proposed algorithm can solve this parallel machine model in reasonable time and can be applied in practical problems.

关键词： manufacturing discrete scenarios identical parallel machine scheduling cutting plane algorithm exact algorithm

来源：评论

学校读者我要写书评

暂无评论

VNS-Based Heuristic for identical parallel machine scheduling Problem

VNS-Based Heuristic for Identical Parallel Machine Schedulin...

引用

International Conference on Artificial Intelligence and Evolutionary Algorithms in Engineering Systems (ICAEES)

作者： Bathrinath, S. Sankar, S. Saravana Ponnambalam, S. G. Leno, I. Jerin Kalasalingam Univ Virudunagar Tamil Nadu India Monash Univ Malaysia Bandar Sunway 46150 Selangor Malaysia Natl Coll Engn Tirunelveli Tamil Nadu India

ISBN: (纸本)9788132221265;9788132221258

Minimization of make span and minimization of number of tardy jobs in identical parallel machine scheduling problems are proved to be NP-hard problems. Many researchers have attempted to solve these combinatorial optimization problems by employing different heuristic algorithms. While providing a satisfactory solution to the production environment for each of the above-said objectives, still remains as a challenge, most of the time, the need has been to have satisfactory solutions optimizing simultaneously the above-said two objectives. In this research work, an attempt is made to address this issue and heuristic algorithms using simulated annealing algorithm (SA) and variable neighborhood search algorithm (VNS) have been developed to provide near-optimal solutions. The developed heuristics are tested for their efficiency on a very large data sets generated as per the prescribed procedure found in the literature. Based on the results of experiments, it is inferred that the VNS-based heuristics outperforms the SA-based heuristics consistently both in terms of solution quality and consistency.

关键词： identical parallel machine scheduling Variable neighborhood search algorithm Simulated annealing algorithm Make span Number of tardy jobs

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：