Research on Optimization of Dual-Resource Batch Scheduling in Flexible Job Shop

With the rapid development of intelligent manufacturing and the changes in market demand,the current manufacturing industry presents the characteristics of multi-varieties,small batches,customization,and a short production cycle,with the whole production process having certain flexibility.In this paper,a mathematical model is established with the minimum production cycle as the optimization objective for the dual-resource batch scheduling of the flexible job shop,and an improved nested optimization algorithm is designed to solve the problem.The outer layer batch optimization problem is solved by the improved simulated annealing algorithm.The inner double resource scheduling problem is solved by the improved adaptive genetic algorithm,the double coding scheme,and the decoding scheme of Automated Guided Vehicle(AGV)scheduling based on the scheduling rules.The time consumption of collision-free paths is solved with the path planning algorithm which uses the Dijkstra algorithm based on a time window.Finally,the effectiveness of the algorithm is verified by actual cases,and the influence of AGV with different configurations on workshop production efficiency is analyzed.

Performance Prediction Based Workload Scheduling in Co-Located Cluster

Cloud service providers generally co-locate online services and batch jobs onto the same computer cluster,where the resources can be pooled in order to maximize data center resource utilization.Due to resource competition between batch jobs and online services,co-location frequently impairs the performance of online services.This study presents a quality of service(QoS)prediction-based schedulingmodel(QPSM)for co-locatedworkloads.The performance prediction of QPSM consists of two parts:the prediction of an online service’s QoS anomaly based on XGBoost and the prediction of the completion time of an offline batch job based on randomforest.On-line service QoS anomaly prediction is used to evaluate the influence of batch jobmix on on-line service performance,and batch job completion time prediction is utilized to reduce the total waiting time of batch jobs.When the same number of batch jobs are scheduled in experiments using typical test sets such as CloudSuite,the scheduling time required by QPSM is reduced by about 6 h on average compared with the first-come,first-served strategy and by about 11 h compared with the random scheduling strategy.Compared with the non-co-located situation,QPSM can improve CPU resource utilization by 12.15% and memory resource utilization by 5.7% on average.Experiments show that the QPSM scheduling strategy proposed in this study can effectively guarantee the quality of online services and further improve cluster resource utilization.

Research on Flexible Job Shop Scheduling Based on Improved Two-Layer Optimization Algorithm

To improve the productivity,the resource utilization and reduce the production cost of flexible job shops,this paper designs an improved two-layer optimization algorithm for the dual-resource scheduling optimization problem of flexible job shop considering workpiece batching.Firstly,a mathematical model is established to minimize the maximum completion time.Secondly,an improved two-layer optimization algorithm is designed:the outer layer algorithm uses an improved PSO(Particle Swarm Optimization)to solve the workpiece batching problem,and the inner layer algorithm uses an improved GA(Genetic Algorithm)to solve the dual-resource scheduling problem.Then,a rescheduling method is designed to solve the task disturbance problem,represented by machine failures,occurring in the workshop production process.Finally,the superiority and effectiveness of the improved two-layer optimization algorithm are verified by two typical cases.The case results show that the improved two-layer optimization algorithm increases the average productivity by 7.44% compared to the ordinary two-layer optimization algorithm.By setting the different numbers of AGVs(Automated Guided Vehicles)and analyzing the impact on the production cycle of the whole order,this paper uses two indicators,the maximum completion time decreasing rate and the average AGV load time,to obtain the optimal number of AGVs,which saves the cost of production while ensuring the production efficiency.This research combines the solved problem with the real production process,which improves the productivity and reduces the production cost of the flexible job shop,and provides new ideas for the subsequent research.

Modeling and Optimization for Scheduling of Chemical Batch Processes

化学的批过程在化学生产变得重要。在这些过程，大量化学产品被生产在日常生命满足人的要求。最近，经济全球化导致了在传统的化学过程工业种世界范围的比赛。以便在全球市场保持竞争，每个公司必须优化它的生产管理并且为市场变化建立一个反应系统。安排是在化学过程的生产管理的核心。这篇论文的目标是在这个挑战性的区域考察最近的开发。安排问题和优化方法的批的分类被介绍。六个典型模型的比较从文学在一个一般基准例子被显示出。最后，在未来研究的挑战和应用被讨论。

A Genetic Algorithm-based Approach to Scheduling of Batch Production with Maximum Profit

The optimal scheduling of multi-product batch process is studied and a new mathematics model targeting the maximum profit is proposed, which can be solved by the modified genetic algorithm (MGA) with mixed coding (sequence coding and decimal coding) developed by us. In which, the partially matched cross over (PMX) and reverse mutation are used for the sequence coding, whereas the arithmetic crossover and heteropic mutation are used for the decimal coding. In axidition, the relationship between production scale and production cost is analyzed and the maximum profit is always a trade-off of the production scale and production cost. Two examples are solved to demonstrate the effectiveness of the method.

An improved multi-objective optimization algorithm for solving flexible job shop scheduling problem with variable batches

