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

Best semi-online algorithms for unbounded parallel batch scheduling

DISCRETE APPLIED MATHEMATICS 2011年第8期159卷 838-847页

作者： Yuan, Jinjiang Ng, C. T. Cheng, T. C. E. Hong Kong Polytech Univ Dept Logist & Maritime Studies Kowloon Hong Kong Peoples R China Zhengzhou Univ Dept Math Zhengzhou 450001 Henan Peoples R China

We consider semi-online scheduling of an unbounded parallel batch machine to minimize the makespan where, at the present time instant t, information on the first longest job arriving after t is known. In this paper online means that jobs arrive over time, J*(t) denotes the first longest job arriving after t, and p*(t) and r*(t) denote the processing time and arrival time of J*(t), respectively. Given information p*(t), we present an online algorithm with a competitive ratio (5 - root 5)/2 approximate to 1.382, and show that the algorithm is the best possible;furthermore, this algorithm generates at most two batches. This algorithm is also the best possible given information J*(t). Given information r*(t), we present an online algorithm with a competitive ratio 3/2, and show that any online algorithm cannot have a competitive ratio less than 3 root 3 approximate to 1.442;furthermore, this algorithm generates at most three batches. Given information r*(t) with the restriction that an online algorithm generates at most two batches, we present an online algorithm with a competitive ratio (root f + 1)/2 approximate to 1.618, and show that the algorithm is the best possible. (C) 2011 Elsevier B.V. All rights reserved.

关键词： parallel batch scheduling Online algorithm Information in advance Competitive ratio

来源：评论

学校读者我要写书评

暂无评论

A branch-and-price algorithm for robust parallel batch scheduling problem with uncertain size

引用

INDUSTRIAL MANAGEMENT & DATA SYSTEMS 2022年第10期122卷 2351-2370页

作者： Wang, Ting Shao, Xiaoling Yan, Xue Nanjing Univ Finance & Econ Sch Management Sci & Engn Nanjing Peoples R China Nanjing Audit Univ Sch Govt Audit Nanjing Peoples R China Nanjing Audit Univ Sch Finance Nanjing Peoples R China

Purpose In intelligent scheduling, parallel batch processing can reasonably allocate production resources and reduce the production cost per unit product. Hence, the research on a parallel batch scheduling problem (PBSP) with uncertain job size is of great significance to realize the flexibility of product production and mass customization of personalized products. Design/methodology/approach The authors propose a robust formulation in which the job size is defined by budget constrained support. For obtaining the robust solution of the robust PBSP, the authors propose an exact algorithm based on branch-and-price framework, where the pricing subproblem can be reduced to a robust shortest path problem with resource constraints. The robust subproblem is transformed into a deterministic mixed integer programming by duality. A series of deterministic shortest path problems with resource constraints is derived from the programming for which the authors design an efficient label-setting algorithm with a strong dominance rule. Findings The authors test the performance of the proposed algorithm on the extension of benchmark instances in literature and compare the infeasible rate of robust and deterministic solutions in simulated scenarios. The authors' results show the efficiency of the authors' algorithm and importance of incorporating uncertainties in the problem. Originality/value This work is the first to study the PBSP with uncertain size. To solve this problem, the authors design an efficient exact algorithm based on Dantzig-Wolfe decomposition. This can not only enrich the intelligent manufacturing theory related to parallel batch scheduling but also provide ideas for relevant enterprises to solve problems.

关键词： Intelligent scheduling Robust optimization parallel batch scheduling Uncertain size

来源：评论

学校读者我要写书评

暂无评论

Unbounded parallel batch scheduling with job delivery to minimize makespan

引用

OPERATIONS RESEARCH LETTERS 2008年第4期36卷 477-480页

作者： Lu, Lingfa Yuan, Jinjiang Zhengzhou Univ Dept Math Zhengzhou 450052 Henan Peoples R China

We consider unbounded parallel batch scheduling with job delivery to minimize makespan. When the jobs have identical size, we provide a polynomial-time algorithm. When the jobs have non-identical sizes, we provide a h... 详细信息

关键词： parallel batch scheduling job delivery heuristic worst-case performance ratio

来源：评论

学校读者我要写书评

暂无评论

Bid construction scheme based on local search to solve serial-parallel cooperative batch scheduling problems

引用

ENGINEERING OPTIMIZATION 2023年第4期55卷 615-631页

