Global manufacturing optimizes production efficiency and cost, enabling enterprises to compete effectively. Distributed production is emerging for the trend of globalization and the requirements of diversified manufacturing, for which distributed scheduling plays an important role in enterprises enhancing efficiency and conserving energy. This study investigates a heterogeneous distributed permutation flowshop scheduling problem to minimize the makespan, in which release date and factory speed are incorporated to mirror a real-world production scenario. A mixed integer programming model is established to address this NP-complete problem using a business optimizer. The findings assist in identifying optimal properties for algorithm development and assessing the performance of a proposed branch and bound algorithm, which includes a problem-specific pruning rule and defined lower and upper bounds to reduce the solution space. For industrial scheduling, a dispatching rule named Dynamic Largest Processing Volume on the Fastest Machine First is proposed, offering asymptotic optimality and ensuring uninterrupted production. Additionally, a discrete artificial bee colony algorithm with a novel availability rule and an abandonment criterion is introduced to improve efficiency. Simulation results demonstrate the efficacy of the proposed algorithms.Note to Practitioners—Distributed production leverages information technology to integrate geographically decentralized manufacturing units for cost reduction and production enhancement. This mode finds extensive application in automobile, electronics, and medical equipment manufacturing. In mass production scenarios, the online Dynamic Largest Processing Volume on the Fastest Machine First rule provides a viable alternative to optimal algorithms, delivering a convergent schedule rapidly and preventing unnecessary delays. In complex industrial settings, the discrete artificial bee colony algorithm offers effective solutions without relying on a mathematical model, proving more efficient in such environments.

Time-of-use (ToU) tariffs flexibly offer markedly cheap electricity prices to industrial and residential users during off-peak periods, encouraging them to shift their peak electricity demands in valley periods. Although ToU tariffs play a crucial role in balancing electricity supply and demand, especially in energy-intensive industries, the best trade-off between industrial performance and energy costs has not been well explored. Manufacturing consumes a substantial amount of energy, primarily in the form of electricity, leading to imbalances in power consumption. The flow shop scheduling (FSS) model is one of the most prevalent models in manufacturing. To explore the significant role of ToU tariffs in manufacturing, this study addresses a bi-objective FSS problem under ToU tariffs. The objective is to find the optimal balance between customer satisfaction and total electricity cost. A tight mixed integer programming model is developed to solve this NP-hard problem using business optimizers. On the bases of the problem properties demonstrated in this study, valid inequalities are designed to reduce the solution space of the problem. For small-scale instances, an improved$\varepsilon $-constraint method is presented to find the Pareto front. For medium and large-scale instances, a two-stage fruit fly optimization (TFFO) algorithm is developed to obtain the near Pareto front. Experimental results demonstrate the efficiency and effectiveness of the proposed model and algorithms.Note to Practitioners—Scheduling for complex systems remains a formidable challenge in manufacturing. Energy cost saving is a major objective for all energy-intensive industries. Effective scheduling is crucial for businesses achieving eco-friendly performance, especially under ToU tariffs. This study aims to provide efficient scheduling model and methods that can guide decision-makers in fostering ecological transitions. The$\varepsilon $-constraint method can find globally optimal solutions within given constraints. This situation is particularly beneficial for small-scale production systems requiring high accuracy. The TFFO algorithm can handle complex industrial environments and enhance production efficiency. Additionally, the TFFO algorithm is flexible and extensible, enabling it to be generalized to other production scenarios. Overall, the proposed model and algorithms lay a solid foundation for achieving efficient scheduling under ToU tariffs.

Food supply chain (FSC) management has attracted increasing attention from academics and practitioners in recent years. Although the closed-loop FSC (CLFSC) with returnable transport items (RTIs) has many realistic applications, it is rarely studied. This paper studies a new production-transportation planning problem for a closed-loop perishable FSC with shared RTIs, in which the RTIs can be used by different manufacturers belonging to the same company. The problem consists of determining production, transportation, and inventory quantities for each period of a considered planning horizon to maximize the total profit of the whole supply chain. For the problem, we first formulate it as a mixed-integer linear program (MILP). To efficiently solve the NP-hard problem, we then develop a two-phase heuristic algorithm (TPHA). Experimental results of randomly generated instances show that the performance of the TPHA outperforms the direct use of a commercial solver CPLEX, the differential evolution algorithm, and column generation. Finally, the benefits of the shared RTI strategy and differential price strategy in a CLFSC are verified.

The U-shaped yard is an important part of the U-shaped automated container terminal (U-ACT), which consists of a set of blocks used for storing containers, I-lanes for automated guided vehicles (AGVs) travel, and U-lanes for external trucks (ETs) travel. Double-side cantilever yard cranes (DCYCs) perform stacking and unstacking operations for containers transported by AGVs and ETs. Managing and coordinating the operations of DCYC, AGVs, and ETs, not only improves the operation efficiency of U-ACTs but also helps to promote the development of green ports. This paper addresses the problem of scheduling DCYCs and path planning for AGVs and ETs in the U-ACT. To achieve this, we establish a bi-objective mixed integer programming model to minimize both the makespan and the energy consumption. The model considers conflicts between two DCYCs within each block, ensures workload balance for these DCYCs, optimizes parking slots for AGVs and ETs, and schedules appropriate entry times for AGVs and ETs into the yard to reduce conflicts. To solve this model, we develop an improved multi-objective particle swarm optimization (IMOPSO) algorithm, where a globally optimal heuristic search mechanism and several conflict avoidance strategies to plan conflict-free spatiotemporal paths are introduced to accelerate the convergence of the algorithm. Numerical experiments demonstrate the superiority of the IMOPSO approach in terms of multiple metrics, confirming the effectiveness of the optimized vehicle entry timing strategy, which improves efficiency by 7.33% and yields energy savings by 11.72%. These findings clearly highlight that our model and solution approach can effectively enhance the operational efficiency of DCYCs, AGVs, and ETs, contributing to the overall improvement of container terminal operations.