In order to solve the flexible job shop scheduling problem with variable batches,we propose an improved multiobjective optimization algorithm,which combines the idea of inverse scheduling.First,a flexible job shop problem with the variable batches scheduling model is formulated.Second,we propose a batch optimization algorithm with inverse scheduling in which the batch size is adjusted by the dynamic feedback batch adjusting method.Moreover,in order to increase the diversity of the population,two methods are developed.One is the threshold to control the neighborhood updating,and the other is the dynamic clustering algorithm to update the population.Finally,a group of experiments are carried out.The results show that the improved multi-objective optimization algorithm can ensure the diversity of Pareto solutions effectively,and has effective performance in solving the flexible job shop scheduling problem with variable batches.

Synthesis and Scheduling of Optimal Batch Water-recycle Networks

这个工作为设计开发基于优化的方法论并且批水安排再循环网络。这项任务要求网络配置的鉴定，淡水用法，从来源再循环任务到水池，废水分泌物，和安排 scheme.A 新 source-tank-sink 表示被开发允许存储和派遣坦克。这个问题被首先消除安排限制并且决定淡水和废水分泌物的最小的用法在阶段解决。一个反复的过程被提出由做贸易离开资本对操作费用最小化系统的全部的年度费用。工作在包括的工作限制了的以前的文学克服限制在一样的周期，不能导致可行答案的 lumped 平衡，和不现实的客观 functions.A 案例研究以内再循环被解决说明设计过程的实用性。

The Single Machine Parallel Batch Scheduling Problem with Job Compatibility Constraints

当图 G 是有限的是一个将军时，有在工作相容性限制被一个图 G.This 问题代表的地方，相容性被考虑最小化 makespan 的工作的单个机器平行批问题被证明是 NP-hard.And 由两部组成，一完全由两部组成并且一张完全的m深裂的图，这些问题分别地在多项式时间被解决。

Bicriteria Scheduling on a Series-Batching Machine to Minimize Makespan and Total Weighted Completion Time with Equal Length Job

It is known that the problem of minimizing total weighted completion time on a series-batching machine is NP-hard. We consider a series-batching bicriteria scheduling problem of minimizing makespan and total weighted completion time with equal length job simultaneously. A batching machine can handle up to b jobs in a batch, where b is called the batch capacity of the machine. We study the unbounded model with b ≥ n, where n denotes the number of jobs. A dynamic programming algorithm is proposed to solve the unbounded model, which can find all Pareto optimal schedules in O(n3) time.

A two-stage flexible flow-shop scheduling problem with m identical parallel machines on one stage and a batch processor on the other stage

This paper considers a hybrid two-stage flow-shop scheduling problem with m identical parallel machines on one stage and a batch processor on the other stage. The processing time of job Jj on any of m identical parallel machines is aj≡ a (j∈N), and the processing time of job Jj is bj(j∈N) on a batch processor M. We take makespan (Cmax) as our minimization objective. In this paper, for the problem of FSMP-BI (m identical parallel machines on the first stage and a batch processor on the second stage), based on the algorithm given by Sung and Choung for the problem of 1| rj, BI | Cmax under the constraint of the given processing sequence, we develop an optimal dynamic programming Algorithm H1 for it in max{O(nlogn), O(nB)} time. A max{O(nlogn), O(nB)} time symmetric Algorithm H2 is given then for the problem of BI-FSMP (a batch processor on the first stage and m identical parallel machines on the second stage).

Hierarchical On-line Scheduling of Multiproduct Batch Plants with a Combined Approach of Mathematical Programming and Genetic Algorithm

In this contribution we present an online scheduling algorithm for a real world multiproduct batch plant. The overall mixed integer nonlinear programming (MINLP) problem is hierarchically structured into a mixed integer linear programming (MILP) problem first and then a reduced dimensional MINLP problem, which are optimized by mathematical programming (MP) and genetic algorithm (GA) respectively. The basis idea relies on combining MP with GA to exploit their complementary capacity. The key features of the hierarchical model are explained and illustrated with some real world cases from the multiproduct batch plants.

Genetic Algorithm for Scheduling Problem of Chemical Batch Process with Due Date Constraints

The intense competition in the current marketplace ha s forced firms to reexamine their methods of doing business, using superior manu facturing practices in the form of just-in-time (JIT), production with JIT pra ctices pursue completion on time and zero inventory, which is often instruct ed according to the custom’s demand or the sale contract. Earliness and tardine ss are undesirable because both of them will bring the extra cost, cost will als o be increased by some factors such as operation condition, intermediate storage , clean method, etc, to minimize the total cost is often the main scheduling objective, but sometime it is most important for factories to eliminate the tar diness cost in order to maintain the commercial credit and to avoid penalty, the refore, minimum of tardiness cost becomes the first objective. It is more import ant to select a reasonable objective by the actual condition during scheduli ng. In this paper scheduling problem of chemical batch process with due date is studied, two different intermediate storage policies and two different productio n modes are also discussed, production scheduling with different intermediate st orage policy and different production mode is proposed and the result is compare d. In order to complete all products within the due date, not only earliness and tardiness but also holding problem is considered, the objective is to selec t a proper intermediate storage policy and production mode and to minimize the c ost resulted by the earliness and tardiness, even the cost result by the interme diate storage. Scheduling with multiple stage and multiple machine is known as a NP-hard problem, mathematical program (MP) method, such as branch-and-bound (BAB), mixed integer linear program (MILP), etc, is often used to solve the sche duling problem. But as is well known, MP method is not good for combination opti mization, especially for large scale and complex optimal problem, whereas geneti c algorithm (GA) can overcome the MP method’s shortcoming and is fit for solvin g such scheduling problem. In this paper a modified genetic algorithm with speci al crossover operator and mutation operator is presented to solve this schedulin g problem. The results show such problem can be solved effectively with the pres ented method.

