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

MILP models and effective heuristic for energy-aware parallel machine scheduling with shared manufacturing

EXPERT SYSTEMS WITH APPLICATIONS 2025年 271卷

作者： Cheng, Junheng Cheng, Jingya Lin, Yanhong Lu, Shu Wu, Peng Fujian Normal Univ Sch Econ Fuzhou 350117 Peoples R China Fuzhou Univ Sch Econ & Management Fuzhou 350116 Peoples R China

Driven by advancements in information technology and the modernization of the manufacturing industry, shared manufacturing has emerged as a novel industrial organization mode that enables manufacturing enterprises to mutually utilize external idle resources. Concurrently, to meet the requirements of sustainable development, manufacturing enterprises need to balance economic efficiency with energy consumption in their production practices. This study investigates a new energy-aware parallel machine scheduling problem shared manufacturing environments, where production time, cost, and energy consumption vary across different jobs and machines. The objective is to minimize the weighted sum of makespan, total energy consumption, and overall sharing costs. We first formulate the problem as a mixed-integer linear programming (MILP) model. Then the problem is further refined into an improved MILP model with fewer integer variables. Given the strong NP-hard nature of the problem, an effective tailored heuristic (ETH) is developed based on analyzed problem properties to solve large-scale instances. It includes three main phases: pre-processing, job assignment, and local search. Extensive experimental results demonstrate that the improved MILP model significantly outperforms the original one, and the ETH can solve large-sized instances with up to 400 machines and 20000 jobs within one second, with gaps of less than 1%. The proposed MILP models and ETH can assist manufacturing enterprises in making more informed decisions and scheduling resource allocation while considering economic and environmental factors.

关键词： parallel machine scheduling Shared manufacturing Energy consumption Mixed-integer linear programming Heuristic

来源：评论

学校读者我要写书评

暂无评论

The integration of shared renewable resources considering setup times for the parallel machine scheduling problem

引用

COMPUTERS & INDUSTRIAL ENGINEERING 2025年 200卷

作者： Shafiee, Mohammad Amiri-Aref, Mehdi Klibi, Walid Yazd Univ Dept Ind Engn Yazd Iran Noavar Ertebat Sanat Co NESCO R&D Dept Qazvin Iran KEDGE Business Sch Ctr Excellence Supply Chain & Transportat CESIT Talence France 40 Ave Terroirs F-75012 Paris France 680 Cr Liberat F-33405 Talence France

With the advent of Industry 5.0, the rise of advanced technologies, and the fast deployment of human- machine collaborative systems, there is a need for novel approaches to optimizing resources and increasing overall production efficiency. In this regard, we investigate a parallel machine scheduling problem (PMS) where various renewable resources switch among unrelated parallel machines during the operational plan. Each machine can be equipped with a specified number of resources, one at a time, on its left and right sides. We propose a mathematical model for the renewable-resource-constrained parallel machine scheduling problem that minimizes total setup times. We further incorporate realistic features such as non-simultaneous start times of machines, machine eligibility, and due date constraints for jobs. We propose a hybrid meta- heuristic algorithm to solve large instances by employing a novel constructive heuristic and the simulated annealing algorithm. Several instances are tested to validate the solution approach and underline its efficiency for large-sized ones. Through the case of a wiring harness manufacturer, we provide managerial insights on the benefit of either increasing the number of sharing renewable resources or increasing the number of machines in PMS problems, which can reduce total setup times by up to 19%.

关键词： parallel machine scheduling Renewable resources Sequence-dependent setup times Changeover minimization Wiring harness manufacturing

来源：评论

学校读者我要写书评

暂无评论

Comparative Analysis of Simulated Annealing and Tabu Search for parallel machine scheduling

引用

Procedia Computer Science 2025年 256卷 573-582页

作者： Alzira Mota Paulo Ávila João Bastos Luís A.C. Roque António Pires ISRC ISEP - School of Engineering Polytechnic of Porto 4249-015 Porto Portugal INESC-TEC ISEP - School of Engineering Polytechnic of Porto 4200-072 Porto Portugal SYSTEC-ISR ARISE ISEP - School of Engineering Polytechnic of Porto 4249-015 Porto Portugal ISEP - School of Engineering Polytechnic of Porto 4249-015 Porto Portugal