Relief network design for predictable disasters is a key issue in humanitarian logistics. However, existing studies on relief network design have not simultaneously considered multiple relief decision stages and the uncertainties which are reduced by improved forecast accuracy as a disaster approaches. These aspects are critical for efficient relief activities. The present study investigates a new relief network design problem for predictable disasters, especially typhoons, which have become increasingly frequent and severe in recent years. It integrates facility location decisions before any specific disaster warnings are issued, relief supply deployment and evacuation decisions between a warning and the onset of the disaster, and relief supply distribution decisions after a disaster strikes. This study also considers time-dependent uncertainties of the disaster’s trajectory and intensity together. For the problem, a novel three-stage hybrid distributionally robust and robust optimization (3HDRO) model is proposed. To make it computationally tractable, the 3HDRO model is transformed into a deterministic equivalent (DE) model. A scenario-based decomposition heuristic algorithm is then designed to solve the DE model for large-scale instances. A case study of historical typhoons in Guangdong Province, China, is used to gain insights into the critical model parameters for disaster relief activities. Furthermore, experimental results on randomly generated instances demonstrate the effectiveness and efficiency of the proposed model and algorithm.

The hybrid flow shop scheduling (HFS) model has significant practical applicability in fields, such as manufacturing, transportation, service, and communication. However, learning effects, refer to the phenomenon of processors spending less processing time with more familiar operations, which are common constraints in actual production while often ignored in HFS research despite their significant impact on processing efficiency. In this article, an HFS problem with learning effects and release dates is investigated from a practical application perspective. For large-scale instances, a dispatching rule-based heuristic is developed with theoretical performance guarantees by demonstrating the asymptotic optimality and the tight worst-case bound. For small-scale instances, a branch-and-boun3d algorithm is designed to obtain an exact solution. An elaborate branching scheme, an idle-time-based pruning rule, and a task-splitting-based lower bound effectively reduce the search space. For medium-scale instances, a hybrid shuffled frog-leaping algorithm combined with macro evolution and local intensification is presented to search for high-quality solutions. Extensive experiments demonstrate the superiority of the developed algorithms against the state-of-the-art algorithms.

The COVID-19 pandemic has not only posed a significant threat to health, life, economy, and the whole society but also led to numerous new theoretical and practical challenges for automation science and engineering. The goal of this Special Issue is to bring together researchers and practitioners into a forum to show the state-of-the-art research and applications in responding to the challenges and opportunities of automation science and engineering to the pandemic, by presenting efficient scientific and engineering solutions, addressing the needs and difficulties for integration of new automation methodologies and technologies, and providing visions for future research and development.

Growing global trade brings an increasing challenge to intelligent maritime transportation, which is an important branch of the intelligent transportation system. Developing efficient technologies to improve the performance of intelligent maritime transportation is especially important. Most existing works for integrated berth allocation and quay crane assignment assume that all the equipment is available over the time horizon, however, there exists frequently time-consuming quay crane maintenance activities in the maritime port. It is recognized that maintenance activities can impact the loading/unloading activities. In this paper, we study a new bi-objective optimization model of integrated berth allocation and quay crane assignment with preventive quay crane maintenance activities. The two objectives are minimizing the total turnaround time of vessels and the total penalty cost of quay crane maintenance earliness and tardiness. For the considered problem, an appropriate integer linear programming model is formulated, and an$\varepsilon $-constraint-based two-phase iterative heuristic is designed based on the characteristics of our problem. Computational results on a case study and randomly generated instances show the efficiency of the proposed algorithm.

The inventory routing problem (IRP) arises in a broad spectrum of real-life applications related to joint decisions of inventory and routing. In the basic IRP, a supplier has to make decisions about the delivery timing, delivered quantity of a single product and routing with a single vehicle to a set of retailers without backlog. It poses computational challenge due to its natural complexity. To tackle this problem, we propose a two-phase decomposition-based heuristic method. In Phase 1, a logic-based Benders like decomposition method is employed to first determine the retailers’ replenishments, followed by the routing decisions individually for each period. Valid cuts, inequalities for diversification constraints and for greedy search are employed. Then, the solutions obtained in Phase 1 are improved with a restricted mixed integer linear programming (MILP) model in Phase 2. Computational experiments are conducted on 220 benchmark problem instances with up to 200 retailers and 6 periods. The results show the high performance of the proposed method and it is comparable to the state-of-the-art heuristics in terms of both efficiency and effectiveness.

We study a new competitive multi-facility location and quality design problem in a continuous space. The facility location and quality design are considered together because of their interdependence. Especially, new entrant facilities compete for customer demands with existing ones and the latter’s reactions are taken into account. The goal is to maximize the profit of all new entrant facilities by optimally determining their locations and qualities. For this problem, a probabilistic Huff-like gravity model is adopted to analyze the market share to be captured by new and existing facilities, and then a mathematical programming model is provided based on the market share analysis. Since it is shown to be strongly NP-hard, a new iterative solution framework is first proposed to solve it, where at each iteration, new configurations of facility locations are firstly generated, and then the quality decisions of all facilities are modelled as a competitive decision process by a non-cooperative game. The best qualities for new and existing facilities are determined by their Nash equilibrium. Finally, optimal or near-optimal solutions are calculated. Then based on the proposed solution framework, a particle swarm optimization-based approach is developed. Computational results for randomly generated instances indicate that the devised algorithm is able to find suitable locations and qualities of newly entering facilities in a competitive environment and outperforms favorably a genetic algorithm-based approach.

