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.

A Hybrid Estimation of Distribution Algorithm for Unrelated Parallel Machine Scheduling with Sequence-Dependent Setup Times

A hybrid estimation of distribution algorithm(EDA)with iterated greedy(IG) search(EDA-IG) is proposed for solving the unrelated parallel machine scheduling problem with sequence-dependent setup times(UPMSP-SDST). For makespan criterion, some properties about neighborhood search operators to avoid invalid search are derived. A probability model based on neighbor relations of jobs is built in the EDA-based exploration phase to generate new solutions by sampling the promising search region. Two types of deconstruction and reconstruction as well as an IG search are designed in the IG-based exploitation phase.Computational complexity of the algorithm is analyzed, and the effect of parameters is investigated by using the Taguchi method of design-of-experiment. Numerical tests on 1640 benchmark instances are carried out. The results and comparisons demonstrate the effectiveness of the EDA-IG. Especially, the bestknown solutions of 531 instances are updated. In addition, the effectiveness of the properties is also demonstrated by numerical comparisons.

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.

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%.

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.