This paper compares the performance of Simulated Annealing and Tabu Search meta-heuristics in addressing a parallel machine scheduling problem aimed at minimizing weighted earliness, tardiness, total flowtime, and machine deterioration costs—a multi-objective optimization problem. The problem is transformed into a single-objective problem using weighting and weighting relative distance methods. Four scenarios, varying in the number of jobs and machines, are created to evaluate these metaheuristics. Computational experiments indicate that Simulated Annealing consistently yields superior solutions compared to Tabu Search in scenarios with lower dimensions despite longer run times. Conversely, Tabu Search performs better in higher-dimensional scenarios. Furthermore, it is observed that solutions generated by different weighting methods exhibit similar performance.

关键词： parallel machine scheduling multi-objective optimization weighting methods Simulated annealing Tabu search

来源：评论

学校读者我要写书评

暂无评论

parallel machine scheduling with job family, release time, and mold availability constraints: model and two solution approaches

引用

MEMETIC COMPUTING 2024年第3期16卷 355-371页

作者： Lin, Xiang Chen, Yuning Xue, Junhua Zhang, Boquan Chen, Yingwu Chen, Cheng Natl Univ Def Technol Deya Rd Changsha 410073 Hunan Peoples R China

This paper investigates a new problem in an identical parallel machine environment called parallel machine scheduling with job family, release time, and mold availability constraints (PMS-JRM), which is highly challenging from the computational perspective as it extends the basic NP-hard problem Pm||& sum;Cj\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$P_m||\sum C_j$$\end{document}. The mold availability notion, first introduced in this paper, represents the availability relationship between jobs and machines. The PMS-JRM model originates from the imaging data collaborative processing in a low-earth-orbit satellite constellation under a time-varying communication network, and it can represent other multi-resource collaborative scheduling problems with discontinuous communication. An integer programming model was proposed to formulate the PMS-JRM. Due to its NP-hardness, two highly efficient heuristic solution approaches were proposed, namely a greedy algorithm with a hybrid first come first serve (HFCFS) dispatching rule (GA-HFCFS) and a Memetic Algorithm with Heterogeneous swap and Key job insertion operators (MA-HK). Extensive experiments were conducted on a set of test cases with various scales, and the results showed that GA-HFCFS outperforms three classical dispatching rules available in the literature. Taking the results of GA-HFCFS as initial solutions, MA-HK achieves optimal solutions for all small-scale cases while providing superior solutions within the same running time compared to two other competitors for large-scale cases. In particular, MA-HK yields better solutions in less running time than the state-of-the-art CPLEX solver. Additional experiments were conducted to highlight the critical ingredients of MA-HK.

关键词： Mold availability parallel machine scheduling Heuristic algorithm Dispatching rule Memetic search

来源：评论

学校读者我要写书评

暂无评论

parallel machine scheduling with time dependent processing times

引用

DISCRETE APPLIED MATHEMATICS 1996年第1期70卷 81-93页

作者： Chen, ZL Department of Civil Engineering and Operations Research Princeton University Princeton NJ 08544 USA

We consider a parallel machine scheduling problem in which the processing time of a job is a simple linear function of its starting time. The objective is to minimize total completion times. We show that the problem is NP-hard in the strong sense even with a fixed number of machines. When the number of machines is arbitrary, we show that there is no polynomial time heuristic with a constant worst-case bound unless P = NP. Under the two-machine case, we derive a data dependent worst-case bound for a simple polynomial time heuristic whose performance can be arbitrarily bad. However, for the case of a fixed number of machines, the question whether there exists a polynomial time heuristic with a constant worst-case bound remains open.

关键词： parallel machine scheduling time dependent processing times strong NP-hardness heuristic worst-case bound

来源：评论

学校读者我要写书评

暂无评论

parallel machine scheduling with a convex resource consumption function

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2006年第1期173卷 92-107页

作者： Shabtay, Dvir Kaspi, Moshe Ben Gurion Univ Negev Dept Ind Engn & Management IL-84105 Beer Sheva Israel

We consider some problems of scheduling jobs on identical parallel machines where job-processing times are controllable through the allocation of a nonrenewable common limited resource. The objective is to assign the jobs to the machines, to sequence the jobs on each machine and to allocate the resource so that the makespan or the sum of completion times is minimized. The optimization is done for both preemptive and nonpreemptive jobs. For the makespan problem with nonpreemptive jobs we apply the equivalent load method in order to allocate the resources, and thereby reduce the problem to a combinatorial one. The reduced problem is shown to be NP-hard. If preemptive jobs are allowed, the makespan problem is shown to be solvable in O(n(2)) time. Some special cases of this problem with precedence constraints are presented and the problem of minimizing the sum of completion times is shown to be solvable in O(n log n) time. (c) 2005 Elsevier B.V. All rights reserved.