This work investigates the problem of optimally locating an automotive service firm (ASF) subject to stochastic customer demands, varying setup cost and regional constraints. The goal is to minimize the transportation cost while maintaining the specified profit of the ASF. This work studies two variants of the problem: ASF location with known demand probability distributions and with partial demand information, i.e., only the support and mean of the customer demands are known. For the former, a chance-constrained program is formulated that improves an existing model, and then an equivalent deterministic nonlinear program is constructed based on our property analysis results. For the latter, a novel distribution-free model is developed. The proposed models are solved by solver LINGO. Computational results on the benchmark examples show that: i) for the first variant, the proposed approach outperforms the existing one; ii) for the second one, the proposed distribution-free model can effectively handle stochastic customer demands without complete probability distributions; and iii) the results of the distribution-free model are slightly worse than those of the deterministic nonlinear one, but the former is more cost-efficient for the practical ASF location as it is less expensive in obtaining demand information. Moreover, the proposed models and approaches are extended to address a multi-ASF location allocation under demand uncertainty.

With the increase of transport demands, more pressure and challenges are being imparted into efficient transportation. As a conventional and direct congestion alleviation strategy, constructing new roads and lanes are increasingly restricted by limited land resources and high costs. Thus, making full use of existing transport network via appropriate management is critical to realize the sustainable development of transportation systems. As a flexible management strategy, lane reservation strategy has been widely adopted in real life. The reserved lanes can improve the efficiency of special transports, while they bring negative impact such as travel delay for general-purpose transports. In addition, the setting and operating of reserved lanes require a certain amount of cost. This paper proposes a new dual-objective integer linear programming model for optimally determining reserved lanes on a network for time-guaranteed special transports in order to simultaneously maximize the benefits and minimize the negative impact brought by reserved lanes, which incorporates road residual capacity and limited budget to the actual decision. Moreover, an iterative weighted sum-based method is proposed to solve it, in which a new relax-and-optimize algorithm is developed to exactly solve the single-objective optimization problems. Results of extensive numerical experiments show the effectiveness and efficiency of the proposed model and approach.

An intelligent logistics system is an important branch of intelligent transportation systems. It is a great challenge to develop efficient technologies and methodologies to improve its performance in meeting customer requirements while this is highly related to people's life quality. Its high efficiency can reduce food waste, improve food quality and safety, and enhance the competitiveness of food companies. In this paper, we investigate a new integrated planning problem for intelligent food logistics systems. Two objectives are considered: minimizing total production, inventory, and transportation cost and maximizing average food quality. For the problem, a bi-objective mixed integer linear programming model is formulated first. Then, a new method that combines an ϵ-constraint-based two-phase iterative heuristic and a fuzzy logic method is developed to solve it. Computational results on a case study and on 185 randomly generated instances with up to 100 retailers and 12 periods show the effectiveness and efficiency of the proposed method.

The air transport industry is an important branch of the intelligent transportation system (ITS). It is widely admitted that modern ITS technologies and advanced management methods, such as fleet assignment, aircraft maintenance routing, and crew scheduling, can significantly increase an airline's market share and profit, and also improve customer satisfaction. This paper studies a new airline stochastic fleet assignment problem with random passenger demands under risk aversion. The objective is to maximize the expected total profit at a certain level of risk avoidance (i.e., conditional value-at-risk). To solve this problem, we present a risk-averse two-stage stochastic mixed-integer programming model. The first stage mainly deals with tactic level decisions: assigning aircraft families (e.g., Airbus A380 family) to flight legs. The operational level decisions are made in the second stage to efficiently assign aircraft types (e.g., Airbus A380-800 or A380-800F) to flight legs while meeting the family assignment plan developed in the first stage. Then, a sample average approximation algorithm is proposed to solve the stochastic programming problem considering risk aversion. A realistic international airline's numerical experiment is conducted to illustrate the efficiency of the proposed two-stage stochastic programming model and algorithm.

A recent study has led to an interesting mixed-integer linear programming (MILP) model for parallel machine scheduling under time-of-use (TOU) tariffs, which assumes great importance in achieving sustainable economic development. In this paper, we provide an improved MILP model by significantly reducing the number of decision variables. The computational results show that the performance of the improved model is superior to that of the existing one.

It is challenging to perform emergency scheduling for fighting forest fires subject to limited rescue resources (i.e., vehicles with fire engines), since extinguishing each fire point should take into account multiple factors, such as the actual fire spreading speed, distance from fire engine depot to fire points, fire-fighting speed of fire engines, and the number of dispatched vehicles. This paper investigates a bi-objective rescue vehicle scheduling problem for multi-point forest fires, which aims to optimally dispatch a limited number of fire engines to extinguish fires. The objectives are to minimize the total fire-extinguishing time and the number of dispatched fire engines. For this problem, we first develop an integer program that is an improved and simplified version of an existing one. After exploring some properties of the problem, we develop an exact dynamic programming algorithm and a fast greedy heuristic method. Computational results for a real-life instance, and benchmark and large-size randomly generated instances confirm the effectiveness and efficiency of the proposed model and algorithms. Besides, a bi-objective integer program is developed to address the multi-depot fire engine scheduling issue.

Maritime transportation is an important branch of intelligent transportation system (ITS). It is widely recognized that modern ITS technologies and advanced management methods, such as automated yard crane (YC) planning and scheduling, can significantly improve container terminal performance, and also impact the global performance of maritime transportation. In this paper, we investigate two YC scheduling with storage and retrieval tasks in a container block. The main contributions of this paper are: (1) container reshuffling operations and inter-crane interference constraint are both considered and (2) the dynamic processing times for retrieval containers are taken into consideration. These typical YC operation characteristics complicate the YC scheduling, and cause late delivery and economic loss. In this study, we focus on minimizing the maximum tardiness of container task and establishing an integer linear programming model. Regarding the NP-hardness nature of the problem, we develop a heuristic named dividing, sequencing, and comparing (DSC) and a genetic algorithm (GA) based on the characteristics of the problem. The computational results show the efficient performance of the developed algorithms, compared with the exact solutions via Cplex software for small size instances. The efficiency and effectiveness of DSC outperform those of GA for practical size instances.

