Search

• 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]

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]

Path planning is an important and classical problem in theoretical research and practical applications. In the complex and hierarchical space scenarios, path planning faces more difficulties and challenges due to the structural particularity. Considering the directivity of paths in hierarchical spaces, it is more important to guarantee the fluency and efficiency of the paths in hierarchical spaces. In this paper, we introduce a path network planning problem from multi-source to multi-destination in hierarchical spaces, namely Balanced-Flow Path Network Planning (BF-PNP) problem, and prove its NP-completeness. To balance the flow rate among the layers in the space, we propose a batch scheduling algorithm with the objective of minimizing the scheduling time consumption. To evaluate the performance on efficiency and time complexity, we perform a series of simulations and the results indicate the advantages of the proposed algorithm. [ABSTRACT FROM AUTHOR]

Despite a great deal of research into precast production scheduling published in academic journals worldwide, little attention has been given to environmental performance related to precast construction transportation and assembly scheduling problems. To address this issue, this paper studies the Just-in-Time (JIT) strategy for supply chain management of precast construction while considering time-dependent transportation time and on-site assembly time. There are two main contributions of our work. First, our analysis expands the current batch-scheduling model of minimizing earliness/tardiness penalties, by incorporating environmental impact considering the time-dependent transportation time and economic impact of resources wasted by waiting for on-site assembly. Second, we quantify the economic and environmental performance using our research objective, consisting of earliness/tardiness penalties, an additional transportation time penalty, and a resource waste penalty. The optimal results show that, compared with the supplier's intuitive minimax optimization with deliveries on the earliest due date, there is an average 10.7% reduction of the objective value of a one-day assembly task by our proposed method. The results also show that the objective of achieving additional environmental performance conflicts with that of obtaining economic performance. However, sensitivity analysis further shows it is not always true to consider only additional environmental performance for the suppliers to achieve ‘green’ value. For a sustainable business, the customer's service-JIT delivery should also be considered. Thus, when the policy makers assign importance weights to different objectives, they should fully consider both the economic and environmental impacts. The research contributes to batch delivery theory by expanding the approach to a time-dependent delivery model by considering both the economic and environmental effects. The method developed is of practical value for precast building projects to help in the successful implementation of sustainable development. [ABSTRACT FROM AUTHOR]

We present in this study an algorithmic framework of an intelligent scheduling system that aims to provide an optimum planning for the production process of cutting tools taking into consideration the constraining conditions such as production characteristics, capacity, and performance criteria. Once blunt, cutting tools are sent to the sharpening service composed of parallel machines capable of sharpening more than one tool at the same time. After sharpening, tools are sent back to the departments of origins to be used in other production processes. Thus, any delay in the sharpening service provokes delays in other departments. We develop first a genetic algorithm enhanced by a dynamic programming procedure capable of optimally scheduling a given job sequence. Then we develop a branch and bound method that emulates at each node possible decisions based on a postpone or schedule strategy. Numerical results show that both methods give high quality solutions for the scheduling of tool sharpening operations. Beside the minimization of total tardiness, many other types of decision making related to minimal operation time of a sharpening service, minimal amount of cutting tool inventory and the number of required sharpening machines can be deduced thanks to applying our models. [ABSTRACT FROM AUTHOR]

With the increasing energy price, the rapid growth of electricity demand and severe challenges for sustainable development, energy-efficient scheduling is becoming more and more important for power-intensive manufacturing industry, especially for batch production companies. This paper investigates a bi-objective single machine batch scheduling problem with non-identical job sizes, the time-of-use (TOU) electricity prices, and different energy consumption rates of the machine. The first objective is to minimize the makespan and the second is to minimize the total energy costs, by considering both the machine utilization and the economic cost. The problem is formulated as an integer programming model. Then, an exact ε -constraint method is adapted to obtain the exact Pareto front. To deal with large scale problems, based on decomposition ideas, two heuristic methods are developed to obtain approximate Pareto fronts. Computational experiments on randomly generated instances show the effectiveness of the methods. A study case of a real-world glass manufacturing company is also conducted to show that the proposed methods are promising for practical usages. [ABSTRACT FROM AUTHOR]