作者： Zeng, Chengkuan Liu, Zixuan Tang, Jiafu Fan, Zhi-Ping Yan, Chongjun Long, Siyuan Northeastern Univ Sch Business Adm Dept Informat Management & Decis Sci Shenyang Peoples R China Dongbei Univ Finance & Econ DUFE Coll Management Sci Engn Dalian Peoples R China Gosuncn Intelligent IOT Technol Co Ltd Tianjin Peoples R China

This study addresses cooperative batch scheduling problems based on both serial batch (s-batch) scheduling and parallel batch (p-batch) scheduling. A mixed-integer linear programming model was formulated to describe such problems and a bid construction scheme (BCS) was developed to solve them. In s-batch and p-batch scheduling, the sheet strips function as both bidders and auctioned resources, with different sheet strips forming different batches over multiple rounds of auctioning. Then, a local search operator is applied to optimize the feasible solutions. Numerical experiments were conducted on a series of randomly generated and real-world instances. The results obtained by the proposed BCS were compared with those obtained by four combinations of existing algorithms and analysed by SPSS. The proposed scheme was able to identify feasible solutions quickly and efficiently, proving its the effectiveness, stability, practicality, and suitability for addressing cooperative batch scheduling problems, especially those corresponding to large-scale instances.

关键词： Serial batch scheduling parallel batch scheduling cooperative batch scheduling bid construct scheme

来源：评论

学校读者我要写书评

暂无评论

batch scheduling Problem and Algorithm on parallel Machines with Time Bound 7

Batch Scheduling Problem and Algorithm on Parallel Machines ...

引用

7th International Conference on Intelligent Human-Machine Systems and Cybernetics (IHMSC)

作者： Li, Haixia Gao, Xiaoli Sun, Chuanguang Shandong Water Polytech Rizhao Peoples R China

We consider the problem of batch scheduling jobs on m parallel machines with time bound to minimize total weighted completion times. Each batching machine can processing to b jobs simultaneously as a batch. A polynomi... 详细信息

ISBN: (纸本)9781479986460

关键词： parallel batch scheduling time bound optimal algorithm

来源：评论

学校读者我要写书评

暂无评论

Makespan minimisation on parallel batch processing machines with non-identical job sizes and release dates

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2012年第20期50卷 6022-6035页

作者： Ozturk, Onur Espinouse, Marie-Laure Di Mascolo, Maria Gouin, Alexia UJF Grenoble 1 Grenoble INP CNRS G SCOPUMR5272 F-38031 Grenoble France UJF Grenoble 1 Grenoble INP CNRS GIPSA LabUMR 5216 F-38402 St Martin Dheres France

The problem we study in this paper arises from the washing step of hospital sterilisation services. Washers in the washing step are capable of handling more than one medical device set as long as their capacity is not exceeded. The medical device set sizes and arrival times to the sterilisation service may be different, but they all have the same washing duration. Thus, we model the washing step as a batch scheduling problem where medical device sets are treated as jobs with non-identical sizes and release dates, but equal processing times. The main findings we present in this paper are the following. First, we study two special cases for which polynomial algorithms are presented. We then develop a 2-approximation algorithm for the general problem. Finally, we develop a MILP model and compare it with another MILP model from the literature. Computational results show that our MILP model outperforms the model from the literature.

关键词： batch scheduling batch processing heuristics makespan mixed integer linear programming parallel batch scheduling approximation algorithm sterilisation service

来源：评论

学校读者我要写书评

暂无评论

A novel carbon reduction engineering method-based deep Q-learning algorithm for energy-efficient scheduling on a single batch-processing machine in semiconductor manufacturing

引用

INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH 2024年第18期62卷 6449-6472页

作者： Kong, Min Wang, Weizhong Deveci, Muhammet Zhang, Yajing Wu, Xuzhong Coffman, D'Maris Anhui Normal Univ Sch Econ & Management Wuhu Peoples R China Hefei Univ Technol Sch Management Hefei Peoples R China UCL Bartlett Sch Sustainable Construct London England Natl Def Univ Turkish Naval Acad Dept Ind Engn Istanbul Turkiye Natl Def Univ Turkish Naval Acad Dept Ind Engn TR-34940 Istanbul Turkiye Anhui Normal Univ Sch Econ & Management Wuhu 241000 Peoples R China Lebanese Amer Univ Dept Elect & Comp Engn Byblos Lebanon