This paper addresses a new lane reservation problem called bus lane reservation problem (BLRP). The focus of the problem is on optimally selecting lanes to be reserved from an existing transport network and designing reserved lane-based bus paths, such that the rapid and station arrival-time guaranteed bus transit can be ensured, thereby achieving rapid and reliable bus transportation. However, once lanes are reserved, negative impact, such as an increase in travel time on adjacent non-reserved lanes may be caused. For this problem, an improved integer linear program is first formulated to minimize such negative impact. As the existing commercial solvers, e.g., CPLEX, can only solve small-size problems, we develop an exact enhanced cut-and-solve algorithm and an improved kernel search heuristic for solving medium- and large-size problems. Results of extensive numerical experiments confirm the effectiveness and efficiency of the proposed algorithms. In addition, a bi-objective robust BRLP is investigated to study the tradeoff between the negative impact of reserved lanes and the robustness of solution against the uncertainties in the link travel time and the bus dwell time.

Time-of-use (TOU) pricing has been implemented by many electricity suppliers to alleviate the peak load of power grid, which provides a good opportunity for industrial consumers to reduce their energy bills. In industrial enterprises that involve batch processing machines, energy expenditure often accounts for large portion of the final product cost. Optimizing batch scheduling under TOU tariffs in these enterprises will be of great significance. This study investigates a single machine batch scheduling problem under TOU tariffs. The objective is to minimize the total electricity cost by optimally scheduling all jobs within a given planning horizon. Two mixed integer linear programming (MILP) models, which are respectively based on time-index formulation and time-interval formulation, are developed for the problem. The models are solved by CPLEX. Computational results on randomly generated instances demonstrate the effectiveness of the proposed approaches.

In this paper, we study a two-stage capacitated facility location problem with choice of facility size. Given a set of potential sites for plants and a set of potential sites for depots, each of the plants and the depots has several possible sizes, and a set a customers with demands, the aim of the problem is to determine the locations of the plants and the depots as well as their sizes, the product flows from the opened plants, via the opened depots to the customers under the single-sourcing constraints, so that all of the customers' demands are satisfied with the minimum sum of the fixed opening costs of the facilities, the producing costs at the plants, the handling costs at the depots, the transportation costs from the plants to the depots and the customer-depot assignment costs. A mixed integer programming model for the problem is formulated and a LaGrange an relaxation approach is proposed to achieve a lower bound and an upper bound of the problem. The performance of the LaGrange an relaxation approach is evaluated on 200 randomly generated instances. The computational results demonstrate that the LaGrange an relaxation approach is effective with the average gaps around 1.30%.

This study investigates a new biobjective lanereservation problem, which is to exclusively reserve lanes from an existing transportation network for special transport tasks with given deadlines. The objectives are to minimize the total negative impact on normal traffic due to the reduction of available lanes for general-purpose vehicles and to maximize the robustness of the lane-reservation solution against the uncertainty in link travel times. We first define the robustness for the lanereservation problem and formulate a biobjective mixed-integer linear program. Then, we develop an improved exact ε-constraint and a cut-and-solve combined method to generate its Pareto front. Computational results for an instance based on a real network topology and 220 randomly generated instances with up to 150 nodes, 600 arcs, and 50 tasks demonstrate that the proposed method is able to find the Pareto front and that the proposed cut-and-solve method is more efficient than the direct use of optimization software CPLEX.

This paper studies a lane reservation problem for large sport events in big cities. Such events require organizers to deliver certain people and materials from athlete villages to geographically dispersed venues within a given travel duration. A lane reservation strategy is usually adopted in this circumstance to ensure that time-critical transportation tasks can be completed despite heavy urban traffic congestion. However, it causes negative impact on normal traffic. The problem aims to optimally select and reserve some lanes in a transportation network for the exclusive use of the tasks such that the total traffic impact is minimized. To solve the problem, we first develop an improved integer linear program. Then, its properties are analyzed and used to reduce the search space for its optimal solutions. Finally, we develop a fast and effective quantum-inspired evolutionary algorithm for large-size problems. Computational results on instances with up to 500 nodes in the network and 50 tasks show that the proposed algorithm is efficient in yielding high-quality solutions within a relatively short time.

Electricity is one of most widely used energies and encouraged to be saved by scientific management and new technologies such as Time-of-Use policy. Batch scheduling can significantly improve production efficiency and is used in many high electricity consumption and high technology industries. This paper investigates a new bi-objective single machine batch scheduling problem with TOU policy. The first objective is to improve productivity and the second aims to minimize the total electricity cost. For the problem, a bi-objective mixed integer nonlinear programming model is formulated. Its corresponding single objective optimization problems are linearized by analyzed properties such that the multiobjective ε-constraint method can be used to obtain Pareto solutions.

With economic development, a great amount of hazardous material is shipped in the transport network every day. Hazardous material transportation is well known for its high potential risk. An accident can cause very serious economic damage and will have a negative impact on public health and the environment over the long term. Transporting hazardous materials on special lanes can reduce the risk. However, a lane reservation strategy may worsen traffic conditions for other vehicles. This paper investigates a hazardous material transportation problem with lane reservation. The problem lies in how to choose lanes to be reserved in the network and select the path for each hazardous material shipment from the reserved lanes. The goal is to obtain the best compromise between the impact on normal traffic and the transportation risk. A multiobjective integer programming model is presented for the new problem. Then, an algorithm is developed based on the ε -constraint method and a fuzzy-logic-based approach. Pareto optimal solutions are obtained by the former, and a preferred solution is selected by the fuzzy-logic-based approach. Computational results demonstrate the efficiency of the proposed algorithm using an instance based on a real network topology and randomly generated instances.

