Hybrid Flow Shop with Setup Times Scheduling Problem

The two-stage hybridflow shop problem under setup times is addressed in this paper.This problem is NP-Hard.on the other hand,the studied problem is modeling different real-life applications especially in manufacturing and high performance-computing.Tackling this kind of problem requires the development of adapted algorithms.In this context,a metaheuristic using the genetic algorithm and three heuristics are proposed in this paper.These approximate solutions are using the optimal solution of the parallel machines under release and delivery times.Indeed,these solutions are iterative procedures focusing each time on a particular stage where a parallel machines problem is called to be solved.The general solution is then a concatenation of all the solutions in each stage.In addition,three lower bounds based on the relaxation method are provided.These lower bounds present a means to evaluate the efficiency of the developed algorithms throughout the measurement of the relative gap.An experimental result is discussed to evaluate the performance of the developed algorithms.In total,8960 instances are implemented and tested to show the results given by the proposed lower bounds and heuristics.Several indicators are given to compare between algorithms.The results illustrated in this paper show the performance of the developed algorithms in terms of gap and running time.

A Linear Programming Approach for Parallel Cell Scheduling with Sequence-Dependent Setup Times

In this study, we consider the problem of scheduling a set of jobs with sequence-dependent setup times on a set of parallel production cells. The objective of this study is to minimize the total completion time. We note that total customer demands for each type should be satisfied, and total required production time in each cell cannot exceed the capacity of the cell. This problem is formulated as an integer programming model and an interface is designed to provide integrity between data and software. Mathematical model is tested by both randomly generated data set and real-world data set from a factory that produce automotive components. As a result of this study, the solution which gives the best alternative production schedule is obtained.

Identical Machine Scheduling Problem with Sequence-Dependent Setup Times: MILP Formulations Computational Study

This work aims to give a systematic construction of the two families of mixed-integer-linear-programming (MILP) formulations, which are graph- based and sequence-based, of the well-known scheduling problem. Two upper bounds of job completion times are introduced. A numerical test result analysis is conducted with a two-fold objective 1) testing the performance of each solving methods, and 2) identifying and analyzing the tractability of an instance according to the instance structure in terms of the number of machines, of the jobs setup time lengths and of the jobs release date distribution over the scheduling horizon.

AN IMPROVED BRANCH-AND-BOUND ALGORITHM TO MINIMIZE THE WEIGHTED FLOWTIME ON IDENTICAL PARALLEL MACHINES WITH FAMILY SETUP TIMES

This article investigates identical parallel machines scheduling with family setup times. The objective function being the weighted sum of completion times, the problem is known to be strongly NP-hard. We propose a constructive heuristic algorithm and three complementary lower bounds. Two of these bounds proceed by elimination of setup times or by distributing each of them to jobs of the corresponding family, while the third one is based on a lagrangian relaxation. The bounds and the heuristic are incorporated into a branch-and-bound algorithm. Experimental results obtained outperform those of the methods presented in previous works, in term of size of solved problems.

On a BMAP/G/1 G-queue with Setup Times and Multiple Vacations

In this paper, we consider a BMAP/G/1 G-queue with setup times and multiple vacations. Arrivals of positive customers and negative customers follow a batch Markovian arrival process （BMAP） and Markovian arrival process （MAP） respectively. The arrival of a negative customer removes all the customers in the system when the server is working. The server leaves for a vacation as soon as the system empties and is allowed to take repeated （multiple） vacations. By using the supplementary variables method and the censoring technique, we obtain the queue length distributions. We also obtain the mean of the busy period based on the renewal theory.

Scheduling a three-machine no-wait flowshop with separated setup time

