Search

Scheduling is an important decision-making problem in production planning and the resulting decisions have a direct impact on reducing waste, including energy and idle capacity. Batch scheduling problems occur in various industries from automotive to food and energy. This paper introduces the parallel p-batch scheduling problem with batch delivery, content-dependent loading/unloading times and energy-aware objective function. The problem has been motivated by a real system used for freezing products in a food processing company. A mixed-integer linear programming model (MILP) has been developed and explained through a numerical example. As it is not practical to solve large-size instances via a mathematical model, the discrete differential evolution algorithm has been improved (iDDE) and hybridised with the genetic algorithm (GA). A release-oriented vector generation procedure and a heuristic batch formation mechanism have been developed to efficiently solve the problem. The performance of the proposed approach (iDDEGA) has been compared with CPLEX, iDDE and GA through a comprehensive computational study. A case study was conducted based on real data collected from the freezing process of the company, which also verified the practical use and advantages of the proposed methodology. [ABSTRACT FROM AUTHOR]

This work addresses a parallel batch machine scheduling problem subject to tardiness penalties, release dates, and incompatible job families. In this environment, jobs of the same family are partitioned into batches and each batch is assigned to a machine. The objective is to determine the sequence in which the batches will be processed on each machine with a view of minimizing the total weighted tardiness. To solve the problem, we propose a population-based iterated local search algorithm that makes use of multiple neighborhood structures and an efficient perturbation mechanism. The algorithm also incorporates the time window decomposition (TWD) heuristic to generate the initial population and employs population control strategies aiming to promote individuals with higher fitness by combining the total weighted tardiness with the contribution to the diversity of the population. Extensive computational experiments were conducted on 4860 benchmark instances and the results obtained compare very favorably with those found by the best existing algorithms. [ABSTRACT FROM AUTHOR]

The 1 | s-batch (∞) , r j | ∑ w j U j scheduling problem takes as input a batch setup time Δ and a set of n jobs, each having a processing time, a release date, a weight, and a due date; the task is to find a sequence of batches that minimizes the weighted number of tardy jobs. This problem was introduced by Hochbaum and Landy (Oper Res Lett 16(2):79–86, 1994); as a wide generalization of Knapsack, it is NP -hard. In this work, we provide a multivariate complexity analysis of the 1 | s-batch (∞) , r j | ∑ w j U j problem with respect to several natural parameters. That is, we establish a classification into fixed-parameter tractable and W [ 1 ] -hard problems, for parameter combinations of (i) # p = number of distinct processing times, (ii) # w = number of distinct weights, (iii) # d = number of distinct due dates, (iv) # r = number of distinct release dates. Thereby, we significantly extend the work of Hermelin et al. (Ann Oper Res 298:271–287, 2018) who analyzed the parameterized complexity of the non-batch variant of this problem without release dates. As one of our key results, we prove that 1 | s-batch (∞) , r j | ∑ w j U j is W [ 1 ] -hard parameterized by the number of distinct processing times and distinct due dates. To the best of our knowledge, these are the first parameterized intractability results for scheduling problems with few distinct processing times. Further, we show that 1 | s-batch (∞) , r j | ∑ w j U j is fixed-parameter tractable parameterized by # d + # p + # r , and parameterized by # d + # w if there is just a single release date. Both results hold even if the number of jobs per batch is limited by some integer b. [ABSTRACT FROM AUTHOR]

Copyright of Journal of South China University of Technology (Natural Science Edition) is the property of South China University of Technology and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Copyright of Journal of Anhui University of Technology (Natural Science) is the property of Anhui University of Technology and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Batch scheduling is a crucial part of pipeline enterprise operation management, especially in the context of market-oriented operation. It involves 3 main tasks: quickly preparing batch plans, accurately tracking interface movement, and operation condition in real time. Normally, the completion of multi-product pipeline batch scheduling depends on simulation models or optimization models and corresponding conventional solving algorithm. However, this approach becomes inefficient when applied to large-scale systems. The rapid development of machine learning has brought new ideas to batch scheduling research. This paper first reviews the current state of batch scheduling technology, and suggests that applying machine learning to it is a promising development direction. Then, we summarize the progress of machine learning applications in batch planning, interface movement tracking, and operational condition monitoring, and point out their limitations. Finally, considering the separation of refined oil production, transportation, and sales processes, 5 recommendations are put forward: oil supply and demand prediction and pipeline capacity prediction, batch planning, batch interface movement tracking, mixed oil development monitoring, and pipeline operation condition identification. [ABSTRACT FROM AUTHOR]