There are wafer fabrication processes in cluster tools that require wafer revisiting. If a swap strategy is applied to dual-arm cluster tools handling wafer revisiting, a three-wafer periodical process is formed with three wafers completed in each period. Such a period contains three cycles in a revisiting process and three cycles in a nonrevisiting one. Hence, analysis and scheduling of such tools become very complicated. In this paper, a Petri net (PN) model is developed to describe their operations. Based on it, it is found that, if a swap strategy is applied, such tools are always in a transient state. A systematic method is then presented to analyze their performance. With the help of the proposed PN model, this work, for the first time, derives the optimality conditions of three-wafer period scheduling. Industrial application examples are given to show the results.

There are wafer fabrication processes in cluster tools that require wafer revisiting. The adoption of a swap strategy for such tools forms a 3-wafer cyclic (3-WC) period with three wafers completed in each period. It has been shown that, by such a scheduling strategy, the minimal cycle time cannot be reached for some cases. This raises a question of whether there is a scheduling method such that the performance can be improved. To answer this question, a dual-arm cluster tool with wafer revisiting is modeled by a Petri net. Based on the model, the dynamical behavior of the process is analyzed. Then, a 2-wafer cyclic (2-WC) scheduling strategy is revealed for the first time. Cycle time analysis is conducted for the proposed strategy to evaluate its performance. It shows that, for some cases, the performance obtained by a 2-WC schedule is better than that obtained by any existing 3-WC ones. Thus, they can be used to complement each other in scheduling dual-arm cluster tools with wafer revisiting. Illustrative examples are given.

Crude oil transportation is a central logistics operation in petrochemical industry because its cost represents a significant part in the cost of petrochemical products. In this paper, we consider the transportation by tankers or trucks. We show that under some realistic assumptions, this problem can be transformed into a single item lot sizing problem with limited production and inventory capacities. We develop a strongly polynomial dynamic programming algorithm to solve it. The problem of crude oil transportation is very difficult. There are few efficient methods in this domain. In the model considered in this paper, crude oil is directly shipped from a supplier port tonclient ports to satisfy customer demands overTfuture periods. The supplier port disposes a fleet of identical tankers with limited capacity. The inventory capacities of customers are limited and time-varying. The backlogging is admitted. The objective is to find an optimal shipment plan minimizing the total cost over theT-period horizon. When the number of tankers is unlimited and customer demands are independent, shipment plans of different customers become independent. This problem can be considered asnindependent problems. Each of them can be transformed into a single item lot sizing problem with limited production and inventory capacities, where tanker capacity corresponds to production capacity in classical lot sizing models. The main contributions of this paper are: 1) transformation of a transportation planning problem into a lot-sizing problem; 2) an O(T3) algorithm is proposed to solve it; and 3) the results can also be applied to terrestrial transportation with direct deliveries.

This work studies a lane reservation problem in a transportation network. It aims to design task paths and optimally select lanes to be reserved in a transportation network. In this problem, each lane has limited residual capacity, which is the lane capacity that can be used for the tasks causing no delay in this lane. If the residual capacity of a lane is not large enough to allow tasks to use it, the reservation of this lane is necessary. Once reserved, the lane can be used by the tasks only. Therefore, the travel time in this reserved lane is less than that when it is not reserved. Such lane reservation strategy ensures that each task can transport the commodity from its source to destination within a given travel time. However, this reserved lane generates traffic impact on nonreserved lanes. The objective of the problem is to minimize the total impact of all reserved lanes on nonreserved lanes subject to the timely completion of all the concerned tasks. In this paper, two integer linear programming models are, for the first time, formulated. The complexity of the problem is demonstrated to be non-deterministic polynomial-time hard. Then, an optimal algorithm based on the cut-and-solve method is developed for the problem. The computational results of randomly generated network instances up to 120 nodes and 468 arcs show that the proposed algorithm significantly outperforms the direct use of an optimization solver of CPLEX.

Short-term scheduling for crude oil operations is a combinatorial problem and involves extreme detail. Thus, it is very complicated and, up to now, there is no efficient technique and software tool for it. To search for efficient techniques, a two-layer hierarchical solution is proposed for it. At the upper level, one finds a realizable refining schedule to optimize some objectives. At the lower level, a detailed schedule is obtained to realize it. A methodology has been presented to solve the lower level problem from a control perspective by the authors of this paper. In this paper, the upper level problem for finding optimal refining schedules is addressed, and a novel method is proposed based on the results obtained at the lower level. This method solves a linear programming problem to determine the maximal production rate and a transportation problem to optimally assign crude oil types and volume to the distillers. This way, the method is computationally very efficient. An industrial case study is presented to show the application of the proposed method.

There are wafer fabrication processes in cluster tools that require revisiting. It is shown that swapping is efficient in operating a dual-arm cluster tool. For dual-arm cluster tools with wafer revisiting, if a swap strategy is applied, it forms a three wafer periodical process with three wafers completed in each period. Such a period contains three cycles in a revisiting process and another three cycles in non-revisiting process. Hence, analysis and scheduling of dual-arm cluster tools with wafer revisiting become very complicated. In this work, a Petri net model is developed to describe the operations of such tools. Based on it, it is found that if a swap strategy is applied to a dual-arm cluster tool with wafer revisiting, it is always in a transient state. A systematic method is presented to analyze its performance.