A Note on DP Algorithm for Batching Scheduling to Minimize Maximum Lateness

In parallel-batching machine scheduling, all jobs in a batch start and complete at the same time, and the processing time of the batch is the maximum processing time of any job in it. For the unbounded parallel-batching machine scheduling problem of minimizing the maximum lateness, denoted 1|p-batch|L_(max), a dynamic programming algorithm with time complexity O(n^2) is well known in the literature.Later, this algorithm is improved to be an O(n log n) algorithm. In this note, we present another O(n log n) algorithm with simplifications on data structure and implementation details.

Batch Scheduling with Job Processing Time Compatibility and Rejection on a Single

We address a scheduling problem with job processing time compatibility and rejection on a parallel-batching machine.The processing time of each job is defined by an interval and any number of jobs can be assigned into a batch provided that the processing time intervals of the jobs in the common batch are not disjoint.Three problems are considered:(1)minimize the sum of the makespan of accepted jobs and the total rejection penalty of rejected jobs;(2)minimize the makespan of accepted jobs subject to an upper bound on the total rejection penalty of rejected jobs;(3)minimize the total rejection penalty of rejected jobs subject to an upper bound on the makespan of accepted jobs.We provide an O(n2)time algorithm for the first problem.Moreover,for the other two problems,we first show that they are NP-hard,and then present pseudo-polynomial time dynamic programming algorithms and fully polynomial time approximation schemes for them,respectively.

Optimal Batching Structures of Single Machine Scheduling

批是必须在连续或平行的形式联合被处理的工作的一个子集。为单个机器， batching，全部的结束时间安排问题，算法的方面广泛地在文学被学习了。这份报纸在 batching 方法上论述这些问题的最佳的 batching 结构：所有工作在确切 N (任意的改正批数字并且 1 < N < n ) 批。

On-line Scheduling Algorithm for Penicillin Fed-batch Fermentation

An on-line scheduling algorithm to maximize gross profit of penicillin fed-batch fermentation is proposed. According to the on-line classification method, fed-batch fermentation batches are classified into three categories. Using the scheduling strategy, the optimal termination sequence of batches is obtained. Pseudo on-line simulations for testing the proposed algorithm with the data from industrial scale penicillin fermentation are carried out.

A Cooperated Imperialist Competitive Algorithm for Unrelated Parallel Batch Machine Scheduling Problem

This study focuses on the scheduling problem of unrelated parallel batch processing machines(BPM)with release times,a scenario derived from the moulding process in a foundry.In this process,a batch is initially formed,placed in a sandbox,and then the sandbox is positioned on a BPM formoulding.The complexity of the scheduling problem increases due to the consideration of BPM capacity and sandbox volume.To minimize the makespan,a new cooperated imperialist competitive algorithm(CICA)is introduced.In CICA,the number of empires is not a parameter,and four empires aremaintained throughout the search process.Two types of assimilations are achieved:The strongest and weakest empires cooperate in their assimilation,while the remaining two empires,having a close normalization total cost,combine in their assimilation.A new form of imperialist competition is proposed to prevent insufficient competition,and the unique features of the problem are effectively utilized.Computational experiments are conducted across several instances,and a significant amount of experimental results show that the newstrategies of CICAare effective,indicating promising advantages for the considered BPMscheduling problems.

视频点播系统中Batching调度方案的一种改进实现

节目调度是视频点播系统设计与实现的一个重要问题。本文首先对视频点播系统中的节目调度方案作了探讨 ,然后提出一种Batching调度方案的改进实现方法。理论与实验证明 。

A hybrid two-stage fexible flowshop scheduling problem with m identical parallel machines and a burn-in processor separately

A hybrid two-stage flowshop scheduling problem was considered which involves m identical parallel machines at Stage 1 and a burn-in processor M at Stage 2, and the makespan was taken as the minimization objective. This scheduling problem is NP-hard in general. We divide it into eight subcases. Except for the following two subcases： （1） b≥ an, max{m, B} 〈 n; （2） a1 ≤ b ≤ an, m ≤ B 〈 n, for all other subcases, their NP-hardness was proved or pointed out, corresponding approximation algorithms were conducted and their worst-case performances were estimated. In all these approximation algorithms, the Multifit and PTAS algorithms were respectively used, as the jobs were scheduled in m identical parallel machines.