This paper studies a two-agent scheduling problem on mixed batch machines in parallel. A mixed batch machine can process several jobs simultaneously as a batch, as long as the number of jobs in the batch does not exceed the machine capacity. The processing time of a mixed batch is the weighted sum of the maximum processing time and the total processing time of jobs in the batch. The objective is to minimise the weighted sum of two agents' makespans. We present four approximation algorithms based on two strategies: the machine-centric strategy and the agent-centric strategy. For each strategy, a full batch longest processing time (FBLPT) rule and a longest processing time greedy (LPTG) rule are used. We conduct theoretical analyses based on the worst-case performance ratio to provide the provable guarantees on the performances of the algorithms, and simulation analyses based on randomly generated instances to evaluate the average performances of the algorithms. Furthermore, we verify the consistency between the theoretical and simulation results. The algorithms using agent-centric strategy perform better than ones using machine-centric strategy. Finally, we provide managerial insights for the problem by analysing the technological parameters of batches, importance of agents, and demand seasonality. [ABSTRACT FROM AUTHOR]

This study introduces a scheduling model for a two-machine flow shop batch system to minimize the actual flow time. In this system, two machines are responsible for processing raw materials and producing finished products, with a single bottleneck machine. The entity overseeing the manufacturing process organizes demand units into batches, ensures the accurate and timely arrival of raw materials, and delivers all finished products punctually to meet an expected due date. The study addresses crucial challenges, including determining the optimal number of batches, sizes, and sequences to achieve the specified objective. The analysis adopted an algorithm grounded in the Lagrange relaxation method to tackle these challenges. Moreover, the algorithm is operated by identifying the bottleneck machine as a scheduling reference and determining the appropriate number of batches and sizes. The analysis showed the efficacy of the developed algorithm by using Johnson's rule for making batch sequence decisions through numerical experiments conducted across 1000 cases. The results showed a 1.44% to 4.43% improvement in efficiency compared to previous research, accompanied by a 2 to 8 times reduction in computational time. [ABSTRACT FROM AUTHOR]

We propose a batch-scheduling model to minimize the total actual flow time (TAF) of parts to be processed in a flow shop consisting of m batch-processing machines. A batch-processing machine (BPM) is a machine that can process several parts at once, and the TAF of parts is the total interval time from the arrival times to the corresponding due date. In the real world, shop floors often have production lines with BPMs and multistage processes. We were motivated by a real problem in the aircraft industry and aimed to simultaneously satisfy the due dates and minimize the total time that parts spend in the shop. The problem was formulated as a mathematical model and solved using a proposed algorithm. The batch-scheduling problem is divided into batching and scheduling subproblems. The solution has been obtained by adopting backward scheduling. This paper develops a new model of flow shop scheduling problem for the shop with batch processing machines and the heuristic solution method. It provides numerical examples and their results to demonstrate the effectiveness of the proposed algorithm for solving the problem.

Copyright of Journal of Beijing University of Technology is the property of Journal of Beijing University of Technology, Editorial Department and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

Abstract This paper presents the development and mathematical implementation of a production scheduling model utilizing mixed-integer linear programming (MILP). A simplified model of a real-world multi-product batch plant constitutes the basis. The paper shows practical extensions to the model, resulting in a digital twin of the plant. Apart from sequential arrangement, the final model contains maintenance periods, campaign planning and storage constraints to a limited extend. To tackle weak computational performance and missing model features, a condensed mathematical formulation is introduced at first. After stating that these measures do not suffice for applicability in a restrained time period, a novel solution strategy is proposed. The overall non-iterative algorithm comprises a multi-step decomposition approach, which starts with a reduced scope and incrementally complements the schedule in multiple subproblem stages. Each of those optimizations holds less decision variables and makes use of warmstart information obtained from the predecessor model. That way, a first feasible solution accelerates the subsequent improvement process. Furthermore, the optimization focus can be shifted beneficially leveraging the Gurobi solver parameters. Findings suggest that correlation may exist between certain characteristics of the scheduling scope and ideal parameter settings, which yield potential for further investigation. Another promising area for future research addresses the concurrent multi-processing of independent MILPs on a single machine. First observations indicate that significant performance gains can be achieved in some cases, though sound dependencies were not discovered yet.