For some wafer fabrication processes in cluster tools, e.g., atomic layer deposition (ALD), wafer revisiting is required. Typically, in such processes, wafers need to visit two consecutive processing steps several times. Such a revisiting process can be denoted as (mi, mi + 1)h, where i means the ith-step and miand mi + 1mean the corresponding quantity of the processing modules in i and (i+1)th steps, and h the number of visiting times. This paper conducts a study for scheduling single-arm cluster tools with such a wafer revisiting process. The system is modeled by Petri nets (PNs) to guarantee the feasibility of robot activities. Based on the model, a deadlock avoidance policy is presented. With the control policy, cycle time analysis for the revisiting process is made. With the fact that wafer processing times are much longer than robot movement times in cluster tools, it is shown that, when mi= mi + 1= 1, i.e., each step has only one processing module, the optimal one-wafer cyclic schedule is deterministic and unique, and the minimal cycle time can be calculated by an analytical expression. It is also shown that, when mi= 1 and mi+ 1 = 2 or mi= 2 and mi+ 1 = 1, the optimal one-wafer cyclic schedule can be obtained by finding h deterministic schedules and the one with the least cycle time. A novel analytical method is finally presented to schedule the overall system containing such reentrant wafer flow. This represents a significant advance in single-arm cluster equipment automation.

For short-term scheduling of crude oil operations in refinery, often crude oil residency time constraint and charging-tank-switch-overlap constraint are ignored by mathematical programming models to make the problem solvable. Thus, a schedule obtained by such mathematical programming models is infeasible and cannot be deployed. To solve this problem, this work studies the short-term scheduling problem of crude oil operations in a control theory perspective. The system is modeled by a hybrid Petri net and a short-term schedule is seen as a series of control commands. With this model, schedulability analysis is carried out and schedulability conditions are presented. These conditions can be used as constraints for finding a realizable and optimal refining schedule. Moreover, based on the proposed approach, a detailed schedule can be easily obtained given a realizable refining schedule. In this way, the complexity for the short-term scheduling problem of crude oil operations in refinery is greatly reduced and effective techniques and tools for practical applications can be obtained.

As the traffic on roads becomes increasingly heavy, driving safety has widely become a concern. Thus, an advanced driving-assistance system (ADAS) becomes much more important, because it can improve driving safety. It is composed of a human driver and an automated system called a copilot. To make it effective, they should properly cooperate. Hence, it is very important to define and model their cooperation behavior such that an ADAS can effectively be designed and realized. This paper presents the colored hybrid Petri net (CHPN) model to describe their cooperation behavior. It shows how switch between the driver and the copilot should be done to control the vehicle. The model is shown to be deadlock-free and conflict-free. Therefore, it is useful for ADAS design, analysis, and simulation.

There are varieties of constraints for a short-term scheduling problem of crude oil operations in a refinery. These constraints are difficult to model and complicate the short-term scheduling problem. Among them, oil residency time and high fusion point crude oil transportation constraints are the challenging ones. With high setup cost for high fusion point oil transportation, it is desired that the volume of high fusion point oil can be transported as much as possible by a single setup. This may result in late transportation of other types of crude oil, leading to the violation of crude oil residency time constraint. These constraints are ignored by existing methods in the literature. To solve this problem, this paper studies the problem in a control theory perspective by viewing an operation decision in the schedule as a control. With this idea, the system is modeled by a hybrid Petri net. With this model and tank grouping strategy, schedulability analysis is carried out and schedulability conditions are presented with tank charging and discharging costs being taken into consideration. These conditions are necessary for determining a refining schedule and can be used to check whether a target-refining schedule is realizable or not. If so, a feasible detailed schedule for the refining schedule can be easily obtained by creating the operation decisions one by one.

Because of the complexity of a short-term scheduling problem for crude oil operations, some constraints are ignored in modeling the system by the existing approaches, leading to an infeasible solution. To avoid this, the short-term scheduling problem can be studied in control theory perspective by viewing an operation decision in the schedule as a control. With this idea, this paper conducts the schedulability analysis for systems with two and more than two distillers, and the schedulability conditions are presented with the help of Petri net theory. It shows that the number of charging tanks and their capacity, the amount of crude oil of different types in the charging tanks, the oil transportation rate of the pipeline, and the production rate of the system affect the safeness of the system. It also presents the conditions under which the system can reach its maximal production rate. With the safeness conditions and proved results presented in this paper, if a refining schedule is realizable, a feasible detailed schedule for the refining schedule can be easily obtained by creating the operation decisions for the schedule one by one. In the schedule obtained, the starting time of each operation decision can be at any continuous time point, and the schedule is certainly feasible, which overcomes the difficulty faced by techniques that are based on mathematical programming methods.

This paper considers the infinite horizon inventory routing problem for one-warehouse multi-retailer distribution systems. We focus on developing an analytic approach for evaluating the effectiveness of direct shipping strategy where each vehicle serves only one retailer in one delivery at its optimal replenishment rate. Explicit formula is obtained in terms of a few of easily measurable parameters. The formula allows the effectiveness of direct shipping strategy to be evaluated quickly using even a hand calculator. We demonstrate that the effectiveness of direct shipping is at least the square root of the smallest utilization ratio of vehicle capacity. This implies that direct shipping is 100% (respectively 94.86%) effective whenever the smallest utilization ratio is 100% (respectively 90%). This insight can help a firm answer questions such as: under what conditions does direct shipping perform well, and why? How well does direct shipping perform in a specific situation.

Because of various constraints, the short-term scheduling of crude oil operations in refinery is very complicated. So far, there is no effective technique and tool. To solve this problem, this paper models the system by a hybrid Petri net and a short-term schedule is seen as a series of control commands. With this model, schedulability analysis of systems with a single distiller is conducted and schedulability conditions are presented. These conditions can be used as constraints for finding a realizable and optimal refining schedule. Moreover, based on the approach presented in this paper, a detailed schedule can be easily obtained for a realizable refining schedule.