In this paper a mixed-integer linear programming (MILP) model is presented to minimize makespan of single-stage multiproduct parallel batch production with sequence dependent changeovers. The computational inefficiency and suboptimal problems are addressed by the tight and rigorous formulation of the proposed model. Subtours (subcycles) are eliminated simultaneously so that the optimal solution is obtained in one step. The proposed model is tested with two examples. The results show that the model obtains the global optimal solutions with significant improvement in solution time. [ABSTRACT FROM AUTHOR]

We present an effective scheduling heuristic for realistic production planning in a petrochemical blending plant. The considered model takes into account orders spanning a multi-product portfolio with multiple bills of materials per product, that need to be scheduled on shared production facilities including a complex pipeline network. Capacity constraints, intermediate storage restrictions, due dates, and the dedication of resources to specific product families have to be respected. The primary objective of the heuristic is to minimize the total order tardiness. Secondary objectives include the minimization of pipeline cleaning operations, the minimization of lead times, and the balanced utilization of filling units. The developed algorithm is based on a dynamic prioritization-based greedy search that schedules the orders sequentially. The proposed method can schedule short to mid-term operations and evaluate different plant configurations or production policies on a tactical level. We demonstrate its performance on various real-world inspired scenarios for different scheduling strategies. Our heuristic was used during the construction phase of a new blending plant and was instrumental in the optimal design of the plant. [ABSTRACT FROM AUTHOR]

This work presents the sizing and scheduling of a semi-batch plant for the production of 348ton/year of pectin from Valencia orange peels under optimum experimental extraction conditions (90 °C, 75 min, pH 1.5). The designed plant included acid hydrolysis of peels, filtration of the hydrolyzed suspension, alcoholic precipitation of pectin, gel pressing, gel drying, and pectin size reduction. Calculations of processing times and size of units were done with Microsoft Excel® and Aspen Plus v7.3®. Characteristic dead times in the precipitation stage of the conventional processes were eliminated by implementing two out-of-phase hydrolysis stages, which lowers the batch size and the dimensions of hydrolysis tanks; this is an important improvement given the technical difficulties that may arise when handling large amounts (e.g., above lton) of highly-viscous suspensions (e.g., above 100 cP), such as those present in the hydrolysis stage of pectin extraction. Up to 76% ethanol recovery was achieved by means of the operation of a continuous distillation column. Furthermore, rheological behavior of the liquid obtained from the hydrolysis of orange peels in acidic media, as well as the drying of pectin gels was modeled in this contribution. In particular, the rheological analysis allowed a more realistic estimation of energy demands for heat transfer and agitation in the hydrolysis stage, which resulted to be the process bottleneck and determined the cycle time and, consequently, defined the equipment size. [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]

Abstract: This paper considers the scheduling problem of parallel batch processing machines with non-identical job sizes. The jobs are processed in batches and the machines have the same capacity. The models of minimizing makespan and total completion time are given using mixed integer programming method and the computational complexity is analyzed. The bound on the number of feasible solutions is given and the properties of the optimal solutions are presented. Then a polynomial time algorithm is proposed and the worst case ratios for minimizing total completion time and makespan is proved to be 2 and (8/3–2/3m) respectively. To test the proposed algorithm, we generate different levels of random instances. The computational results demonstrate the effectiveness of the algorithm for minimizing the two objectives. [Copyright &y& Elsevier]

Abstract: We study the online batch scheduling problem on parallel machines with delivery times. Online algorithms are designed on parallel batch machines to minimize the time by which all jobs have been delivered. When all jobs have identical processing times, we provide the optimal online algorithms for both bounded and unbounded versions of this problem. For the general case of processing time on unbounded batch machines, an online algorithm with a competitive ratio of 2 is given when the number of machines or , respectively. When , we present an online algorithm with a competitive ratio of . [Copyright &y& Elsevier]

Abstract: This paper considers a coordinated scheduling problem. For the first-stage transportation there is a crane available to transport the product from the warehouse to a batching machine. For the second-stage transportation there is a vehicle available to deliver the completed jobs from the machine shop floor to the customer. The coordinated scheduling problem of production and transportation deals with sequencing the transportation of the jobs and combining them into batches to be processed. The problem of minimizing the sum of the makespan and the total setup cost was proven by Tang and Gong to be strongly NP-hard. This paper proposes two genetic algorithm (GA) approaches for this scheduling problem, with different result representations. The experimental results demonstrate that a regular GA and a modified GA (MGA) can find near-optimal solutions within an acceptable amount of computational time. Among the two proposed metaheuristic approaches, the MGA is superior to the GA both in terms of computing time and the quality of the solution. [Copyright &y& Elsevier]