We consider online parallel-batch scheduling of f incompatible unit-length job families with variable lookahead interval to minimize the maximum completion time, where f is the number of job families which is known in advance. Incompatible job family means that a batch only contains the jobs from the same job family. At any time t , an online algorithm can foresee the information of the jobs arriving in the time interval (t , t + Δ (t) ] , where Δ (t) = (λ − 1) t + β is variable. When the batch capacity b = ∞ and f ≥ 1 , we provide a best possible online algorithm with competitive ratio 1 + α f for 0 ≤ β < 1 and 1 ≤ λ ≤ 1 + β , where α f is a positive root of λ f α f 2 + (λ f + β + 1 − f) α f + β − f = 0. When the batch capacity (f <) b < ∞ and f ≥ 2 , we give an online algorithm with competitive ratio 1 + max { f f α f + f , f λ f α f + β + 1 } for 0 ≤ β < 1 and λ ≥ 1 , and prove that it is the best possible for λ = 1 and 0 ≤ β ≤ f + 1 − f 2 + 1 2 . [ABSTRACT FROM AUTHOR]

This paper addresses a parallel machine scheduling problem with non-anticipatory family setup times and batching, considering the task's stochastic processing times and release dates. The problem arises from a real-life ship scheduling problem in the oil and gas industry. We developed an Iterated Greedy simheuristic with built-in Monte Carlo Simulation to sample the stochastic parameters. We conducted experiments on a set of instances from the literature, considering two simheuristic variants and three uncertainty levels for the stochastic parameters. To highlight the advantages of using simulation to tackle the stochastic problem, the simheuristics are compared against a regular Iterated Greedy metaheuristic, yielding an improvement of up to 16.5% on the objective function's expected values, with a reduced impact on computational times. During a risk analysis, the Pareto set of solutions is generated to illustrate the trade-off between the expected objective value of the solutions and the conditional value at risk, providing decision-makers with a useful tool to select the schedules that better fit their risk profiles. We use an iterative mechanism to build confidence intervals within a certain confidence level during the method's simulation step, interrupting the procedure when it reaches the desired error. This strategy's advantage is highlighted in the computational experiments, which indicates that the number of replications of the simulation is instance and uncertainty level dependent. A periodic re-planning strategy is also used to evaluate the performance of the simheuristic, highlighting the advantages of using the proposed algorithm in a real-life usage situation. [ABSTRACT FROM AUTHOR]

In this paper, we consider a single machine parallel batch scheduling problem subject to chains of jobs. We present polynomial lower and upper bounds as well as their experimental comparison and relative errors. According to the results of the numerical experiment, the relative difference between upper and lower bounds does not exceed 1.5. [ABSTRACT FROM AUTHOR]

This paper presents the problem of batching and scheduling jobs belonging to incompatible job families on unrelated-parallel machines. More specifically, we investigate cost-efficient approaches for solving batching and scheduling problems concerning the desired lower bounds on batch sizes ( LB b ), which indirectly has a considerable impact on the production cost. Batch scheduling is a more realistic extension of the traditional group scheduling approach, in which the jobs belonging to a job family can be processed as multiple batches. The objective is to minimize the total weighted job completion time and tardiness subject to a machine- and sequence-dependent setup time, dynamic machine availability and job release times, customer segments and job priority, and different machine capability and eligibility criteria for processing. Solving this type of batch scheduling problem is a big challenge due to the high computational complexity incurred by both the sequencing assignment and batching composition. A machine learning random forest classification algorithm is used for the LB b determination. Then, an efficient mixed-integer linear programming model (MILP) is developed based on the flow conservation constraints of jobs on machines to reduce the computational complexity. By mapping the MILP model onto a network formulation, an equivalent integer set partitioning type formulation is developed for a branch-and-price optimization algorithm. Computational experiments carried out over different sets of instances, indicate the efficiency and effectiveness of the optimization algorithm, compared to the linear relaxation and relaxed MILP models. Regarding the only available benchmark in the literature, the optimization algorithm yields optimal solutions with affordable computational time. [ABSTRACT FROM AUTHOR]