In discrete manufacturing, a just-in-time schedule is pursued so as to respond better to the market. It is also required in oil refinery. However, the existing techniques for short-term scheduling in oil refinery are based on the push production mode. This paper addresses the short-term scheduling problem for crude oil operations in a pull production way. A target refining schedule resulting from production planning is given as a constraint to make an executable schedule. The system is modeled by a timed hybrid Petri net. This model is structurally simple and can describe the dynamic behavior and all the constraints of the system without any difficulty. Based on the model, an efficient heuristic algorithm is proposed to test the realizability of a target refining schedule. If it is realizable, a feasible short-term schedule realizing it is created. A real-life industrial case study is presented to show the industrial application of the proposed method.

This paper addresses a real-life lot-sizing problem which can be considered a single-item dynamic lot-sizing problem with bounded inventory. The particularity is that the demand of a period can be entirely or partially outsourced with an outsourcing cost. The goal is to minimize the total cost of production, setup, inventory holding, and outsourcing. The cost functions are linear but time-varying. We assume that the unit production cost is constant or nonincreasing over time. The problem is shown to be solvable in a strongly polynomial time with a dynamic-programming approach. The proposed algorithm can solve problems of sizes of up to 400 periods in less than 2 ms on a 1.4-GHz Pentium IV processor.

A short-term schedule for oil refinery should arrange all the activities in every detail for the whole scheduling horizon, leading to a complex problem. There lacks efficient techniques and software tools for its solution applicable to industrial oil refinery. Considering that the feasibility of a schedule is essential, this paper studies the feasibility problem from a control perspective. A short-term schedule is composed of a series of operation decisions (ODs), each of which can be seen as a control. When an OD is executed, it transfers the system from one state to another. To guarantee the schedule feasibility, the system should be always be kept in safe states. The system is modeled by a Petri net model that is under control of the ODs. With this model, schedulability conditions for a system with one distiller are presented. These conditions reveal the relationship among the number of charging tanks, the oil transportation flow rate of the pipeline, and the production rate. The conditions are presented in a constructive way. Based on the conditions, when a realizable refining schedule is verified, a detailed short-term schedule is created for practical use.

We consider the inventory-routing problem for a three-level distribution system consisting of a single outside vendor, a single warehouse and many geographically dispersed retailers. Each retailer faces external demands for a single item which arise at a deterministic, retailer specific rate. Inventory holding cost is charged at both the warehouse and the retailers. All shipments are delivered by a fleet of homogeneous vehicles of limited capacity. We develop a lower bound on the long run average cost over any feasible policies. We use this lower bound to show that an effective strategy, in which all shipments are delivered from the vendor to the retailers not to pass the warehouse, is at least radic2 asymptotic optimal, and with a high probability, the strategy has a higher asymptotic optimality than the strategy to pass the warehouse. Particularly, if the probability distribution of the retailer demand rates allows for perfect packing, then the strategy is almost surely 100% asymptotic optimal and better than the strategy to pass the warehouse. Our results also show that the strategy not to pass the warehouse as well as the strategy to pass the warehouse would not work very well in three-level distribution systems with limited number of retailers or with many retailers but the perfect packing ratio allowed by the retailer demand rates is small. Further we provide a numerical example to show that in some conditions the strategy to pass the warehouse is better than the strategy not to pass the warehouse. We then can conclude that a hybrid strategy, i.e., combing the strategy not to pass the warehouse with the strategy to pass the warehouse, should be used in three-level distribution systems with limited number of retailers or with many retailers but the perfect packing ratio allowed by the retailer demand rates is small.

The feasibility of a schedule is essential to the operation of a complex system involving both discrete and continuous processes. This paper studies the short-term scheduling problem for crude oil operations in a control theory perspective. A short-term schedule is composed of a series of operation decisions, each of which can be seen as control. Their execution transfers the system from one state to another. To guarantee a schedule’s feasibility, the system must always be kept in safe states. It is modeled by a Petri net that is under the control of operation decisions. With this model, safeness or schedulability conditions are presented. They reveal the relationship among the number of charging tanks, oil transportation flow rate of the pipeline, and production rate. Based on them, if a refining schedule is found schedulable, a detailed short-term schedule is created as well.

This paper addresses a real-life single-item dynamic lot sizing problem arising in a refinery for crude oil procurement. It can be considered as a lot sizing problem with bounded inventory. We consider two managerial policies. With one policy, a part of the demand of a period can be backlogged and with the other, a part of the demand of a period can be outsourced. We define actuated inventory bounds and show that any bounded inventory lot sizing model can be transformed into an equivalent model with actuated inventory bounds. The concept of actuated inventory bounds significantly contributes to the complexity reduction. In the studied models, the production capacity can be assumed to be unlimited and the production cost functions to be linear but with fixed charges. The results can be easily extended to piecewise linear concave production cost functions. The goal is to minimize the total cost of production, inventory holding and backlogging, or outsourcing. We show that the backlogging model can be solved in O(T2) time with general concave inventory holding and backlogging cost functions where T is the number of periods in the planning horizon. The complexity is reduced to O(T) when the inventory/backlogging cost functions are linear and there is no speculative motives to hold either inventory or backlogging. When the outsourcing levels are unbounded, we show that the outsourcing model can be transformed into an inventory/backlogging model. As a consequence, the problem can be solved in O(T2) time, if the outsourcing cost functions are linear with fixed charges even if the inventory holding cost functions are general concave functions. When the outsourcing level of a period is bounded from above by the demand of the period, which is the case in many application areas, we show that the outsourcing model can be solved in O(T2logT) time if the inventory holding and the outsourcing cost functions are linear. Note to Practitioners-This paper considers dynamic lot-sizing models with bounded inventory and outsourcing or backlogging decisions. Based on the forecasted requirements of a given item for each period of the planning horizon, the problem consists of determining the quantity to be produced inhouse or to be ordered from a supplier and the quantity to be outsourced in each period to minimize a total cost over the considered planning horizon, composed of the production or purchasing cost, inventory holding cost, and the backlogging cost or the outsourcing cost. These problems initially come from real-life crude oil procurement and often arise in many companies. In this paper, we consider two models. In one model, backlogging is allowed with a backlogging penalty while there is no possibility of outsourcing. In the other model, all of the customer requirements are satisfied in time (i.e., without backlogging) but outsourcing is possible. For each model, we develop an algorithm to find an optimal solution. The computation time of these algorithms can be bounded by a one or two degree polynom of the number of periods in the planning horizon, which means that the computation time required to find an optimal solution is very short