The semiconductor industry is a resource-intensive sector that heavily relies on energy, water, chemicals, and raw materials. Within the semiconductor manufacturing process, the diffusion furnace, ion implantation machine, and plasma etching machine exhibit high energy demands or operate at extremely high temperatures, resulting in significant electricity consumption, which is usually carbon-intensive. To address energy conservation concerns, the industry adopts batch production technology, which allows for the simultaneous processing of multiple products. The energy-efficient parallel batch scheduling problem arises from the need to optimise product grouping and sequencing. In contrast to existing heuristics, meta-heuristics, and exact algorithms, this paper introduces the Deep Q-Network (DQN) algorithm as a novel approach to address the proposed problem. The DQN algorithm is built upon the agent's systematic learning of scheduling rules, thereby enabling it to offer guidance for online decision-making regarding the grouping and sequencing of products. The efficacy of the algorithm is substantiated through extensive computational experiments.

关键词： Semiconductor manufacturing deep reinforcement learning parallel batch scheduling less is more carbon reduction engineering

来源：评论

学校读者我要写书评

暂无评论

A branch and bound based heuristic for makespan minimization of washing operations in hospital sterilization services

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2014年第1期239卷 214-226页

作者： Ozturk, Onur Begen, Mehmet A. Zaric, Gregory S. Univ Western Ontario Ivey Business Sch London N6G 0N1 ON Canada

In this paper, we address the problem of parallel batching of jobs on identical machines to minimize makespan. The problem is motivated from the washing step of hospital sterilization services where jobs have different sizes, different release dates and equal processing times. Machines can process more than one job at the same time as long as the total size of jobs in a batch does not exceed the machine capacity. We present a branch and bound based heuristic method and compare it to a linear model and two other heuristics from the literature. Computational experiments show that our method can find high quality solutions within short computation time. (C) 2014 Elsevier B.V. All rights reserved.

关键词： OR in health services parallel batch scheduling Makespan Branch and bound heuristic

来源：评论

学校读者我要写书评

暂无评论

parallel batching with multi-size jobs and incompatible job families

引用

TOP 2023年第2期31卷 440-458页

作者： Druetto, Alessandro Pastore, Erica Rener, Elena Univ Torino Dipartimento Informat Via Pessinetto 12 I-10149 Turin Italy Politecn Torino Dept Management & Prod Engn Cso Duca Abruzzi 24 I-10129 Turin Italy

parallel batch scheduling has many applications in the industrial sector, like in material and chemical treatments, mold manufacturing and so on. The number of jobs that can be processed on a machine mostly depends on the shape and size of the jobs and of the machine. This work investigates the problem of batching jobs with multiple sizes and multiple incompatible families. A flow formulation of the problem is exploited to solve it through two column generation-based heuristics. First, the column generation finds the optimal solution of the continuous relaxation, then two heuristics are proposed to move from the continuous to the integer solution of the problem: one is based on the price-and-branch heuristic, the other on a variable rounding procedure. Experiments with several combinations of parameters are provided to show the impact of the number of sizes and families on computation times and quality of solutions.

关键词： parallel batch scheduling Column generation Incompatible job families Multi-size jobs

来源：评论

学校读者我要写书评

暂无评论

Column generation and rounding heuristics for minimizing the total weighted completion time on a single batching machine

引用

COMPUTERS & OPERATIONS RESEARCH 2022年 139卷 1页

作者： Druetto, Alessandro Grosso, Andrea Univ Torino Dipartimento Informat Via Pessinetto 12 I-10149 Turin Italy

This paper deals with the single-machine, parallel batching, total weighted completion time scheduling problem. A new graph-based formulation of the problem is proposed, where such graph has an exponential number of nodes and arcs. The problem is modeled as an integer linear program on this graph, combining features of a minimum cost flow problem and features of a set-partition problem as well. The continuous relaxation of this integer problem is solved via column generation, providing a very tight lower bound. Two different flavors of column generation are tested, leading to two models with identical performances in terms of bound tightness but in practice very different in terms of running time. A simple and effective rounding strategy applied to the faster model allows to generate heuristic solutions with values within a few percentage points from the optimum. Two different variants of the heuristic rounding procedure are tested;one allows to certify the optimality gap, while the other trades the ability to certify the gap with a greater computational speed.

关键词： parallel batch scheduling Column generation Weighted completion time

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：