Abstract: During the last 15 years, many mathematical models have been developed in order to solve process operation scheduling problems, using discrete or continuous-time representations. In this paper, we present a unified representation and modeling approach for process scheduling problems. Four different time representations are presented with corresponding strengthened formulations that rely on exploiting the non-overlapping graph structure of these problems through maximum cliques and bicliques. These formulations are compared, and applied to single-stage and multi-stage batch scheduling problems, as well as crude-oil operations scheduling problems. We introduce three solution methods that can be used to achieve global optimality or obtain near-optimal solutions depending on the stopping criterion used. Computational results show that the multi-operation sequencing time representation is superior to the others as it allows efficient symmetry-breaking and requires fewer priority-slots, thus leading to smaller model sizes. [Copyright &y& Elsevier]

Abstract: Short-term scheduling for batch processes which allocates a set of limited resources over time to manufacture one or more products plays a key role in batch processing systems of the enterprise for maintaining competitive position in fast changing market. This paper proposes an effective hybrid particle swarm optimization (HPSO) algorithm for polypropylene (PP) batch industries to minimize the maximum completion time, which is modeled as a complex generalized multi-stage flow shop scheduling problem with parallel units at each stage and different inventory storage policies. In HPSO, a novel encoding scheme based on random key representation, a new assignment scheme STPT (smallest starting processing time) by taking the different intermediate storage strategies into account, an effective local search based on the Nawaz–Enscore–Ham (NEH) heuristic, as well as a local search based on simulated annealing with an adaptive meta-Lamarckian learning strategy are proposed. Simulation results based on a set of random instances and comparisons with several adaptations of constructive methods and meta-heuristics demonstrate the effectiveness of the proposed HPSO. [Copyright &y& Elsevier]

Abstract: Semiconductor manufacturing is characterized by a manufacturing line with multiple processing tools, products, and other sources of variation. Run-to-run control applications need a constant stream of information about the state of the process in order to perform well. The trace of the state error covariance matrix from the Kalman filter is used as a metric for determining the information content of a particular data set to the run-to-run control algorithm. Processing decisions such as batch scheduling, equipment allocation, and sampling plans are shown to have an effect on estimator performance. Algorithms using the state error covariance matrix are developed that can optimize the factory schedule in order to provide run-to-run control algorithms with the best possible information. Simulation results demonstrate that measurable improvements in state estimation and control output performance can be achieved by using information from the process estimator. [Copyright &y& Elsevier]

Abstract: We study the coordinated scheduling problem of hybrid batch production on a single batching machine and two-stage transportation connecting the production, where there is a crane available in the first-stage transportation that transports jobs from the warehouse to the machine and there is a vehicle available in the second-stage transportation to deliver jobs from the machine to the customer. As the job to be carried out is big and heavy in the steel industry, it is reasonable assumed that both the crane and the vehicle have unit capacity. The batching machine processes a batch of jobs simultaneously. Each batch occur a setup cost. The objective is to minimize the sum of the makespan and the total setup cost. We prove that this problem is strongly NP-hard. A polynomial time algorithm is proposed for a case where the job transportation times are identical on the crane or the vehicle. An efficient heuristic algorithm for the general problem is constructed and its tight worst-case bound is analyzed. In order to further verify the performance of the proposed heuristics, we develop a lower bound on the optimal objective function. Computational experiments show that the heuristic algorithm performs well on randomly generated problem instances. [Copyright &y& Elsevier]

Abstract: An engineered evolutionary algorithm for a realistic chemical batch scheduling problem with uncertain data is developed systematically. The problem is formulated as a two stage stochastic integer program with discrete scenarios. The model is solved by a stage decomposition-based hybrid algorithm using an evolutionary algorithm combined with mixed-integer programming. Earlier experiments with a standard evolutionary algorithm led to the hypothesis that the constrained search space is not covered well such that in some cases the population converges to a subset of the solution space which does not include the best known solution. An efficient engineered evolutionary algorithm is developed which is shown to cover the feasible set significantly better such that a high quality feasible schedule can be generated comparatively fast. As the hierarchical structure of the case study is typical for many batch scheduling problems, some general principles may be postulated from the experience gained here. [Copyright &y& Elsevier]