In practice, the short-term scheduling job of oil refinery processes is still done manually by planners, because of the lack of such tools. This paper briefly reviews the theoretic research advancement in this field. It shows that although some progress has been made, the techniques obtained are not applicable in practice. Thus, the future research trends in this field should focus on methods that can bridge the gap between theory and applications. Based on the review, this paper concludes that it may be helpful if the problem is studied in a viewpoint of control theory and hence, solved by combining enumeration and heuristic instead of using mathematical programming formulations.

In this paper we consider a dynamic lot sizing model with mixed backlogging and outsourcing and bounded inventory, in which outsourcing may occur in a period even if the inventory level at that period is positive. The production cost may include setup cost and the production level is unlimited. The holding, backlogging and outsourcing cost functions are linear. Furthermore, backlogging level at each period is limited, and outsourcing level at each period cannot exceed the demand of that period. The goal is to minimize the total cost of production, inventory holding/backlogging and outsourcing. We show that this problem can be solved in O(T4log T) time where T is the length of the planning horizon. Finally, the proposed algorithm is implemented in C++ and evaluated on a large variety of instances generated randomly.

In discrete manufacturing, just in time schedule is pursued so as to better respond to the market. In the practice, it is also required to do so in oil refinery. However, the existing scheduling techniques for finding short-term scheduling in oil refinery are based on push production mode. This paper addresses the short-term scheduling for crude oil operations in a pull production way, or a target refining schedule derived from production planning is given as a constraint for schedule making. The system is modeled by Petri net, and based on the model an efficient heuristics is proposed to test the readability of the target refining schedule. If it is realizable, a feasible short-term schedule for crude oil operations that realize the target schedule is created. A case study is presented to show the application of the heuristics.

Batch deterministic and stochastic Petri nets are introduced as a tool for modeling and performance evaluation of supply chains. The new model is developed by enhancing deterministic and stochastic Petri nets (DSPNs) with batch places and batch tokens. By incorporating stochastic Petri nets (SPNs) with the batch features, inhibitor arcs, and marking-dependent weights, operational policies of supply chains such as inventory policies can be easily described in the model. Methods for structural and performance analysis of the model are developed by extending existing ones for DSPNs. As applications, an inventory system and an industrial supply chain are modeled and their performances are evaluated analytically and by simulation, respectively, using this BSPN model. The applications demonstrate that our model and associated methods can solve some important supply chain modeling and analysis issues. Note to Practitioners-This paper was motivated by the problem of performance analysis and optimization of supply chains but it also applies to other discrete event systems where materials are processed in finite discrete quantities (batches) and operations are performed in a batch way because of batch inputs and/or in order to take advantages of the economies of scale. Existing Petri net modeling and analysis tools for such systems ignore their batch features, making their modeling complicated. This paper suggests a new model called batch deterministic and stochastic Petri nets (BDSPNs) by enhancing deterministic and stochastic Petri nets with batch places and batch tokens. Methods for structural and performance analysis of the model are developed. We then show how an inventory system and a real-life supply chain can be modeled and their performances can be evaluated analytically and by simulation respectively based on the model. The model and associated analysis methods therefore provide a promising tool for modeling and performance evaluation of supply chains.

Batch deterministic and stochastic Petri nets are developed as a new tool for modeling and performance evaluation of supply chain. It is derived by enhancing deterministic and stochastic Petri nets. with batch places and batch tokens. Batch tokens, which have sizes and reside in batch places, are used to describe the information flow of a supply chain, while discrete tokens residing in discrete places are used to describe the material flow and the financial flow. By incorporating stochastic Petri nets with the batch features, inhibitor arcs, and marking-dependent weights, operational policies of a supply chain can be easily described in the model. A real-life supply chain is modeled by applying this tool and its performance is evaluated and optimized by simulation.

Proposes an exact algorithm for the multicyclic schedules of hoist moves in a printed circuit board (PCB) electroplating facility, where exactly r(r>1) parts enter and r parts leave the production line during each cycle, and the processing time at each production stage is a given constant. The multicyclic scheduling problem is transformed into enumeration of intervals for linear functions of decision variables. This enumeration is accomplished with a branch and bound procedure. At each node of the search tree, by solving a linear programming problem (LPP), either the corresponding partial solution is proved to be unable to lead to a feasible solution, or a lower bound is computed. Due to its particular structure, this LPP is equivalent to a cycle time evaluation problem in a bivalued graph which can be solved efficiently. The proposed algorithm is polynomial in the number of tanks for a fixed r, but exponential if r is arbitrary. Computational experience with both benchmark and randomly generated test instances is presented.

This paper exploits the potential of siphons for the analysis of Petri nets, It generalizes the well-known Commoner condition and is based on the notion of potential deadlocks which are siphons that eventually become empty. A linear programming based sufficient condition under which a siphon is not a potential deadlock is obtained. Based on the new sufficient condition, a mathematical programming approach and a mixed-integer programming approach are proposed for checking general Petri nets and structurally bounded Petri nets respectively without explicitly generating siphons. Stronger results are obtained for asymmetric choice nets and augmented marked graphs. In particular, we show that an asymmetric choice net is live iff it is potential-deadlock-free and an augmented marked graph is live and reversible iff it is potential-deadlock-free.