In the field of production scheduling, due to the influence of many factors such as production technology, each production process usually requires multiple machines to simultaneously participate in processing. Meanwhile, the number of workpieces to be processed is large, and each type of workpiece needs to be processed in batches for shortening the production cycle. Aiming at the above problems, in a job shop environment, this paper adopts a variable batching scheme according to the load of the machines involved in each processing process, and proposes a non-mixed multi-processor combined production batch scheduling model and integrate the brainstorming algorithm to search the shortest processing time. Moreover, an improved brainstorming algorithm is proposed by introducing greedy thinking and dynamic discussion mechanism. The number of discussions is changed adaptively with the iteration and the global search and local search are utilized to strengthen the search ability of the proposed algorithm. Finally, it is shown via the test results that the improved brainstorming algorithm is more efficient and convergent than the basic brainstorming algorithm. [ABSTRACT FROM AUTHOR]

• A MILP model for the DRHHFBSP is developed. • A construction heuristic capable of generating excellent solutions is developed. • An iterative construction-local search-reconstruction algorithm is designed. In recent years, the distributed hybrid flowshop scheduling problem (DHFSP) has garnered widespread attention due to the continuous emergence of practical challenges. The production model, characterized by multiple varieties and small batches, is widely observed in the industrial sector. Additionally, in various real-world scenarios, batches often undergo repeated processes across multiple stages. This paper addresses the research gap by introducing the reentrant nature of batches and the heterogeneity of factories into the DHFSP, resulting in a novel problem referred to as the distributed reentrant heterogeneous hybrid flowshop batch scheduling problem (DRHHFBSP). To tackle this problem, we propose a mixed-integer linear programming (MILP) model. Given that this problem falls into the NP-hard category, an iterative construction-local search-reconstruction algorithm (ICLSRA) is designed. Specifically designed by incorporating construction, local search, and reconstruction processes that have different roles, this algorithm strikes a balance between local and global search. Comparative analysis with the MILP model and state-of-the-art algorithms demonstrates the superiority of ICLSRA in achieving efficient solutions for the DRHHFBSP. [ABSTRACT FROM AUTHOR]

Copyright of Computer Measurement & Control is the property of Magazine Agency of Computer Measurement & Control and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

We propose a batch-scheduling model to minimize the total actual flow time (TAF) of parts to be processed in a flow shop consisting of m batch-processing machines. A batch-processing machine (BPM) is a machine that can process several parts at once, and the TAF of parts is the total interval time from the arrival times to the corresponding due date. In the real world, shop floors often have production lines with BPMs and multistage processes. We were motivated by a real problem in the aircraft industry and aimed to simultaneously satisfy the due dates and minimize the total time that parts spend in the shop. The problem was formulated as a mathematical model and solved using a proposed algorithm. The batch-scheduling problem is divided into batching and scheduling subproblems. The solution has been obtained by adopting backward scheduling. This paper develops a new model of flow shop scheduling problem for the shop with batch processing machines and the heuristic solution method. It provides numerical examples and their results to demonstrate the effectiveness of the proposed algorithm for solving the problem. [ABSTRACT FROM AUTHOR]

This paper studies the scheduling problem of jobs with release times, non-identical sizes, and incompatible job families on unrelated parallel batch machines. The capacities of batch machines and the processing times of each job on the batch machines are different. The processing time of one batch is equal to the longest processing time of jobs in this batch. Different types of jobs are not allowed to be assigned into the same batch, which is known as incompatible job families. Mixed integer linear programming and constraint programming (CP) models are proposed. A new batch-based local search method is designed and an iterated greedy (IG) algorithm is developed to avoid unreasonable exchanging of jobs during the local search. Numerical results show that the CP method can obtain high quality solutions in the small-scale instances. For the large-scale instances, the IG algorithm with the new local search method has a competitive performance. [ABSTRACT FROM AUTHOR]

