Since 2000, the field of machine scheduling—an integral part of computer science and operations research—has seen significant advancements. This paper explores the dynamic progression of machine ...scheduling, offering a detailed overview of its past advancements, current practices, and future directions. Anchoring the research in robust data analysis and statistical methodologies, the paper reveals the subtle yet impactful changes that have characterized the field in the last two decades. It examines the prominence of various scheduling problems, identifies leading research journals, and highlights international contributions and collaborations, thereby offering a thorough guide to the machine scheduling ecosystem. The study delves into specific problem characteristics and assesses performance criteria and solution methods to provide an in-depth view of the field's multifaceted nature. Ultimately, this paper captures the essence of machine scheduling's evolution and suggests new paths for exploration. The insights gained contribute significantly to academic discussions and equip practitioners with a comprehensive understanding of the dynamic landscape of machine scheduling.
With the developments and applications of the new information technologies, such as cloud computing, Internet of Things, big data, and artificial intelligence, a smart manufacturing era is coming. At ...the same time, various national manufacturing development strategies have been put forward, such as Industry 4.0 , Industrial Internet , manufacturing based on Cyber-Physical System , and Made in China 2025 . However, one of specific challenges to achieve smart manufacturing with these strategies is how to converge the manufacturing physical world and the virtual world, so as to realize a series of smart operations in the manufacturing process, including smart interconnection, smart interaction, smart control and management, etc. In this context, as a basic unit of manufacturing, shop-floor is required to reach the interaction and convergence between physical and virtual spaces, which is not only the imperative demand of smart manufacturing, but also the evolving trend of itself. Accordingly, a novel concept of digital twin shop-floor (DTS) based on digital twin is explored and its four key components are discussed, including physical shop-floor, virtual shop-floor, shop-floor service system, and shop-floor digital twin data. What is more, the operation mechanisms and implementing methods for DTS are studied and key technologies as well as challenges ahead are investigated, respectively.
The first comprehensive survey paper on scheduling problems with separate setup times or costs was conducted by Allahverdi, A., Gupta, J.N.D., Aldowaisan, T., 1999. A review of scheduling research ...involving setup considerations. OMEGA The International Journal of Management Sciences 27, 219–239, who reviewed the literature since the mid-1960s. Since the appearance of that survey paper, there has been an increasing interest in scheduling problems with setup times (costs) with an average of more than 40 papers per year being added to the literature. The objective of this paper is to provide an extensive review of the scheduling literature on models with setup times (costs) from then to date covering more than 300 papers. Given that so many papers have appeared in a short time, there are cases where different researchers addressed the same problem independently, and sometimes by using even the same technique, e.g., genetic algorithm. Throughout the paper we identify such areas where independently developed techniques need to be compared. The paper classifies scheduling problems into those with batching and non-batching considerations, and with sequence-independent and sequence-dependent setup times. It further categorizes the literature according to shop environments, including single-machine, parallel machines, flow shop, no-wait flow shop, flexible flow shop, job shop, open shop, and others.
Designing effective dispatching rules for production systems is a difficult and time-consuming task if it is done manually. In the last decade, the growth of computing power, advanced machine ...learning, and optimisation techniques has made the automated design of dispatching rules possible and automatically discovered rules are competitive or outperform existing rules developed by researchers. Genetic programming is one of the most popular approaches to discovering dispatching rules in the literature, especially for complex production systems. However, the large heuristic search space may restrict genetic programming from finding near optimal dispatching rules. This article develops a new hybrid genetic programming algorithm for dynamic job shop scheduling based on a new representation, a new local search heuristic, and efficient fitness evaluators. Experiments show that the new method is effective regarding the quality of evolved rules. Moreover, evolved rules are also significantly smaller and contain more relevant attributes.
Flexible job shop scheduling problem (FJSP) has been extensively considered; however, multiobjective FJSP with energy consumption threshold is seldom investigated, the goal of which is to minimize ...makespan and total tardiness under the constraint that total energy consumption does not exceed a given threshold. Energy constraint is not always met and the threshold is difficult to be decided in advance. These features make it more difficult to solve the problem. In this paper, a two-phase meta-heuristic (TPM) based on imperialist competitive algorithm (ICA) and variable neighborhood search (VNS) is proposed. In the first phase, the problem is converted into FJSP with makespan, total tardiness and total energy consumption and the new FJSP is solved by an ICA, which uses some new methods to build initial empires and do imperialist competition. In the second phase, new strategies are provided for comparing solutions and updating the nondominated set of the first phase and a VNS is used for the original problem. The current solution of VNS is periodically replaced with member of the set <inline-formula> <tex-math notation="LaTeX">\Omega </tex-math></inline-formula> to improve solution quality. An energy consumption threshold is obtained by optimization. Extensive experiments are conducted to test the performance of TPM finally. The computational results show that TPM is a very competitive algorithm for the considered FJSP.
Flexible job shop scheduling problems ( FJSP ) have received much attention from academia and industry for many years. Due to their exponential complexity, swarm intelligence ( SI ...) and evolutionary algorithms ( EA ) are developed, employed and improved for solving them. More than 60% of the publications are related to SI and EA. This paper intents to give a comprehensive literature review of SI and EA for solving FJSP. First, the mathematical model of FJSP is presented and the constraints in applications are summarized. Then, the encoding and decoding strategies for connecting the problem and algorithms are reviewed. The strategies for initializing algorithms? population and local search operators for improving convergence performance are summarized. Next, one classical hybrid genetic algorithm ( GA ) and one newest imperialist competitive algorithm ( ICA ) with variables neighborhood search ( VNS ) for solving FJSP are presented. Finally, we summarize, discus and analyze the status of SI and EA for solving FJSP and give insight into future research directions.
•The primary aspects of JSSP types and models are presented.•The general representation and overview of JSSP models are provide.•State of the art on JSSP types and models is reviewed.•Some ...under-developed research topics for further research are suggested.
Job shop scheduling problem (JSSP) is a thriving area of scheduling research, which has been concerned and studied widely by scholars in engineering and academic fields. This paper provides a comprehensive review on the types and models of JSSP, to the best of our knowledge, there has not been a review paper on this aspect up to now. The main purpose of this review is to help researchers and scholars outlining an overview of existing JSSP models and exploring more valuable research directions. We first analyze and classify the entities and their attributes, assumptions, basic subtypes, and measures of performance of JSSP based on the researches from mid-1960s to 2020s. The general representation and overview of JSSP models are also presented. Then, some extensive statistics and analysis are conducted on 297 published papers in 72 journals ranging between 2016 and early 2021. Finally, some hot research aspects of JSSP models are reviewed in detail and some promising research directions are provided.
We propose a framework to learn to schedule a job-shop problem (JSSP) using a graph neural network (GNN) and reinforcement learning (RL). We formulate the scheduling process of JSSP as a sequential ...decision-making problem with graph representation of the state to consider the structure of JSSP. In solving the formulated problem, the proposed framework employs a GNN to learn that node features that embed the spatial structure of the JSSP represented as a graph (representation learning) and derive the optimum scheduling policy that maps the embedded node features to the best scheduling action (policy learning). We employ Proximal Policy Optimization (PPO) based RL strategy to train these two modules in an end-to-end fashion. We empirically demonstrate that the GNN scheduler, due to its superb generalization capability, outperforms practically favoured dispatching rules and RL-based schedulers on various benchmark JSSP. We also confirmed that the proposed framework learns a transferable scheduling policy that can be employed to schedule a completely new JSSP (in terms of size and parameters) without further training.
Extended technical precedence constraints (ETPC) in dynamic job shop scheduling problem (DJSP) are the precedence constraints existing between different jobs instead of the conventional technical ...precedence constraints existing in the operations of the same job. This paper presents the mathematical programming model of the DJSP with ETPC to minimize the mean weighted tardiness of the jobs. The mathematical model contributes to the solution and modelling of the DJSP with ETPC and it is used to solve small-sized problems to optimality. To solve industry-sized problems, a constructive heuristic called the dispatching rule (DR) is employed. This paper investigates the use of genetic programming (GP) as a hyper-heuristic in the automated generation of the problem-specific DRs for solving the problem under consideration. The genetic programming-based hyper heuristic (GPHH) approach constructs the DRs which are learned from the training instances and then verified on the test instances by the simulation experiments. To enhance the efficiency of the approach when evolving effective DRs to solve the problem, the approach is improved with strategies which consist of a problem-specific attribute selection for GP and a threshold condition mechanism for fitness evaluation. The simulation results verify the effectiveness and efficiency of the evolved DRs to the problem under consideration by comparing against the existing classical DRs. The statistical analysis of the simulation results shows that the evolved DRs outperform the selected benchmark DRs on the problem under study. The sensitivity analysis also shows that the DRs generated by the GPHH approach are robust under different scheduling performance measures. Moreover, the effects of the model parameters, including the percentage of jobs with ETPC and the machine utilization, on the performance of the DRs are investigated.
•Effective heuristic for the parallel blocking flow shop problem with setup times.•Performance evaluation of different neighbourhood structures and local searches.•Performance evaluation of different ...initial solution procedures.•The best performing constructive method does not lead to obtaining better solutions.•The level of setup times has slightly influence on the behavior of heuristics.
This paper deals with the problem of scheduling jobs in a parallel flow shop configuration under the blocking constraint, in which the setup time of machines depends not only on the job to be processed but also on the previously processed one, i.e., there are sequence-dependent setup times. The performance analysis of several iterated greedy algorithms with different initial solution procedures and local searches lets us define an efficient algorithm to minimize the maximum job completion time. Moreover, the computational evaluation showed the efficiency of searching in different neighborhood structures and noted the significant influence of the initial solution. However, contrary to other scheduling problems, starting with a high quality solution does not guarantee better performance of the algorithm.
PDF