Abstract: An optimal operating mode for a sequencing batch reactor was determined via a model-based optimization. Synthetic wastewater containing mainly organic matter (as glucose) and nitrogen (as ammonium chloride) was treated without any addition of an external carbon source to accomplish denitrification step. A simplified model was used to describe process dynamics, comprised of six ordinary differential equations and an empirical correlation for oxygen consumption rate. Batch cycle time was the chosen objective function to be minimized for a fixed volume of waste to be treated. Furthermore, as SBR operation is divided in two major phases – aerobic and anoxic, to achieve total pollutants removal within minimum time, these phases can be repeatedly alternated. To ensure availability of organic matter necessary for denitrification, these two phases were combined with feed steps. Different feed strategies were tested using one, two or three feed steps. A successive quadratic programming algorithm was used, and maximum values for final COD, nitrate and ammonium concentrations, as well as maximum feed pump flow rate were some the process constraints. One step feed strategy was indicated by the optimization leading to a batch cycle time of 5h. [Copyright &y& Elsevier]

Abstract: In this paper, we present new approximation results for the offline problem of single machine scheduling with sequence-independent set-ups and item availability, where the jobs to be scheduled are independent (i.e., have no precedence constraints) and have a common release time. We present polynomial-time approximation algorithms for two versions of this problem. In the first version, the input includes a weight for each job, and the goal is to minimize the total weighted completion time. On any input, our algorithm produces a schedule whose total weighted completion time is within a factor 2 of optimal for that input. In the second version, the input includes a due date for each job, and the goal is to minimize the maximum lateness of any job. On any input, our algorithm produces a schedule with the following performance guarantee: the maximum lateness of a job is at most the maximum lateness of the optimal schedule on a machine that runs at half the speed of our machine. [Copyright &y& Elsevier]

Abstract: Starting from a batch scheduling problem, we consider a weighted subcoloring in a graph G; each node v has a weight ; each color class S is a subset of nodes which generates a collection of node disjoint cliques. The weight is defined as . In the scheduling problem, the completion time is given by where is a partition of the node set of graph G into color classes as defined above. Properties of such colorings concerning special classes of graphs (line graphs of cacti, block graphs) are stated; complexity and approximability results are presented. The associated decision problem is shown to be NP-complete for bipartite graphs with maximum degree at most 39 and triangle-free planar graphs with maximum degree k for any . Polynomial algorithms are given for graphs with maximum degree two and for the forests with maximum degree k. An (exponential) algorithm based on a simple separation principle is sketched for graphs without triangles. [Copyright &y& Elsevier]

This contribution deals with scheduling problems of flexible chemical batch processes with a special emphasis on their real-time character. This implies not only the need for sufficiently short response times, but in particular the burden of in-complete knowledge about the future. To solve such problems, the application of two-stage stochastic integer programming techniques on moving horizons is proposed. They reflect the need for immediately applicable decisions and the potential of later recourse actions to cope with realized uncertainties. In addition to the classical expected value objective, simple measures of risk can be included. Motivated by an example process, some essential modeling prerequisites are discussed. As an important first step, the master scheduling problem is studied and a number of master scheduling models are presented. Large mixed-integer linear problems arise, which are well-suited for a dual decomposition approach. Numerical experiments with a problem-specific solution algorithm demonstrate the applicability of the method to real-world problems. [Copyright &y& Elsevier]

The paper presents a mixed integer programming approach for makespan minimization in flexible flow lines. The line consists of several processing stages in series, separated by finite intermediate buffers, where each stage has one or more parallel identical machines. The problem objective is to determine a minimum length schedule for a mix of part types, where identical parts are scheduled consecutively. The limited intermediate buffers between the stages result in a scheduling problem with machine blocking, where a completed part may remain on a machine and block it until a downstream machine becomes available. Numerical examples modeled after real-world surface mount technology lines for printed wiring board assembly are provided and some computational results are reported to illustrate the approach. [Copyright &y& Elsevier]