In many practical flowshop production environments, there is no intermediate storage space available to keep partially completed jobs between any two machines. The workflow has to be continuous, implying that the no-wait conditions must be abided, which is typical in steel and plastic production. We discuss the three-machine no-wait flowshop scheduling problem where the setup times are considered as separated from processing times and sequence independent. The scheduling goal is to minimize the total flowtime. An optimal property and two heuristic algorithms for this problem are proposed. Evaluated over a large number of problems, the proposed heuristics are found that they can yield good solutions effectively with low computational complexity, and have more obvious advantage for the large size problem compared with the existing one.

Performance Assessment and Configuration Analysis in the Study of SCADA System (Supervisory Control and Data Acquisition)

Queuing models are used to assess the functionality and aesthetics of SCADA systems for supervisory control and data collection.Here,the main emphasis is on how the queuing theory can be used in the system’s design and analysis.The analysis’s findings indicate that by using queuing models,cost-performance ratios close to the ideal might be attained.This article discusses a novel methodology for evaluating the service-oriented survivability of SCADA systems.In order to evaluate the state of service performance and the system’s overall resilience,the framework applies queuing theory to an analytical model.As a result,the SCADA process is translated using the M^(X)/G/1 queuing model,and the queueing theory is used to evaluate this design’s strategy.The supplemental variable technique solves the queuing problem that comes with the subsequent results.The queue size,server idle time,utilization,and probabilistic generating factors of the distinct operating strategies are estimated.Notable examples were examined via numerical analysis using mathematical software.Because it is used frequently and uses a statistical demarcation method,this tactic is completely acceptable.The graphical representation of this perspective offers a thorough analysis of the alleged limits.

Neighborhood Combination Search for Single-Machine Scheduling with Sequence-Dependent Setup Time

In a local search algorithm,one of its most important features is the definition of its neighborhood which is crucial to the algorithm's performance.In this paper,we present an analysis of neighborhood combination search for solv-ing the single-machine scheduling problem with sequence-dependent setup time with the objective of minimizing total weighted tardiness(SMSWT).First,We propose a new neighborhood structure named Block Swap(B1)which can be con-sidered as an extension of the previously widely used Block Move(B2)neighborhood,and a fast incremental evaluation technique to enhance its evaluation efficiency.Second,based on the Block Swap and Block Move neighborhoods,we present two kinds of neighborhood structures:neighborhood union(denoted by B1UB2)and token-ring search(denoted by B1→B2),both of which are combinations of B1 and B2.Third,we incorporate the neighborhood union and token-ring search into two representative metaheuristic algorithms:the Iterated Local Search Algorithm(ILSnew)and the Hybrid Evolutionary Algorithm(HEA_(new))to investigate the performance of the neighborhood union and token-ring search.Exten-sive experiments show the competitiveness of the token-ring search combination mechanism of the two neighborhoods.Tested on the 120 public benchmark instances,our HEA_(new)has a highly competitive performance in solution quality and computational time compared with both the exact algorithms and recent metaheuristics.We have also tested the HEA,new algorithm with the selected neighborhood combination search to deal with the 64 public benchmark instances of the single-machine scheduling problem with sequence-dependent setup time.HEAnew is able to match the optimal or the best known results for all the 64 instances.In particular,the computational time for reaching the best well-known results for five chal-lenging instances is reduced by at least 61.25%.

Two-Stage Adaptive Memetic Algorithm with Surprisingly Popular Mechanism for Energy-Aware Distributed Hybrid Flow Shop Scheduling Problem with Sequence-Dependent Setup Time