This study examined the flexible assembly job-shop scheduling problem with lot streaming (FAJSP-LS), common in multivariety and small-batch production, such as household electrical appliances. In FAJSP-LS, an assembly stage is appended to the flexible job shop, and jobs in the first stage are processed in a large batch to reduce switching costs, while leading to more waiting time, especially during the assembly stage. This article considered splitting the batch into a few sub-batches of unequal and consistent sizes to allow jobs to efficiently pass the two-stage system. With this objective, the problem was modeled as a mixed-integer linear program comprising the following two subproblems: batch splitting and batch scheduling. As the integrated problem is NP-hard, the improved bioinspired algorithm based on an artificial bee colony was proposed, including a four-layer chromosome–encoding structure to describe the solution, as well as an optimization strategy utilizing different bee colonies to synchronously solve this two-stage problem. To examine the algorithm’s efficiency, a benchmark case was used to show that better solutions can be acquired with the improved algorithm regardless of whether the batch was split into equal or unequal sizes. To promote practical implementation, the algorithm was applied to a real case refrigerator workshop and showed better performance on time efficiency when jobs were split into unequal sizes compared to jobs without splitting or splitting into equal sizes.

Summary: Computer aided engineering (CAE) practices improved drastically within the last decade due to ease of access to computing resources and open‐source software. However, increasing complexity of hardware and software settings and the scarcity of multiskilled personnel rendered the practice inefficient and infeasible again. In this article, we present a method for continuous performance improvement in computational engineering that combines online performance profiling with machine learning (ML). To test the viability of this method, we provide a detailed analysis for solution time estimation of finite element analysis (FEA) jobs based on multidimensional models. These models combine numerous matrix features (matrix size, density, bandwidth, etc.), solver features (direct‐iterative, preconditioning, tolerance), and hardware features (core count, virtual–physical). We repeat our analysis over different machines as well as docker containers to demonstrate applicability over different platforms. Next, we train supervised and unsupervised ML algorithms over commonly used, realistic FEA benchmarks and compare accuracy of different models. Finally, we design two new ML‐based online batch schedulers called shortest predicted time first (SPTF) and shortest cluster time first (SCTF), which are comparable in performance to the optimal, but offline shortest job first (SJF) scheduler. We find that ML‐based profiling and scheduling can reduce the average turnaround times by 2×–5× over other alternatives. [ABSTRACT FROM AUTHOR]

Copyright of Operations Research Transactions / Yunchouxue Xuebao is the property of Editorial office of Operations Research Transactions and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

This study addresses the issue of scheduling batch machine to minimize total tardiness. Vacuum heat treatment allows multiple jobs to be processed as a batch, as long as they do not exceed the machine's weight and size limits; the weight and size of the jobs both impact the batch processing time. By considering the differences in the release time and due date for each job, a mixed-integer linear programming model is developed and validated using small-scale instances. To tackle large-scale scheduling problems, an intelligent algorithm based on deep reinforcement learning is proposed. Double deep Q-learning networks are designed, and the environmental state feature matrix is extracted as input parameters for the networks. Four job-sorting rules and three scheduling time windows are defined, resulting in twelve action rules within the action space. The most suitable action rule is dynamically selected based on the current batch's environmental status during the scheduling process. Through extensive comparison using large-scale random data, the proposed algorithm demonstrates significantly improved scheduling performance compared to the benchmark algorithms. • A new mixed-batch scheduling problem involves batch times influenced by job weight/size, constrained by machine weight/size. • An intelligent algorithm based on DRL (Deep Reinforcement Learning) was proposed to address batch scheduling problems. • Double deep Q-learning networks were designed, with environmental state feature matrix extracted as input for the networks. • Four job sorting rules and three scheduling time windows were defined, yielding twelve action rules in the action space. • Dynamic selection of the most suitable action rule based on the current batch's environmental status during the scheduling. [ABSTRACT FROM AUTHOR]

• In this paper, we present CProS (C hemical pro duction S cheduling), a free-to-use web-based application (https://cpros.azurewebsites.net/) for chemical production scheduling. • The application offers a graphical interface to model production facilities and provides an array of solution methods. • The paper provides essential details on the models and methods used in the application, and a step-by-step guide to help the users navigate the interface. While a large range of models and methods have been proposed in the literature for chemical production scheduling, very limited tools are available for researchers to test these methods. This communication describes a web-based application (CProS) that was recently developed to facilitate the generation and solution of chemical production scheduling instances. The application offers an interface through which a user can define an instance using the state-task network (STN) representation. Given an instance, the application then automatically generates a discrete-time STN-based mixed-integer linear programming (MIP) model. In addition, the user has the option to use three different solution methods: (1) tightening constraints; (2) a reformulation; and (3) a three-stage discrete-continuous algorithm. We showcase the functionality of the application through a case study. [ABSTRACT FROM AUTHOR]