关键词： scheduling parallel machine scheduling resource allocation equivalent load method computational complexity

来源：评论

学校读者我要写书评

暂无评论

parallel machine scheduling under a grade of service provision

引用

COMPUTERS & OPERATIONS RESEARCH 2004年第12期31卷 2055-2061页

作者： Hwang, HC Chang, SY Lee, K Pohang Univ Sci & Technol Div Elect & Comp Engn Dept Ind Engn Pohang 790784 Kyungbook South Korea Chosun Univ Dept Ind Engn Kwangju 501709 South Korea

We consider the problem of scheduling parallel machines that process service requests from various customers who are entitled to many different grade of service (GoS) levels. We propose and analyze one simple way to ensure such differentiated service. In particular, we investigate how the longest processing time first algorithm (LPT) would perform in the worst case and show that a slight modification of LPT could significantly improve its worst-case performance. (C) 2003 Elsevier Ltd. All rights reserved.

关键词： parallel machine scheduling longest processing time first eligibility grade of service

来源：评论

学校读者我要写书评

暂无评论

parallel machine scheduling with earliness-tardiness penalties and space limits

引用

INTERNATIONAL JOURNAL OF ADVANCED MANUFACTURING TECHNOLOGY 2008年第7-8期37卷 793-802页

作者： Jeong, Suk Jae Kim, Kyung Sup Yonsei Univ Dept Ind & Informat Engn Seoul 120749 South Korea

In order to maximize an availability of machine and utilization of space, the parallel machines scheduling problem with space limit is frequently discussed in the industrial field. In this paper, we consider the parallel machine scheduling problem in which n jobs having different release times, due dates, and space limits are to be scheduled on m parallel machines. The objective function is to minimize the weighted sum of earliness and tardiness. To solve this problem, a heuristic is developed which is divided into three modules hierarchically: job selection, machine selection and job sequencing, and solution improvement. To illustrate its effectiveness, a proposed heuristic is compared with genetic algorithm (GA), hybrid genetic algorithm (HGA), and tabu search (TS), which are well-known meta-heuristics in a large number of randomly generated test problems based on the field situation. Also, we determine the job selection rule that is suitable to the problem situation considered in this paper and show the effectiveness of our heuristic method.

关键词： parallel machine scheduling earliness-tardiness penalties heuristic algorithm

来源：评论

学校读者我要写书评

暂无评论

parallel machine scheduling to minimize total tardiness

引用

INTERNATIONAL JOURNAL OF PRODUCTION ECONOMICS 2002年第3期76卷 265-279页

作者： Yalaoui, F Chu, CB Univ Technol Troyes Ind Syst Optimizat Lab F-10010 Troyes France

This paper addresses, using an exact method, the identical parallel machine scheduling problem to minimize total tardiness. In this problem, a set of jobs has to be scheduled, without preemption, on identical parallel machines. Each machine is able to treat only one job at a time. In order to prune the search tree, dominance properties are proved and lower and upper bounding schemes are proposed. A branch and bound (BAB) algorithm is developed taking into account these theoretical properties, lower and upper bounds. This BAB algorithm has been tested on a large set of randomly generated medium-sized problems. Computational results demonstrate the effectiveness of our approach over existing methods in the literature. (C) 2002 Elsevier Science B.V. All rights reserved.

关键词： parallel machine scheduling total tardiness dominance properties lower bound branch and bound

来源：评论

学校读者我要写书评

暂无评论

parallel machine scheduling with multiple unloading servers

引用

JOURNAL OF scheduling 2010年第3期13卷 213-226页

作者： Ou, Jinwen Qi, Xiangtong Lee, Chung-Yee Hong Kong Univ Sci & Technol Dept Ind Engn & Logist Management Kowloon Hong Kong Peoples R China Jinan Univ Dept Adm Management Guangzhou Guangdong Peoples R China

We study a parallel machine scheduling problem with multiple unloading servers. After a machine completes processing one job, an unloading server is needed to remove the job from the machine. Only after unloading, the machine is available for processing the next job. The model is motivated by the milk run operations of a logistics company that faces limited unloading docks at the warehouse. Our interest is to minimize the total completion time of the jobs. We show that the shortest-processing-time-first (SPT) algorithm has a worst-case bound of 2. We also develop other improved heuristic algorithms as well as a branch-and-bound algorithm to solve the problem. Computational experiments show that our algorithms are efficient and effective.

关键词： parallel machine scheduling Unloading servers Logistics Milk run

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：