This paper considers the impact of setup time in production scheduling and proposes energy-aware distributed hybrid flow shop scheduling problem with sequence-dependent setup time(EADHFSP-ST)that simultaneously optimizes the makespan and the energy consumption.We develop a mixed integer linear programming model to describe this problem and present a two-stage adaptive memetic algorithm(TAMA)with a surprisingly popular mechanism.First,a hybrid initialization strategy is designed based on the two optimization objectives to ensure the convergence and diversity of solutions.Second,multiple population co-evolutionary approaches are proposed for global search to escape from traditional cross-randomization and to balance exploration and exploitation.Third,considering that the memetic algorithm(MA)framework is less efficient due to the randomness in the selection of local search operators,TAMA is proposed to balance the local and global searches.The first stage accumulates more experience for updating the surprisingly popular algorithm(SPA)model to guide the second stage operator selection and ensures population convergence.The second stage gets rid of local optimization and designs an elite archive to ensure population diversity.Fourth,five problem-specific operators are designed,and non-critical path deceleration and right-shift strategies are designed for energy efficiency.Finally,to evaluate the performance of the proposed algorithm,multiple experiments are performed on a benchmark with 45 instances.The experimental results show that the proposed TAMA can solve the problem effectively.

Scheduling Multiple Orders per Job with Multiple Constraints on Identical Parallel Machines

With a comprehensive consideration of multiple product types, past-sequence-dependent （ p-s-d ） setup times, and deterioration effects constraints in processes of wafer fabrication systems, a novel scheduling model of multiple orders per job（MOJ） on identical parallel machines was developed and an immune genetic algorithm（IGA） was applied to solving the scheduling problem. A scheduling problem domain was described. A non-linear mathematical programming model was also set up with an objective function of minimizing total weighted earliness-tardlness penalties of the system. On the basis of the mathematical model, IGA was put forward. Based on the genetic algorithm （GA）, the proposed algorithm （IGA） can generate feasible solutions and ensure the diversity of antibodies. In the process of immunization programming, to guarantee the algorithm＇s convergence performance, the modified rule of apparent tardiness cost with setups （ATCS） was presented. Finally, simulation experiments were designed, and the results indicated that the algorithm had good adaptability when the values of the constraints＇ characteristic parameters were changed and it verified the validity of the algorithm.

A Penalty Groups-Assisted Iterated Greedy Integrating Idle Time Insertion:Solving the Hybrid Flow Shop Group Scheduling with Delivery Time Windows

The hybrid flow shop group scheduling problem(HFGSP)with the delivery time windows has been widely studied owing to its better flexibility and suitability for the current just-in-time production mode.However,there are several unresolved challenges in problem modeling and algorithmic design tailored for HFGSP.In our study,we place emphasis on the constraint of timeliness.Therefore,this paper first constructs a mixed integer linear programming model of HFGSP with sequence-dependent setup time and delivery time windows to minimize the total weighted earliness and tardiness(TWET).Then a penalty groups-assisted iterated greedy integrating idle time insertion(PG IG ITI)is proposed to solve the above problem.In the PG IG ITI,a double decoding strategy is proposed based on the earliest available machine rule and the idle time insertion rule to calculate the TWET value.Subsequently,to reduce the amount of computation,a skip-based destruction and reconstruction strategy is designed,and a penalty groups-assisted local search is proposed to further improve the quality of the solution by disturbing the penalized groups,i.e.,early and tardy groups.Finally,through comprehensive statistical experiments on 270 test instances,the results prove that the proposed algorithm is effective compared to four state-of-the-art algorithms.

THE MIMIc QUEUE WITH (e, d) SETUP TIME

The authors present a new queueing model with （e, d） setup time. Using the quasi-birth-and-death process and matrix-geometric method, the authors obtain the stationary distribution of queue length and the LST of waiting time of a customer in the system. Furthermore, the conditional stochastic decomposition results of queue length and waiting time are given.

Modeling and Scheduling Optimization for Bulk Ore Blending Process

A new scheduling model for the bulk ore blending process in iron-making industry is presented , by converting the process into an assembly flow shop scheduling problem with sequence-depended setup time and limited intermediate buffer , and it facilitates the scheduling optimization for this process.To find out the optimal solution of the scheduling problem , an improved genetic algorithm hybridized with problem knowledge-based heuristics is also proposed , which provides high-quality initial solutions and fast searching speed.The efficiency of the algorithm is verified by the computational experiments.