Sage Journals: Discover world-class research

Abstract

The article deals with a formal approach to solving manufacturing problem with defects removal and presents the application of this approach to flow-shop system with defects. The defects are detected during quality control and thus they are unexpected events. Moreover, a job processing time is not predetermined, and it may contain the unknown time needed to repair. Therefore, stochastic uncertainties are considered, but in addition, we model the process of decision making. The algebraic-logical meta-model methodology constitutes the basis for our approach. A hybrid algorithm for constructing a solution based on the process simulation using special local optimizing task and algebraic-logical models switching when defect detection occurs is presented. In particular, the following elements of the presented approach are shown: disturbances type analyzing, definition of switching states set, definition of subproblems, algebraic-logical meta-models creating for all subproblems, switching types determining, determination of the switching rules, the switching function, and components of special local criterion definition. The article shows results of computer experiments.

Keywords

Simulation discrete optimization discrete scheduling problems flow-shop problem unexpected event decision support system

Introduction

The article presents formal approach to solving manufacturing problem with defects removal, especially flow-shop problem. The defects are detected during quality control and thus they are unexpected events. Moreover, job processing time is not predetermined. In the presence of quality defect, it contains the unknown time needed to repair because it depends on the size of defect, and in each case it may be different for the same job. Therefore, stochastic uncertainties are considered, but in addition, we model the process of decision making.

Moreover, stochastic uncertainties are considered, but in addition, we would like to model decision-making process connected with assignment of the tasks with defect to repair. Thus, it is not stochastic scheduling, because not only processing time is stochastic but also we deal with additional operation of defect repairing (only when the defect is detected). It should be noted that our approach takes account of the stochastic uncertainties as well as allows to model the process of decision making. Moreover, the application of our approach allows to optimize the time of machine usage and in this way to save resources and energy with a consequent cost and emissions of greenhouse gas reduction.

We consider flow-shop manufacturing problem in which there are quality control for the defects detection, removal of the manufacturing quality defects on an additional repairing machine, and job re-treatment in part or all technological routes. Moreover, deadline is determined for some or all jobs. The execution orders in powder coating plant are an example of the problem that belongs to considered class of problems. Manufacturing process of painting details is as follows. There are five workstations: chemical bath, dryer, powder coating booth, curing oven, and packing. Each detail passes through the all workstations step by step. Checking the quality of painting execution is after heat treatment in curing oven. As a result of quality control, the defective elements should be repaired. For this purpose, additional operation should be done, that is, powder coating must be removed. Therefore, the operation on each of five workstations is repeated.

Our approach to solving this problem is a combination of the searching algorithm with a special local criterion and algebraic-logical models switching. So far, the searching algorithm has been used to determine the deterministic problem solution on the basis of discrete process simulation. Switching method allows to present a problem using two simple models and switching function, which specifies the rules of using these models. A combination of those methods allows to solve non-deterministic problems. Our approach is based on algebraic-logical meta-model (ALMM) when the idea of an ALMM paradigm was proposed and developed by E Dudek-Dyduch. Using ALMM approach allows to reconstruct the process of decision making as well as to monitor and track decisions during the manufacturing process.

This article constitutes summary and extension of our previous works mainly related to problem modeling and representation. In particular, the papers^1,2 present a general form of switching method, ALM models and definition of the switching functions, and the switching algorithm for the flow-shop system with defects and one additional repairing machine. The paper³ proposes a combination of switching models method and an optimization method to solve the considered problem. The results of experiments examine the cost of algebraic-logical models switching operations, and the impact of the number of defect repairs for execution time and the switching number between models were shown. In this article, we propose the general form of hybrid algorithm. We present in detail a complete example of solving the problem using hybrid algorithm, hence we provide the details of the problem analysis, the precise elements of the models, and the detailed stages resulting from the combination of two methods. In addition, the analysis of data changes depending on different kinds of disturbances that have been described. Moreover, detailed scheme of a hybrid algorithm for the flow-shop with defects problem and experiments comparing the obtained results with the reference solutions of the problem of flow shop is presented.

The presented approach differs from the concept of the modeling method for discrete manufacturing processes with disturbances described in Dudek-Dyduch,^4,5 called a two-stage algebraic-logical model transformation method (2SALMT method). A parallel identical machine processes with job’s due dates were mentioned in these papers.

The article is organized as follows. In section “Motivation and background,” we present our motivation and an overview of the literature concerning existing approaches for solving scheduling problems, especially flow-shop system. In section “Flow-shop system with defects problem,” we describe the flow-shop manufacturing system with time limits, in which there are the quality control for the defects detection, removal of the manufacturing quality defects on an additional repairing machine, and job re-treatment in part or all technological routes. Section “ALMM approach for multistage decision process” includes a definition of a multistage decision process (MDP) according to ALMM methodology and its general application to non-deterministic polynomial-time (NP)-hard problems. In section “ALMM-based hybrid algorithm,” we present in detail the general form of hybrid approach including searching algorithm using special local optimizing task and the method of algebraic-logical models switching. Moreover, the hybrid algorithm is described. The elements of presented approach, i.e., types of disturbances analyzing, determining the set of switching states, definition of subproblems, ALM models creating for all subproblems, switching types specifying, determination of the switching rules, the switching function definition, and special local criterion determining for considered problem are given in section “Algorithm for flow-shop system with defects.” Section “Experiments and results” contains the results of computational experiments. The last section contains conclusions and future works.

Motivation and background

Our motivation is as follows. The task of scheduling is one of the most challenging problems, and the majority of real scheduling problems are known to be NP-complete or NP-hard in their general form. Different exact and approximate methods are used to solve them, such as mathematical methods (e.g. petri net, branch and bound, and integer programming), heuristic methods (genetic algorithms, Tabu search, simulated annealing, and nature-inspired metaheuristics), and other approaches such as agent methods.^6–11 However, researchers are still searching for methods to decrease the complexity of computations in this field. Recently, the application of cellular automata to solve scheduling problems has been described in the literature. The adaptation of cellular automata to solve parallel scheduling problems was first described by Seredyński and colleagues,^12–14 Vidica and de Oliveira,¹⁵ and Draa and Meshoul.¹⁶ The next proposition for using cellular automata to solve scheduling problems is described by M Abdolzadeh and H Rashidi¹⁷ and Antczak et al.¹⁸ In these papers, the application of cellular automata (CA) technique to solve job shop problems was presented. Solving scheduling problems using constraint programming (CP) is also very popular, especially in production scheduling, project planning, and transport problems.^19–21 CP is very useful for NP-completeness problems where different strategies and heuristics have to be tested and also decision support is required.

Moreover, real manufacturing scheduling problems are also dynamic and subjected to a wide range of stochastic uncertainties, such as stochastic processing time and rush order. Therefore, the production scheduling under uncertainty has indeed attracted much attention in recent years.^22–26 However, the considered flow-shop problem with defects is not equivalent to the flow-shop problem with stochastic uncertainties. The most important thing in considered problem is the detection of unexpected events when schedule is executed and the possibility of including in schedule data or parameter changes which come from the occurrence of the event.

In our approach, we use switching models method. This concept models appear in the scientific literature. Most methods are used in financial econometric and economics models (Markov chain, Markov-switching multifractal, and regime-switching models)^27–29 or in sequential logic circuits. However, these methods are related to totally different problems than the considered flow-shop problems. Moreover, they do not allow to model decision-making process connected with the assignment of tasks with defect to repair. Such modeling is important and helpful in making decisions in real production systems.

Because in the considered flow-shop problem with defect removal we would like to reconstruct the process of decision making (not only obtain a solution taking into account the job stochastic execution time), we choose ALMM approach. Unfortunately, ALMM approach does not allow to change data during the process; thus, we propose to use ALM model switching method. To solve this type of optimization problem, we propose using hybrid algorithm, which includes searching algorithm with the special local criterion and the method of algebraic-logical models switching.

Flow-shop system with defects problem

In the article, we consider flow-shop manufacturing problem in which there are the quality control for the defects detection, removal of the manufacturing quality defects on an additional repairing machine, and job re-treatment in part or all technological routes. Moreover, deadline is determined for some or all jobs. Thus, the dedicated machines process a set of jobs. A job may consist of a single element up to k elements. When the job consists of more than one element, it can be divided into parts and the parts can be independently processed as new jobs. The stores in front of each machine (where job must wait to be processed when machine is busy) are considered as well as store for finished jobs. During the manufacturing process after the indicated treatment, there is a quality control performed always on the same indicated machine. A quality lack may be found for some part of the checking job in consequence of this control. Then, in manufacturing process, it is necessary to use additional operations of defects removal on additional machine. Job with defect is divided into two parts and considered now as new jobs. As a result of the job division, size of new jobs depends on the number of faulty elements and correct elements. A faultless job continues technological line operations, while job with a defect is directed to repairing machine. After the repair operation, all of technology route operations or part of them should be repeated for repaired items. Therefore, the total time of job execution is not known a priori, because the number of faultless job is unknown and it follows that the time needed for performing additional operations to correct defects is unknown. The goal is to schedule jobs, so that all the jobs are completed before its due date and when its quality is accepted. It should be noted that in this article, we consider one machine with quality control and one repairing machine.

We use the following notation to describe the considered problem. There is a set of $m + 1$ dedicated machines $M = {M_{1}, M_{2}, \dots, M_{m + 1}}$ , where m machines constitute the production route $(M_{1}, M_{2}, \dots, M_{m + 1})$ , one $m + 1$ machine is outside the production route and is named a repairing machine (on which all jobs with defects are repaired). We denote this machine as $M_{dr}$ . Moreover, we differentiate single machine with quality control from the production route is denoted as $M_{qc}$ , and the machine on which repaired jobs return to the technological line is denoted as $M_{ret}$ . There is a store in front of each machine, where job must wait to be processed when machine is busy. There is a store for finished jobs too. Considered flow-shop technology route with stores and a repairing machine is shown in Figure 1. The set of jobs $J = {J_{1}, J_{2}, \dots, J_{n}}$ . As we previously mentioned, one job is equivalent to a few elements. Each jth job, $1 \leq j \leq n$ , is performed by m operations (all jobs follow the same route from the first machine to the m one). For each ith operation, we have the processing time of the operation $p^{i, j}$ , where i is the number of operation and j is the number of job. The processing time on the machine with quality control includes the quality control time. Therefore, we assume that the jobs can be divided into smaller jobs. The processing time for jobs resulting from the division of a job with defects is calculated based on the number of elements to repair and elements without defect. Because the number of jobs with defect and number of defected elements in particular job is not known a priori, the processing time for jobs with defects is unknown a priori, and it is calculated during the process. Moreover, due dates for some of the jobs $d (j)$ are given there. The aim is to determine the production schedule where all jobs are completed before their deadlines.

Figure 1.

Flow-shop technology route with stores and a repairing machine.

ALMM approach for MDP

The idea of an ALMM paradigm was proposed and developed by E Dudek-Dyduch. The definition of ALMM of discrete deterministic process is inter alia in Dudek-Dyduch.^30–32 According to ALMM methodology, a problem is modeled as a MDP together with optimization criterion Q. MDP is defined as a sextuple which elements are a set of decisions U, a set of generalized states $S = X \times T$ (X is a set of proper states and T is a subset of non-negative real numbers representing the time instants), an initial generalized state $s_{0} = (x_{0}, t_{0})$ , a transition function $f (s, u)$ , a set of non-admissible generalized states $S_{N} \subset S$ , and a set of goal-generalized states $S_{G} \subset S$ .

Transition function f is defined by means of two functions: $f_{x} : U \times X \times T \to X$ determines the next state and $f_{t} : U \times X \times T \to T$ determines the next time instant. As a result of the decision u that is taken at some proper state x and a moment t, the state of the process changes to $x' = f_{x} (u, x, t)$ that is observed at the moment $t' = f_{t} (u, x, t) = t + Δ t$ . All limitations concerning the control decisions in a given state s can be defined in a convenient way by means of so-called sets of possible decisions $U_{p} (s)$ and can be defined as follows: $U_{p} (s) = {u \in U : (u, s) \in Domf}$ .

The optimization task is to find an admissible decision sequence $\tilde{u}$ that optimizes criterion Q. The consecutive process states are generated as follows. A process starts with initial state $s_{0}$ . Each next state depends on the previous state and the decision made at that state. The decision is chosen from different decisions, which can be made at the given state. Generation of the state sequence is terminated if the new state is a goal state, a non-admissible state, or state with an empty set of possible decisions. The sequence of consecutive process states from the given initial state to a final state (goal or non-admissible) form a process trajectory.

The advantages of ALMM are that values of particular coordinates of a state or/and decision may be names of elements (symbols) as well as some objects, for example, a finite set and sequence (thus they do not have to be numerical), and the set of possible decisions $U_{p}$ , a set of non-admissible generalized states $S_{N}$ , and a set of goal-generalized states $S_{G}$ are formally defined with the use of logical formula. It allows to represent all kind of information regarding to the mentioned problem (including various temporal relationships and restriction of the process) in a convenient way.³⁰ Moreover, such an approach enables making collective decisions in successive process stages, not only for individual objects separately.^33,34

The ALMM approach allows one to solve discrete optimization problems by finding optimal or suboptimal solutions. Based on ALMM methodology, the following general approach has been developed so far: method uses specially designed local optimization task and the idea of semi-metric,^31,32 learning method uses the information gathered during a searching process,³³ method based on learning process connected with pruning non-perspective solutions,³⁴ and substitution tasks method³⁵ (a solution is generated by means of sequence of dynamically created local optimization tasks so-called substitution tasks).

In general, applying a formal approach ALMM is useful for a wide class of difficult (especially NP-hard problem) multistage decision problems, the parameters of which depend on the system state (e.g. the retooling time or resources depending on system state) and unexpected events during process (e.g. quality defect, lack of resource, and failure mode). This methodology allows to design algorithms and methods in a formal way, on a general level (high level of abstraction).

ALMM-based hybrid algorithm

Above-mentioned ALMM-based approach allows to solve non-deterministic discrete optimization problems which are modeled using algebraic-logical model. It is a combination of the searching algorithm with the special local criterion and the method of algebraic-logical models switching. The searching algorithm is used to determine the deterministic problem solution on the basis of discrete process simulation. Switching method is used when an occurrence of events during the process is detected and allows to present a problem using simple models and switching function, which specifies the rules of using these models. In the article, we develop the approach proposed in Kucharska et al.,³ which shows only one type of disturbance and switching between only two models, and now, the general hybrid algorithm form is proposed (section “Hybrid algorithm procedure”). Beforehand, let us recall the basic elements of this approach: searching algorithm with the special local criterion (section “Searching algorithm with the special local”) and ALM switching method (section “ALM switching method”).

Searching algorithm with the special local criterion

The searching algorithm belongs to the class of heuristic algorithms based on partial generation and searching of states graph and using local optimization. But, in basic form of those methods, local optimization was only based on minimization (maximization) of the local increase in quality criterion. Our algorithm consists of generation of consecutive solutions (whole trajectories started from the initial state $s_{0} = (x_{0}, t_{0})$ ) in accordance with ALMM methodology. In the course of generating the trajectory, specially designed local optimization task is used to choose decision in a particular state which takes into account much more information than only the one about the increase in the criterion. Particularly, this task may use the semimetrics term in the state space. The ideas of using local criterion relate to additional limitation and semimetrics were first presented by E Dudek-Dyduch³⁰ and developed inter alia in Dudek-Dyduch and colleagues.^31,33,34 Characteristic element of the algorithm is the possibility of modification of local criterion weight coefficients as well as criterion form depending on current process state. Let us recall the basic elements of this approach.

Local optimization of decision choice

The trajectory generation is connected with a choice of decision in subsequent states. Selecting the appropriate decision among all possible decisions in given state has a significant impact on the ability to generate an admissible and good quality solution and on the ability to generate an admissible solution faster. One way of selecting a decision at the u from a set of possible decisions in given state $U_{p} (s)$ is using the special local optimization criterion $q (u, x, t)$ which consists of the following three parts:

Components related to the value of the global index of quality for the generated trajectory and consists of the increase in the quality index resulting from the realization of the considered decision and the value related to the estimation of the quality index for the final trajectory section, which follows the possible realization of the considered decision. This part of the criterion is suitable for problems which quality criterion is additively separable and monotonically ascending along the trajectory.³⁰

Components related to additional limitations or requirements. The components estimate the distance in the state space between the state in which the considered decision has been taken and the states belonging to the set of non-admissible states $S_{N}$ , as well as unfavorable states or favorable states (these subsets can be identified a priori, based on analysis of problem or may be specified by the experts). Since the results of the decision are known, no further than one step ahead, we apply semimetrics as the “measure of distance” in the set of states.

Components responsible for the preference of certain types of decisions resulting from problem analysis. These subsets can be identified a priori, based on analysis of algebraic-logical model of problem or may be specified by the experts.

The basic form of the local criterion $q (u, x, t)$ is as follows

\begin{array}{l} q (u, x, t)' = Δ Q (u, x, t) + \hat{Q} (u, x, t) \\ + a_{1} α_{1} (u, x, t) + … + \\ + a_{i} α_{i} (u, x, t) + … + a_{n} α_{n} (u, x, t) \\ + b_{1} β_{1} (u, x, t) + … + \\ + b_{j} β_{j} (u, x, t) + … + b_{m} β_{m} (u, x, t) \end{array}

(1)

where

$Δ Q (u, x, t)$ is the increase in the quality index value as a result of decision u taken in the state $s = (x, t)$ ;

$\hat{Q} (u, x, t)$ is the estimation of the quality index value for the final trajectory section after the decision u has been realized;

$α_{i} (u, x, t)$ is the component reflecting additional limitations or additional requirements in the space of states, $i = 1, 2, \dots, n$ ;

$β_{j} (u, x, t)$ is the component responsible for the preference of certain types of decisions, $j = 1, 2, \dots, m$ ;

$a_{i}, b_{j}$ is the coefficients which define the weight of proper component.

Because the total quality index value Q is being minimized, the best $u^{*}$ decision is decision for which the local criterion value q is the smallest. Because of determining optimal weights of coefficients a_i and b_j a priori difficulty (both depend on the considered optimization problem as well as the input date for the particular optimization task), they may be calculated during simulation experiments or using learning method.

Local optimization criterion modification

Modifications may be subject to both a form of criteria and weights of coefficients. In the simplest case, the basic form of local criterion as well as weights of coefficients (a and b) can be established for one trajectory generation. But generally, they can be modified in the course of the same trajectory generation too. The modification (increase or reduction) of the coefficients during the generation of trajectory may appear when certain limitations and preference of certain types of decisions are more/less important or inactive in the given state of process. The modification of criterion form can occur when some limitations lose sense or some additional limitation or situation takes place. Both types of modification can occur automatically, based on previously defined rules. Regarding verification, it is important whether the modification should be done or not and whether it requires the minimum or possibly a small amount of calculation, for example, checking only one or a few coordinates of state. In fulfilling this requirement, it seems possible to reduce the calculations, the value of q which is implemented for each decision belonging to the set of possible decisions in the given state.

It needs to be highlighted that using a more complicated form of a local criterion and its modification should consider two opposing postulates. On one hand, more complicated criterion form usually includes more information and thus choice of decisions may be more beneficial—a chance of finding a better solution is greater. On the other hand, we must take into account the complexity and computation time of determining the value of a local criterion.

ALM switching method

The switching ALM method for flow-shop system with defects was proposed in Grobler-Dębska et al.¹ Let us recall it in short. This method is an approach to formal notation of problems in which some events that would influence job processing occur during the process execution and comes from a conception of control of discrete manufacturing process in the failure mode proposed by H Sękowski and E Dudek-Dyduch.³⁶ A detection of defect in produced element, that is, irregular application of paint on a painted element, bad balance of springs in mattress, and backfilling of the hollow headings in a mine may cause such events. Usually, it cannot be predicted a priori when these events occur, but it is possible to predict the effects of these events, that is, an appearance of a new job for processing, a necessity of repairing operation, a necessity of repeating an operation, or several operations for a job with defects. Consequently, these events may cause data or parameters of the problem to change. Moreover, we would like to model formally the effect of these events in decision process.

The ALM models switching method is based on the ALMM methodology and consists of the following elements:

Analysis of types of disturbances;

Analysis of how date can change based on type of disturbance;

Determining the set of switching states;

Distribution of problem for subproblems;

ALM models creating for all subproblems;

Specifying types of switching;

Determination of the switching rules;

The switching function definition.

It should be noted that a structure of ALM models for subproblems may be the same or different. It depends on the type of data changes. In the simplest case, we can use the same model. Furthermore, for some problems, in which there are various types of data changes, we can specify several models of simpler problems (subproblems of initial problem) taking into account the changes that can be predicted.

The executing method is as follows. A disturbance occurrence is detected in the nearest next process state $s_{k}$ . Based on type of disturbance and current algebraic-logical model $AL M_{now}$ , the type of algebraic-logical model you want to switch $AL M_{next}$ is specified. Then, the switching function, using switching rules, calculates the initial state $s_{0}$ in $AL M_{next}$ model based on the event occurrence, and the current state of the manufacturing process represented by $s_{k}$ of current $AL M_{now}$ model. The changes in data and parameters, which are a consequence of the event, are taken into account in the new state. After ALM models, switching trajectory generation of process is continued. Moreover, in every switching, data are recalculated based on types of disturbances. The notation of the method of ALM models switching was presented in Grobler-Dębska et al.²

General hybrid algorithm procedure

The general idea of the hybrid algorithm is proposed in this section and the elements of the algorithm are given as follows. The algorithm generates process trajectory using the special local optimization task. A trajectory generation is interrupted when a disturbance is detected or disturbance or its effect is eliminated. Then, the switching ALM models method is used. To apply the general idea, individual elements of the algorithm should be developed. We proposed the following elements based on the factors set out in the general descriptions of the methods in the previous sections:

Analysis of the problem. Consists in determining some characteristic problem features. In particular, limitations or requirements reflected to the problem are detected and preferences of certain types of states or decisions are determined. Moreover, identification of occurring disturbances is made, both kind of disturbances and the moment of occurrence. The purpose of this analysis is to design local criterion form and particular elements of switching method.

Local criterion definition. Consists in determining particular components based on identifying limitations, requirements, and preferences. Definition of components related to the estimation of the quality index for the final trajectory section is also important (it may have different forms and precision). Moreover, modification of the local optimization task could be defined. It should be noted that the local criterion form can be designed in different ways. First, the components may be determined based on the properties of the problem without disturbance; then, the criterion in such a form can also be used for a process taking account of the disturbance. The second way is to design an additional component or components associated with the considered disturbance. When one has identified more different types of disturbances, suitable ingredients may be used appropriately.

Switching method elements definition. Consists in set of switching states specification (includes all states when new disturbance occurs or previous detected disturbance is removed for all types of disturbance and this also states when, for example, the first kind of disturbance is removed and the second occurs in the same process state), distribution of problem for subproblems (e.g. problem without disturbance and problems which take disturbance or its effects into consideration), ALM models for all subproblems specification (depends on the type of data changes, a structure of ALM models may be the same or different. The aim is to specify simpler models of simpler problems), types of switching specification (it depends on number of disturbance type. There are three types of switching when only one type disturbance is detected: (1) the system switches from process without the disturbance to process taking into account disturbance or its effects when there is no other disturbance, (2) the system switches from process taking into account disturbance to the same process with modified parameters and data for detection of new disturbance when the effects of the earlier disturbance have not been removed yet or when the part of disturbance effects has just been removed, and (3) the system switches from process taking into account disturbance or its effects to process without disturbance when all disturbance effects have been just removed. However, the greatest number of type switching should be considered when the greatest number of disturbance type is detected. In such a case, it should be analyzed all the possibilities of switching when the system switches from process with one kind of disturbance to the process with another type of disturbance or to the process without disturbances), and the switching function constructing (determining the rules depending on types of switching. It consists in determination of algebraic formulas to recalculate parameter values in case of switching between the same model ALM or calculate a new state and new parameters value in case of switching between different ALM models. The switching rules are not determined for all combinations of switching between models. It should be excluded the switching between those models, which are not related. For example, two models are not related when reparation of one type of disturbances is two-sided: first, the other type of disturbance is received and after that, it is total repaired. It means that the system cannot be switched from model with this type of disturbances to the model without disturbances).

When all the algorithm elements presented above are determined, the steps of proposed algorithm are as follows. Let us assume following notation to better illustrate the steps of the algorithm: $AL M_{A}$ denotes algebraic-logical model of process without disturbance; $AL M_{B}$ and $AL M_{C}$ denote algebraic-logical models of process with different disturbance types, respectively; and symbol “′” of the model denotes algebraic-logical model with the same structure, but with recalculated parameters as a result of switching, for example, $AL M_{A'}$ denotes algebraic-logical model of process without disturbance, but with recalculated parameters as a result of switching when all disturbance effects have just been removed.

The first trajectory is constructed. The basic process, for problem without disturbance, starts with initial state $(s_{0})_{A}$ and model $AL M_{A}$ for problem without disturbance. A new process state is calculated based on the previous state and the decision made at that state. The decision is chosen from the set of possible decisions which can be made at the given state and has the smallest value of the local criterion determined in accordance with the method described above. The new state is checked in respect of belonging to the set of goal state, the set of non-admissible state, the set of state with an empty set of possible decisions or the set of switching states. In the first three cases, generation of the state sequence is terminated and the reason for stopping can be stored and used for the next trajectory constructing. The fourth case indicates that some disturbance has been detected. Then, the switching ALM model method is used in this new process state, denoted as $(s_{k})_{A}$ . Based on the type of disturbance and current algebraic-logical model $AL M_{now} = AL M_{A}$ , the type of algebraic-logical model you want to switch $AL M_{next} = AL M_{B}$ or $AL M_{next} = AL M_{C}$ is specified. Then, the switching function calculates the initial state $(s_{0})_{n} ext$ in $AL M_{next}$ model using switching function, and the current state of the manufacturing process represented by $(s_{k})_{A}$ of current $AL M_{A}$ model. Then, next states are calculated using the local criterion, in the same or modified form, respectively, for process modeled by $AL M_{now}$ . Each next states are checked in respect of belonging to the set of non-admissible state, the set of state with an empty set of possible decisions, or the set of switching states. The next state is checked in respect of belonging to the set of goal state if and only if belongs to the model $AL M_{A}$ or $AL M_{A'}$ , because all disturbances have to be removed. The fourth case indicates that some new disturbances have been detected or some (all) types of disturbance effects have just been removed. In that case, further switching of ALM models occurs, and the switching function calculates the initial state $(s_{0})_{next}$ in $AL M_{next}$ model using switching function and the current state of the manufacturing process represented by $(s_{k})_{now}$ of current $AL M_{now}$ model. The next ALM model is respectively:

The basic model without disturbances, but with recalculated parameters $AL M_{A'}$ , when all types of disturbance effects have just been removed;

The current version of the model with disturbances with recalculated parameters $AL M_{now'}$ , for example, $AL M_{B'}$ , when process has been modeled by $AL M_{B}$ and the same disturbance type occurs;

Other appropriate models with disturbances $AL M_{next}$ , for example, $AL M_{C}$ , when process has been modeled by $AL M_{B}$ and the different disturbance type occurs.

The above procedure is repeated until the whole trajectory (admissible or non-admissible) is not generated. The result can be stored and used for constructing the next trajectory. Based on this, the next trajectories can be constructed with modified local criterion coefficients value (a and b) as well as the modified local criterion basic form.

Figure 2 shows examples of the process trajectory. The first example takes into account the trajectory of one switch to the model with disturbances $AL M_{B}$ and return to the model without disturbances with recalculated parameters $AL M_{A'}$ . The second example takes into account the trajectory of one switch to the model with disturbances $AL M_{B}$ , re-switches to the model with disturbances $AL M_{B}$ with recalculated parameters $AL M_{B'}$ resulting from the recurrence of disturbances and returns to the model without disturbances with recalculated parameters $AL M_{A'}$ .

Figure 2.

Examples of the process trajectories.

Algorithm for flow-shop system with defects

This section presents the complete hybrid algorithm application to flow-shop system with defects. The algorithm generates process trajectory using the special local optimization task. When job quality defect is detected or repair of defective elements was completed, the trajectory generation is interrupted and the switching ALM models method is used. Then, the process of constructing the trajectory is continuing. Below, particular elements of hybrid algorithm are presented.

Analysis of the problem

First, analysis of the problem and identification of occurring disturbances were made. The purpose of this analysis was to determine some characteristic problem features. This analysis took into account several aspects characterizing the specific problem: number of workstations in which quality control is performed, range and accuracy of quality control, and actions to be taken after finding a lack of quality.

Based on the analysis of the process, it can be concluded that detection of defect is an uncertain event (disturbance). Without this event, a basic process is a realization of a set of jobs in flow-shop system with deadline. The consequence of those events is that we have to use an additional machine (machines in the general case) to repair the defected job. In this case, the process is realized in a flow system, where there is repairing operation outside manufacturing route. Therefore, the analysis showed that a repair on the additional machine and re-treatment can be modeled by switching the model of flow system with deadline, the model of flow system with deadline which takes into account the additional machine to repair deficiencies and the division of job into two parts (one including only elements to repair and second including elements without defect).

Set of switching states

Switching takes place in two cases; first, in the kth state of the process, in which as a result of quality control defects were found. In this case, the additional repairing machine is needed. Second, switching takes place in states in which defect repairing is finished, thus an additional machine is not necessary anymore. Therefore, the set of switching states $S_{switch}$ includes states in which the machine with quality control has just finished job performance and the result of quality control has been negative and the states in which the additional machine has just finished repair a task with defect.

Distribution of problem for subproblems

Having regard to analysis results, the basic flow-shop system with deadlines and defects removal problem was split into two subproblems: flow-shop system with deadlines and flow-shop system with deadlines and additional repairing machine.

ALM models for all subproblems

The next step was creating two algebraic-logical models. For this purpose, first, we created a model of flow-shop problem with time limits but without repairing and re-treatment (called model $AL M_{A}$ in section “Algebraic-logical model of flow-shop system with time limits”). Then, we appropriately modify the model without changing the original structure of ALM model, but we only complement the model of component which requires a repair of parts with defects (called model $AL M_{B}$ presented in section “Algebraic-logical model of flow-shop system with repairing machine”). It should be emphasized that the essential structure of the modified model has not been changed. Both models in its original form were proposed in Grobler-Dębska et al.¹ Below, the slightly improved models are shown.

To define the process using algebraic-logical model, it should be given a form of system state, the initial state, the set of non-admissible generalized states, and the set of goal-generalized states first. The form of the system state has to contain an adequate description of the system components like machines, jobs, and warehouses, so that the model takes into account the ability to assign jobs to the appropriate machine or waiting machines to complete certain jobs and jobs waiting to be assigned to the machine, which is currently busy. Then, it should be given the form of a decision and the set of decisions that can be taken in individual state. At the end of the model construction, it should define the transition function, that is, the way of determining the moment when another state occurs.

Algebraic-logical model of flow-shop system with time limits

Let $U_{A}, S_{A}, (s_{0})_{A}, f_{A}, (S_{N})_{A}, and (S_{G})_{A}$ denote adequate set of decisions, the set of proper states, the initial state, the transition function, the set of non-admissible states, and the state of goal states in the algebraic-logical model of flow-shop system with time limits $AL M_{A}$ , respectively.

A set of jobs is denoted as $J_{A}$ and a set of machines is denoted as $M$ .

State of system

The generalized state of process $s_{A} = (x_{A}, t_{A})$ at any instant $t_{A}$ can be described by state of machines in the technology route, state of the initial store, and state of the work-in-progress store. Intentionally, in the system state, it is not taken into account the information of the final store including completed jobs because it is redundant information (a set of completed jobs is calculated slightly lower). Thus, the proper state of the process is defined as a n-tuples

x_{A} = (x_{A}^{1}, \dots, x_{A}^{| M |}, x_{A}^{| M | + 1}, \dots, x_{A}^{2 | M |})

(2)

where $x_{A}^{1}$ is the state of the initial store, $x_{A}^{i}$ is the state of the ith work-in-progress store (between i − 1th and ith machine) for $i = 2, \dots, | M |$ , and $x_{A}^{| M | + i}$ is the state of the ith machine for $i = 1, \dots, | M |$ .

A coordinate $x_{A}^{1}$ is a set of jobs to process by first machine, that is, jobs which have not started performing yet. Particular coordinate $x_{A}^{i}$ , where $i = 2, \dots, | M |$ , is a set of jobs which has been finished on the i − 1th machine and in the current state are available to process by ith machine and are not assigned to this machine.

A structure of the machine state is as follows: $x_{A}^{i} = (β_{A}, τ_{A})$ , where particular coordinates take the following: $β_{A} \in {0, 1, \dots, | J_{A} |}$ —job number, which is currently performing on the machine (0 denotes that no job is assigned to process by the machine) and $τ_{A} \in [0, \infty]$ —time remaining to complete currant job ( $\infty$ denotes that the machine doesn’t work).

We can say that each ith machine is not working (is free) in state s when machine state is $x_{A}^{| M | + i} (s) = (0, \infty)$ . Each ith machine is working (is busy) in state when $x_{A}^{| M | + i} (s) = (β_{A} \neq 0, τ_{A} > 0)$ . In fact, there are no states when the machine is working and job is not allocated to machine ( $β = 0$ and $τ > 0$ ) as well as machine is not working and has assigned the job the same time ( $β > 0$ and $τ = 0$ ).Thus, other combinations of the coordinate values of the machine state are not reflected in the real manufacturing process.

Let $β_{A}^{i}$ and $τ_{A}^{i}$ denote the appropriate values for a particular ith machine, and $x_{A}^{i} (s)$ denotes the value of ith coordinate in a particular state $s_{A}$ .

In an initial state ( $(t_{0})_{A} = 0)$ , the jobs are not performed and no job has been assigned to perform by any machine. Thus, the initial system state is as follows: $(x_{0})_{A} = ((x_{0})_{A}^{1}, \dots, (x_{0})_{A}^{| M |}, (x_{0})_{A}^{| M | + 1}, \dots, (x_{0})_{A}^{2 | M |})$ , where $(x_{0})_{A}^{1} = J_{A}$ , $(x_{0})_{A}^{i} = \emptyset$ for $i = 2, \dots, | M |$ and $(x_{0})_{A}^{i} = (0, \infty)$ for $i = | M | + 1, \dots, 2 | M |$ .

We define in the model a helpful set of completed jobs $(J_{F})_{A}$ in state s, which is equal to a difference of set of all jobs to perform and sets of jobs in stores with jobs processing by machines: $(J_{F})_{A} (s) = J_{A} / \cup_{i = 1}^{| M |} (x_{A}^{i} (s) \cup {β_{A}^{i + | M |} (s)})$ .

The set of non-admissible generalized states $S_{N}$ includes states for which job has not been finished and its due date has passed: $(S_{N})_{A} = {s_{A} : \exists_{j \in J} j \notin (J_{F})_{A} (s_{A}) \land d (j) < t_{A}}$ . A state $s_{A}$ is a goal where all the jobs have been performed and all job’s deadlines are not overdue. Set of goal-generalized states $(S_{G})_{A}$ is as follows: $(S_{G})_{A} = {s_{A} : (J_{F})_{A} (s_{A}) = J_{A} \land \forall_{j \in J_{A}} d (j) \geq t_{A}}$ .

Decisions

In the considered problem it is assumed that the decision consists in assigning jobs to individual machines at the same time. Particular coordinate $u_{A}^{i} \in U_{A}^{i}$ represents separate decisions and refers to the ith machine ( $i = 1, \dots, | M |$ ).

The following assumptions have been proposed regarding the decision: the decision to allocate the next job for the machine can be taken if and only if the machine finished the previously assigned job and the job was previously performed by the previous machine in the technological route, the taken decision cannot be changed. Thus, the busy machine (realizing decision taken earlier) can only continue performing the previously assigned job. To the free machine in current state, it can be assigned the job which satisfies the condition that it has been done by the previous machine in the technological route. When there is no job assigned to the free machine, the machine is still free.

Thus, the decision is a vector, $u_{A} = (u_{A}^{1}, \dots, u_{A}^{| M |})$ and value of particular coordinate $u_{A}^{i} \in J_{A} \cup {0}$ is as follows:

If jth job is assigned to the ith machine, then only the possible decision to take is processing continuation $u_{A}^{i} = 0$ ;

If the ith machine is free and there is no job that could be assigned, that is, $x_{A}^{i} (s) = \emptyset$ , then the only possible decision to take is not assigning any task $u_{A}^{i} = 0$ ;

If the ith machine is free and the ith store is not empty (i.e. any jth job from the store can be assigned to the machine), then the possible decision to take is assigned job $u_{A}^{i} = j$ or no any job (still inactivity) $u_{A}^{i} = 0$ .

The decision $(u_{p})_{A}$ must belong to the set of possible decision $(U_{p})_{A}$ in a given state $s_{A}$ . Possible decision is dependent on the state of the particular machine. Possible decisions $(u_{p}^{i})_{A} (s)$ for the ith machine in state $s = (x, t)$ is defined as follows $\forall_{i = 1, 2, \dots, | M |}$

(u_{p}^{i})_{A} (s) = {\begin{matrix} 0 & for x_{A}^{i + | M |} (s) \neq (0, \infty) \\ 0 & for x_{A}^{i + | M |} (s) = (0, \infty) if x_{A}^{i} (s) = \emptyset \\ 0 \lor j & for x_{A}^{i + | M |} (s) = (0, \infty) if j \in x_{A}^{i} (s) \end{matrix}

(3)

We should note that it is not possible to assign one job to two different machines. Each set $(U_{p}^{i})_{A}$ is equal to the set of jobs in work-in-progress store plus the element 0, that is, $(U_{p}^{i})_{A} = x_{A}^{i} (s) \cup {0}$ .

The complete definition of the set of the possible decision is as follows: $(U_{p})_{A} (s) = (U_{p}^{1})_{A} (s) \times \dots \times (U_{p}^{| M |})_{A} (s) / H_{A} (s)$ , where $H_{A} (s)$ is a set which includes decision of not assigning to any job $u_{A} = (0, \dots, 0)$ when all the machines in a given state are free and not all jobs are completed. $H_{A} (s) = {u_{A} : (\forall_{i \in M} : u_{A}^{i} (s) = 0 \land x_{A}^{i + | M |} (s) = (0, \infty)) \land (J_{F})_{A} \neq J_{A}}$ Consecutively taken decisions form a decision sequence ${\tilde{u}}_{A} = ((u_{1})_{A}, (u_{2})_{A}, \dots, (u_{c})_{A})$ , where c is the number of taken decisions. This sequence uniquely determines the trajectory of process.

Transition function $f_{A}$

The transition function is defined by means of two functions $f_{A} = ((f_{x})_{A}, (f_{t})_{A})$ , where $(f_{x})_{A}$ determines the next proper state and $(f_{t})_{A}$ determines the next time instant. First, it is necessary to determine the moment when the subsequent state occurs $t_{A'} = t_{A} + Δ t_{A}$ . $Δ t_{A}$ equals the lowest value of time needed to complete job processing by ith machine.

Once the moment $t_{A'}$ is known, it is possible to determine the proper state of the process at that time (determining $(f_{x})_{A}$ ). The coordinate $x_{A}^{1}$ (state of initial store) is reduced by job, which is assigned to the first machine: $(x_{A}^{1} (s))' = x_{A}^{1} (s) / {j : u_{A}^{1} (s) = j}$ . Coordinate $x_{A}^{i} for i = 2, \dots, | M |$ (state of store between i − 1th and ith machine) is increased by the job performed on $i - 1 th$ machine and is reduced by the job, which is assigned to ith machine in the technological route: $(x_{A}^{i} (s))' = x^{i} (s) \cup ({j : x_{A}^{i - 1 + | M |} (s) = (j, Δ t_{A})} {j : u_{A}^{i} (s) = j})$ .

Value of coordinates related to machine state $(x_{A}^{i + | M |})' = (β'_{A}, τ'_{A})$ for $i = 1, \dots, | M |$ depends on the decision taken and is as follows:

If ith machine is free in given state machine and decision is $u_{A}^{i} (s) = j$ (assigning jth job to perform by this machine)

\begin{matrix} β_{A'} = {\begin{matrix} 0 & for τ_{A}^{i + | M |} = Δ t_{A} \\ j & for τ_{A}^{i + | M |} > Δ t_{A} \end{matrix} \\ τ_{A'} = {\begin{matrix} \infty & for τ_{A}^{i + | M |} = Δ t_{A} \\ p^{ij} - Δ t_{A} & for τ_{A}^{i + | M |} > Δ t_{A} \end{matrix} \end{matrix}

(4)

If ith machine is free in given state and decision is $u_{A}^{i} (s) = 0$ (not assigning job to perform by this machine): $β_{A'} = 0$ and $τ_{A'} = \infty$ ,

If ith machine is busy in given state and decision is $u_{A}^{i} (s) = 0$ (continuation previously assigned job j)

\begin{matrix} β_{A'} = {\begin{matrix} 0 & for τ_{A}^{i + | M |} = Δ t_{A} \\ j & for τ_{A}^{i + | M |} > Δ t_{A} \end{matrix} \\ τ_{A'} = {\begin{matrix} \infty & for τ_{A}^{i + | M |} = Δ t_{A} \\ τ_{A}^{i + | M |} - Δ t_{A} & for τ_{A}^{i + | M |} > Δ t_{A} \end{matrix} \end{matrix}

(5)

Algebraic-logical model of flow-shop system with repairing machine

Let $U_{B}$ , $S_{B}$ , $(s_{0})_{B}$ , $f_{B}$ , $(S_{N})_{B}$ , and $(S_{G})_{B}$ denote adequate set of decisions, the set of proper states, the initial state, the transition function, sets of non-admissible and goal states in the algebraic-logical model of flow-shop system with repairing machine $AL M_{B}$ , respectively. A set of jobs is denoted as $J_{B}$ and a set of machines is denoted as $M_{B}$ . In the considered problem the size of sets of machines is $| M_{B} | = | M | + 1$ .

State of system

In the same way as in the $AL M_{A}$ model, the generalized state of the process $s_{B}$ at any instant $t_{B}$ is described by state of machines in the technology route, state of the initial store, state of the work-in-progress stores and also by state of additional store for elements with defects and state of the repairing machine: $x_{B} = (x_{B}^{1}, \dots, x_{B}^{2 | M |}, x_{B}^{2 | M | + 1}, x_{B}^{2 | M | + 2})$ , where $x_{B}^{1}$ is a state of the initial store; $x_{B}^{i}$ is a state of the ith work-in-progress store for $i = 2, \dots, | M |$ ; $x_{B}^{| M | + i}$ is a state of the ith machine for $i = 1, \dots, | M |$ ; $x_{B}^{2 | M | + 1}$ is a state of the additional store for the elements to repair; and $x_{B}^{2 | M | + 2}$ is a state of the repairing machine.

The initial state of model $AL M_{B}$ is as follows: $x_{B} = ((x_{0}^{1})_{B}, \dots, (x_{0}^{| M |})_{B}, \dots, (x_{0}^{2 | M |})_{B}, (x_{0}^{2 | M | + 1})_{B}, (x_{0}^{2 | M | + 2})_{B})$ . The initial system state is calculated based on the result of quality control and the current state of the $AL M_{A}$ model at the moment of models switching. The calculation method of the initial state is given in section “The switching function.”

The set of non-admissible states and the set of goal states have the same structure as in the $AL M_{A}$ model, only taking into account the set of jobs $J_{B}$ instead of $J_{A}$ , work-in-progress store, and the machine to defects repairing.

Decisions

Analogically, as in the $AL M_{A}$ model, decisions refer to the allocation of the job to the appropriate machines from appropriate work-in-progress store. Including a repairing machine, we should extend the u decision vector to additional coordinate $u_{B}^{| M | + 1}$ and take into account an additional job. Hence, the decision vector is of the form of $u_{B} = (u_{B}^{1}, u_{B}^{2}, \dots, u_{B}^{| M |}, u_{B}^{| M | + 1})$ and $u_{B}^{i} \in J_{B} \cup {0}$ .

Transition function

Moment $t_{B'}$ is determined exactly as in the $AL M_{A}$ model taking into consideration the processing time of repairing machine. Coordinates, which are responsible for the state of storage (without additional storage) $x_{B}^{i} for : i = 1, \dots, | M |$ , are changing in the transition function in the same way as in the $AL M_{A}$ model. In addition, the coordinate $x_{B}^{2 | M | + 1}$ is reduced to job, which is assigned to repairing machine $(x_{B}^{2 | M | + 1} (s))' = x_{B}^{2 | M | + 1} (s) \ {j : u_{B}^{| M | + 1} (s) = j}$ . Afterward, the value of individual coordinates of the machine $(x_{B}^{i + | M |})' for : i = 1, \dots, | M |$ depends on the decision taken exactly the same as in the $AL M_{A}$ model. Moreover, the state of the repairing machine is going to change in the same way:

If $2 | M | + 2$ th machine is free in given state and decision is $u_{B}^{| M | + 1} (s) = j$ (assigning jth job to perform by this machine, that is, additional storage is not empty)

\begin{matrix} β_{B'} = {\begin{matrix} 0 & for τ_{B}^{2 | M | + 2} = Δ t_{B} \\ j & for τ_{B}^{2 | M | + 2} > Δ t_{B} \end{matrix} \\ τ_{B'} = {\begin{matrix} \infty for τ_{B}^{2 | M | + 2} = Δ t_{B} \\ τ_{B}^{2 | M | + 2} - Δ t_{B} for τ_{B}^{2 | M | + 2} > Δ t_{B} \end{matrix} \end{matrix}

(6)

If $2 | M | + 2 th$ machine is free in given state and decision is $u_{B}^{| M | + 1} (s) = 0$ (not assigning job to perform by this machine)

β_{B'} = 0, τ_{B'} = \infty

If $2 | M | + 2 th$ machine is busy and decision is $u_{B}^{| M | + 1} (s) = 0$ (continuation of previously assigned job j)

\begin{matrix} β_{B'} = {\begin{matrix} 0 & for τ_{B}^{2 | M | + 2} = Δ t_{B} \\ j & for τ_{B}^{2 | M | + 2} > Δ t_{B} \end{matrix} \\ τ_{B'} = {\begin{matrix} \infty for τ_{B}^{2 | M | + 2} = Δ t_{B} \\ τ_{B}^{2 | M | + 2} - Δ t_{B} for τ_{B}^{2 | M | + 2} > Δ t_{B} \end{matrix} \end{matrix}

(7)

Types of switching

The following steps were to specify the types of switching. Three types of switching should be executed:

The system switches from $AL M_{A}$ to $AL M_{B}$ for detection of quality defect when there is no other quality defect;

The system switches from $AL M_{B}$ to $AL M_{B'}$ , in which the parameters must be modified for detection of quality defect while there is another, previously detected, quality defect and it hasn’t been repaired yet (it has been waiting for repair or is during the process of repair), and completion of repair previously detected quality defect and the work-in-progress store before repair machine isn’t empty (there are previously detected tasks with defect);

The system switches from $AL M_{B}$ to $AL M_{A}$ for completion of repair previously detected quality defect, the work-in-progress store before repair machine is empty and repair machine is not working (there is no previously detected task with defect).

The switching function

The last step was determining the switching rules and the switching function. Detailed formulas of how to calculate the next state in case of switching was proposed in Grobler-Dębska et al.²

Let us consider the following notation that is used to present the switching function. Let $J_{d}$ denote the job for which lack of quality has been established, thus d denotes index of job with defect. After the division of job $J_{d}$ into two parts, d is also an index of job containing parts correctly made. Let r denote index of new job including elements with defects $J_{r}$ (job to repair). Let c denotes the index of job with just repaired defect $J_{c}$ (corrected job, returning to the production line). Let $qc \in M$ denotes the index of the machine on which quality control was carried out; $ret < qc \in M$ is the index of the machine on which repaired job goes and $dr = | M | + 1$ denotes the index of repairing machine on which the repairing operation of job $J_{r}$ is performed. The processing time $p^{id}$ for the job $J_{d}$ where $i = qc + 1, \dots, | M |$ and the processing time $p^{ir}$ for job $J_{r}$ (including the treatment on repairing machine) where $i = 1, \dots, | M | + 1$ must be specified based on the amount of job elements with defects. Furthermore, $J_{d}$ and $J_{r}$ jobs have the same deadline. Other data are not changed. The rules of switching are described below:

1. Detection of quality defect when there is no other quality defect. Until that moment, additional defects removal machine was not necessary, thus the $AL M_{A}$ model has been used. In this case, the system switches from $AL M_{A}$ to $AL M_{B}$ . The initial system state $(s_{0})_{B}$ of $AL M_{B}$ is generated based on the current state $(s_{k})_{A}$ of $AL M_{A}$ and the result of quality control $(s_{k})_{A} \to (s_{0})_{B}$ $((t_{0})_{B} = (t_{k})_{A})$ . In this situation, the machine $M_{d} r$ is free in the state $(s_{k})_{A}$ $((β_{k}^{dr})_{A} = 0)$ . $J_{d}$ and $J_{r}$ , where $r = | J | + 1$ , jobs should be assigned to the appropriate work-in-progress stores. The $J_{d}$ job is in store before the next $qc + 1 th$ machine. The $J_{r}$ job is in the store before repairing drth machine. The other coordinates of the state are not changed. Thus, $| J_{B} | = | J_{A} | + 1$ and the following dependents take place

\begin{matrix} (x_{0}^{i})_{B} = (x_{k}^{i})_{A} for i \neq (qc + 1) \\ (x_{0}^{qc + 1})_{B} = (x_{k}^{qc + 1})_{A} \cup {J_{d}} \\ (x_{0}^{| M | + i})_{B} = (x_{k}^{| M | + i})_{A} \\ (x_{0}^{2 | M | + 1})_{B} = {J_{r}} \\ (x_{0}^{2 | M | + 2})_{B} = (0, \infty) \end{matrix}

(8)

2. Detection of quality defect when there is another, previously detected, quality defect and it hasn’t been repaired yet. Until that moment, additional defects removal machine was necessary, thus $AL M_{B}$ was used. In this case, the system switches from $AL M_{B}$ to $AL M_{B'}$ , in which the parameters must be modified. Hence, only division of job and assigning featured jobs $J_{d}$ and $J_{r} = J_{| J_{B} | + 1}$ to the appropriate store is considered. $J_{d}$ is assigned to the store in route and $J_{r}$ to the store before repairing machine.

Thus, $| J_{B'} | = | J_{B} | + 1$ and the initial system state ${(s_{0})}_{B'}$ of $AL M_{B'}$ are generated based on the current state $(s_{k})_{B}$ of $AL M_{B}$ and the result of quality control $(s_{k})_{B} \to (s_{0})_{B'}$ $((t_{0})_{B'} = (t_{k})_{B})$ . The following dependents take place

\begin{matrix} (x_{0}^{i})_{B'} = (x_{k}^{i})_{B} for i \neq (qc + 1) \\ (x_{0}^{qc + 1})_{B'} = (x_{k}^{qc + 1})_{B} \cup {J_{d}} \\ (x_{0}^{| M | + i})_{B'} = (x_{k}^{| M | + i})_{B} \\ (x_{0}^{2 | M | + 1})_{B'} = (x_{k}^{2 | M | + 1})_{B} \cup {J_{r}} \\ (x_{0}^{2 | M | + 2})_{B'} = (x_{k}^{2 | M | + 2})_{B} \end{matrix}

(9)

3. Detection of quality defect when there is another, previously detected, quality defect and it has been just repaired. Until that moment, additional defects removal machine was necessary, thus $AL M_{B}$ was used. In this case, the system switches from $AL M_{B}$ to $AL M_{B'}$ , in which the parameters must be modified. Thus, division of jobs after quality control and assigning featured jobs $J_{d}$ , $J_{r} = J_{| J_{B} | + 1}$ , and $J_{c}$ to the appropriate work-in-progress stores is considered. $J_{d}$ is assigned to the next store in technological route, $J_{r}$ to store before repairing machine and $J_{c}$ to the store before concrete machine in the technological route

\begin{matrix} (x_{0}^{i})_{B'} = (x_{k}^{i})_{B} for i \neq (qc + 1), i \neq ret \\ (x {B'}_{ret}) = (x_{k}^{ret})_{B} \cup {J_{c}} \\ (x {B'}_{ret}) = (x_{k}^{qc + 1})_{B} \cup {J_{d}} \\ (x_{0}^{| M | + i})_{B'} = (x_{k}^{| M | + i})_{B} \\ (x_{0}^{2 | M | + 1})_{B'} = (x_{k}^{2 | M | + 1})_{B} \cup {J_{c}} \\ (x_{0}^{2 | M | + 2})_{B'} = (x_{k}^{2 | M | + 2})_{B} \end{matrix}

(10)

4. Completion of repairing previously detected quality defect and the work-in-progress store before repairing machine isn’t empty (there are previously detected jobs with defect). Until that moment, additional defects removal machine was necessary, thus model $AL M_{B}$ was used. In this case, the system switches from $AL M_{B}$ to $AL M_{B'}$ , in which the parameters must be modified. Thus only assigning the $J_{c}$ job to the appropriate store is considered. Thus, $| J_{B'} | = | J_{B} |$ and the initial state $(s_{0})_{B'}$ (where $(t_{0})_{B'} = (t_{k})_{B}$ ) of $AL M_{B'}$ are as follows

\begin{matrix} (x_{0}^{i})_{B'} = (x_{k}^{i})_{B}, for i \neq ret \\ (x {B'}_{ret}) = (x_{k}^{ret})_{B} \cup {J_{c}} \\ (x_{0}^{| M | + i})_{B'} = (x_{k}^{| M | + i})_{B} \\ (x_{0}^{2 | M | + 1})_{B'} = (x_{k}^{2 | M | + 1})_{B} \\ (x_{0}^{2 | M | + 2})_{B'} = (x_{k}^{2 | M | + 2})_{B} \end{matrix}

(11)

5. Completion of repairing previously detected quality defect, the work-in-progress store before repairing machine is empty and repairing machine is not working (there is no previously detected job with defect). In this case, the system switches from $AL M_{B}$ to $AL M_{A'}$ , in which the parameters must be modified. Thus, only assigning the $J_{c}$ job to the appropriate work-in-progress store in $AL M_{A'}$ is considered. Thus, $| J_{A'} | = | J_{B} |$ and the initial state $(s_{0})_{A'}$ (where $(t_{0})_{A'} = (t_{k})_{B}$ ) are as follows

\begin{matrix} (x_{0}^{i})_{A'} = (x_{k}^{i})_{B}, for i \neq ret \\ (x_{0}^{ret})_{A'} = (x_{k}^{ret})_{B} \cup {J_{c}} \\ (x_{0}^{| M | + i})_{A'} = (x_{k}^{| M | + i})_{B} \end{matrix}

(12)

Local criterion definition

Based on preliminary analysis of problem, the form and modification the local optimization task could be defined. The analysis gives the following information: the number of tasks with deadline, the earliest due date and the latest deadline, and maximum and minimum size of elements in the task. As a result of this analysis, the local criterion takes into account the part defined by A* strategy, the change of global criterion Q resulting from making this decision and estimated value global criterion for the rest part of the trajectory. Second part takes into consideration the restriction reflecting jobs due date. The third part deals with preference of certain types of decisions. We would like to perform job containing the greatest number of elements or job with shortest processing time (in accordance with the SPT principle of the priority job scheduling) first. Finally, local criterion has following components

\begin{matrix} q (u, x, t)' = Δ Q (u, x, t) + \hat{Q} (u, x, t) + a_{1} α_{1} (u, x, t) \\ + b_{1} β_{1} (u, x, t) + b_{2} β_{2} (u, x, t) \end{matrix}

(13)

where

$Δ Q (u, x, t)$ denotes the increase in time as a result of realizing decision u taken in the state $s = (x, t)$ ;

$\hat{Q} (u, x, t)$ is an estimation of the time for the final trajectory section after the decision u has been realized and is calculated as the average value of the minimum time to complete for the unfinished jobs (time to complete performing on current machine and total processing time for the rest machines in technological route). The estimation should take place with the lowest number of calculations, so there has been proposed relaxation which omits temporal limitations (due date, if it is required for the considered jobs) and stoppages (job waiting time for performance in store between machines is not known in advance. Because additional knowledge or historical data is required, stoppages are not estimated. Such estimation unnecessarily increases the complexity). Moreover, breaks in job performing are not mentioned in considered problem;

$α (u, x, t)$ is connected with the necessity for the trajectory to omit the states of set $S_{N}$ , including states in which job due date is overdue. It is defined by means of semimetrics. Because non-admissible state omitting consists in task time requirements filling, the slack time $z_{j}$ for each not realized and not assigned job j with due date $d (j)$ is calculated. The j-th job slack time determines how much time is actually to job deadline and it is equal to the difference $z_{j} = d (j) - t$ . Because we do not want to make a decision causing job overdue, $\infty$ is assumed in that case. Moreover, we want to obtain a state most distant from the set of non-admissible states, including states when some non-realized jobs with due date are overdue. Thus, we consider average value of slack time in current state. Finally, component $α_{1} (u, x, t)$ is as follow (JN denotes a set of non-realized jobs).

α_{1} (u, x, t) = {\begin{matrix} \frac{\sum_{j \in JN} \frac{1}{z_{j}}}{| JN |} & for z_{j} > 0 & j \in JN \\ 0 & for z_{j} = 0 & j \in JN \\ \infty & for z_{j} < 0 & j \in JN \end{matrix}

(14)

$β_{1} (u, x, t)$ and $β_{2} (u, x, t)$ are components responsible for the preference of certain types of decisions.

• $β_{1}$ is related to the preference decision, the result of which jobs with the greatest number of elements are performed first. Because the decision is taken collectively for all machines, we take into account the average value of the considered jobs size. The smaller the total size, the greater the penalty charged. As a consequence, $β_{1} (u, x, t)$ is inversely proportional to the sum of the size of jobs to perform the considered decision.

• $β_{2}$ is related to the preference decision, the result of which jobs with the shortest processing time are performed first. Because the decision is taken collectively for all machines, we consider the average value of the considered jobs processing time. The longer the total time, the greater the punishment. Thus, $β_{2} (u, x, t)$ is proportional to the sum of the processing time of jobs to perform in considered decision.

In the course of trajectory generation, the local optimization task may be modified. Problem analysis reveals that the moment of all tasks with deadline are already finished, it is no longer necessary to apply the component $α (u, x, t)$ in the local criterion.

A schema of hybrid algorithm for flow-shop with defects is presented in Figure 3. The steps of hybrid algorithm for flow-shop system with deadline and defect removal are as follows. The process starts with initial state $(s_{0})_{A}$ and model ALM for problem without defects (denoted as $AL M_{A}$ ) is used. Until any quality defect has not been detected on machine with quality control, each next state depends on the previous state and the decision taken at that state. The decision is chosen from possible decisions which can be taken at the given state, using the adaptive local criterion (according to equation (13)). This state is checked in respect of belonging to set of the non-admissible state or the goal state. If quality defect is not detected, the new state of process is generated. When a quality defect is detected, the switching ALM model method is used in the nearest next process state $(s_{k})_{A}$ . The current algebraic-logical model $AL M_{A}$ is switched to model $AL M_{B}$ with additional repairing machine. Then, the switching function calculates the initial state $(s_{0})_{B}$ in $AL M_{B}$ model based on the result of the quality control (division of job with quality defect) and the current state of the manufacturing process represented by $(s_{k})_{A}$ of current $AL M_{A}$ model. Then, next states are calculated using the local criterion. This state is checked in respect of belonging: first to set of the non-admissible state and second to set of switching states.

Figure 3.

Hybrid algorithm.

In the case of new quality defect detection, the further switching of ALM models takes place. The current version of the model with additional repairing machine is recalculated using switching function. We use the model $AL M_{B'}$ , and the initial state $(s_{0})_{B}$ is calculated based on the result of the quality control (division of job with quality defect) and the current state of the manufacturing process represented by $(s_{k})_{B}$ of current $AL M_{B}$ model. In the case of occurrence of the next defect detection or completion of repair, subsequent switching and calculation of parameter values in the model $AL M_{B}$ type happens. There is a switching to the basic type of model without disturbances but with recalculated parameters $AL M_{A'}$ when the last defected job has been repaired. The next states are generated according to the above steps, that is, until there is no defect, we use the model type $AL M_{A}$ , and in the case of a quality defect detection, the switching to the model type $AL M_{B}$ takes place. Generation of the state sequence is terminated if the new state is a goal state, a non-admissible state, or state with an empty set of possible decisions.

Experiments and results

The effectiveness of the searching algorithm with the special local criterion has been used to solve some problems of parallel scheduling and verified by simulation experiments many times.^31,33,34 For the flow shop scheduling problem with defect removal we have tested heuristic algorithm, which is very intuitive and consistent with the considered problem assumptions. Thus, the purpose of the simulation experiments is to verify the effectiveness of the algorithm knowing that the time to find a solution by the algorithm is short.

The proposed solution of the aforementioned problem has been implemented in C# as authoring software program. The simulation experiments run on an Intel CoreTM i5-4210U CPU 2.40 GHz (16 GB RAM).

In the paper,³ we have tested how the combination of the switching method and searching algorithm works. Thus, first, we have tested how expensive it is to switch one model to another model. Next, we have studied how number of defect repairs influences to all jobs execution time and the number of switching between models. Based on these experiments, we have deduced that more economical is to switch between models than considering only one model the maximum model (with machine repair). It should be emphasized that the time of checking of defect occurrence or checking whether the repair machine has completed repairing is calculated in computation time of switching procedure. Thus, the purpose of the simulation experiments is to verify the effectiveness of the heuristic algorithm knowing that the computational time is short.

These studies on the effectiveness of the algorithm have compared the results obtained with the reference solutions of the problem of flow-shop: ta001, ta002, and ta024.³⁷ We have calculated for each problem a result (denoted as $C_{\max}$ ), number of simulation states, computational time, and relative error between obtained result and best known result for the problem. The results are shown in Table 1.

Table 1.

Results of experiments for p = 0 and known instances.

No. of machines	5	5	20
No. of jobs	20	20	20
Name of instances	ta001	ta002	ta024
Execution time	1297	1366	2274
Number of states	100	98	196
Computation time (ms)	241	2136	446
Best known result	1278	1359	2223
Relative error (%)	1.48	0.52	2.29

In spite of the fact that the heuristic algorithm is simple, the obtained results are worse than the best solution by approximate 2.

We have also tested several settings of the algorithm (values of parameters $a_{1}, b_{1}, and b_{2}$ ) for the proposed problem of flow-shop with defect. We have studied a few cases of the probability of defects occurrence $(p \in {0; 0.2; 0.5})$ for three sizes of the flow-shop problem: 20 jobs and 5 machines, 20 jobs and 10 machines, and 50 jobs and 10 machines. For each setting, we have done a simulation experiment several times and we have calculated average value of makespan (denoted in tables of results as Average $C_{\max}$ ), deviation of makespan (denoted as Deviation $C_{\max}$ ), and average of number of simulation states and average of computational time. The results are shown in Tables 2 –4.

Table 2.

Results of experiments for $p = 0$ and instances of problem.

No. of machines	5	5	5	5	10	10	10	10	10	10	10	10
No. of jobs	20	20	20	20	20	20	20	20	50	50	50	50
Value of $a_{1}, b_{1}, c_{1}$	$\frac{1}{3}, \frac{1}{3}, \frac{1}{3}$	$0, \frac{1}{2}, \frac{1}{2}$	0, 0, 1	0, 1, 0	$\frac{1}{3}, \frac{1}{3}, \frac{1}{3}$	$0, \frac{1}{2}, \frac{1}{2}$	0, 0, 1	0, 1, 0	$\frac{1}{3}, \frac{1}{3}, \frac{1}{3}$	$0, \frac{1}{2}, \frac{1}{2}$	0, 0, 1	0, 1, 0
$C_{\max}$	2198	2198	2198	2219	2606	2606	2606	2610	5583	5583	5583	5574
No. of states	82	82	82	82	182	182	182	182	436	436	436	450
Time (ms)	176	167	170	171	346	331	335	337	2922	2731	2916	2694

Table 3.

Results of experiments for $p = 0.2$ and instances of problem.

No. of machines	5	5	5	5	10	10	10	10	10	10	10	10
No. of jobs	20	20	20	20	20	20	20	20	50	50	50	50
Value of $a_{1}, b_{1}, b_{2}$	$\frac{1}{3}, \frac{1}{3}, \frac{1}{3}$	$0, \frac{1}{2}, \frac{1}{2}$	0, 0, 1	0, 1, 0	$\frac{1}{3}, \frac{1}{3}, \frac{1}{3}$	$0, \frac{1}{2}, \frac{1}{2}$	0, 0, 1	0, 1, 0	$\frac{1}{3}, \frac{1}{3}, \frac{1}{3}$	$0, \frac{1}{2}, \frac{1}{2}$	0, 0, 1	0, 1, 0
Average $C_{\max}$	2350	2309	2386	2346	2656	2616	2614	2624	5633	5631	5645	5584
Deviation $C_{\max}$ (%)	1.91	1.88	2.11	1.73	1.69	1.83	1.81	1.93	1.98	1.94	1.57	1.89
Average no. of states	115	109	117	124	215	206	207	210	527	526	536	522
Average time (ms)	176	167	170	171	327	335	267	315	3320	3065	3197	3184

Table 4.

Results of experiments for $p = 0.5$ and instances of problem.

No. of machines	5	5	5	5	10	10	10	10	10	10	10	10
No. of jobs	20	20	20	20	20	20	20	20	50	50	50	50
Value of $a_{1}, b_{1}, b_{2}$	$\frac{1}{3}, \frac{1}{3}, \frac{1}{3}$	$0, \frac{1}{2}, \frac{1}{2}$	0, 0, 1	0, 1, 0	$\frac{1}{3}, \frac{1}{3}, \frac{1}{3}$	$0, \frac{1}{2}, \frac{1}{2}$	0, 0, 1	0, 1, 0	$\frac{1}{3}, \frac{1}{3}, \frac{1}{3}$	$0, \frac{1}{2}, \frac{1}{2}$	0, 0, 1	0, 1, 0
Average $C_{\max}$	3182	2836	2768	2789	3368	3270	3362	3098	6404	6422	6334	6339
Deviation $C_{\max}$ (%)	1.87	1.74	2.07	1.89	1.98	2.22	2.54	2.29	2.13	2.11	2.37	2.00
Average no. of states	271	207	229	173	483	496	505	500	961	994	903	927
Average time (ms)	417	330	365	325	698	672	702	687	4957	4641	5059	5116

It can be seen that the deviation of makespan for each size of problem is small (approximately 2%), which means that the algorithm is stable. Although there is no guarantee to find optimal solutions, the computational time is very short.

Conclusion

The article presents a hybrid algorithm for solving manufacturing problem and its application to flow-shop problem, where manufacturing defects are removed to re-treatment as a result of the quality control. This algorithm is based on ALMM paradigm proposed by E Dudek-Dyduch. We have shown that hybrid algorithm can be successfully applied to problems with unexpected events occurring during manufacturing process. Especially, occurrence of quality defect is taken into consideration. What distinguishes this approach from the stochastic scheduling is the possibility of modeling the decision-making process contented with assignment of the tasks with defect to repair. We are convinced that the presented algorithm can be used in other similar problems.

Future efforts will focus on comparative research between stochastic methods and considered approach, using more complex heuristic algorithm as well as on application of our hybrid algorithm in other classes of problems.

Footnotes

Acknowledgements

The authors thank the anonymous referees for providing detailed comments and suggestions for improvements.

Academic Editor: Wu Naiqi

Declaration of conflicting interests

The author(s) declared no potential conflicts of interest with respect to the research, authorship, and/or publication of this article.

Funding

The author(s) disclosed receipt of the following financial support for the research, authorship, and/or publication of this article.

References

Grobler-Dębska

Kucharska

Dudek-Dyduch

. Idea of switching algebraic-logical models in flow-shop scheduling problem with defects. In: Proceedings of the 18th international conference on methods and models in automation and robotics (MMAR), Międzyzdroje, 26–29 August 2013, pp.532–537. New York: IEEE.

Grobler-Dębska

Kucharska

Jagodziński

. ALMM-based switching method for FSS problem with defects. In: Proceedings of the 19th international conference on methods and models in automation and robotics (MMAR), Międzyzdroje, 2–5 September 2014, pp.814–819. New York: IEEE.

Kucharska

Grobler-Dębska

Rączka

. ALMM-based methods for optimization makespan flow-shop problem with defects. In: Borzemski

Grzech

Świątek

. (eds) Information systems architecture and technology: proceedings of 37th international conference on information systems architecture and technology (ISAT 2016)—part I. Cham: Springer-Verlag, 2017, pp.41–53.

Dudek-Dyduch

Modeling manufacturing processes with disturbances—a new method based on algebraic-logical meta-models. In: Rutkowski

Korytkowski

Scherer

. (eds) Lecture notes in artificial intelligence, vol. 9120. Cham: Springer-Verlag, 2015, pp.353–363.

Dudek-Dyduch

. Modeling manufacturing processes with disturbances—two-stage AL model transformation method. In: Proceedings of the 20th international conference on methods and models in automation and robotics (MMAR), Międzyzdroje, 24–27 August 2015, pp.782–787. New York: IEEE.

Brucker

Scheduling algorithms, vol. 3. Berlin, Heidelberg: Springer-Verlag, 2007.

Gawiejnowicz

Time-dependent scheduling. Berlin, Heidelberg: Springer-Verlag, 2008.

Jarboui

Siarry

Teghem

Metaheuristics for production scheduling. Hoboken, NJ: Wiley Online Library, 2013.

Kwiecień

Filipowicz

Comparison of firefly and cockroach algorithms in selected discrete and combinatorial problems. Bull Polish Acad Sci Tech Sci 2014; 62: 797–804.

10.

Tajbakhsh

Fattahi

Behnamian

Multi-objective assembly permutation flow shop scheduling problem: a mathematical model and a meta-heuristic algorithm. J Oper Res Soc 2014; 65: 1580–1592.

11.

Eskandari

Hosseinzadeh

A variable neighbourhood search for hybrid flow-shop scheduling problem with rework and set-up times. J Oper Res Soc 2014; 65: 1221–1231.

12.

Seredyński

Zomaya

AY.

Sequential and parallel cellular automata-based scheduling algorithms. IEEE T Parall Distr 2002; 13: 1009–1023.

13.

Świecicka

Seredyński

Cellular automata approach to scheduling problem. In: Proceedings of the 2000 international conference on parallel computing in electrical engineering (PARELEC 2000), Trois-Rivieres, QC, Canada, 27–30 August 2000, pp.29–33. New York: IEEE.

14.

Świecicka

Seredyński

Zomaya

AY.

Multiprocessor scheduling and rescheduling with use of cellular automata and artificial immune system support. IEEE T Parall Distr 2006; 17: 253–262.

15.

Vidica

de Oliveira

GMB

. Cellular automata-based scheduling: a new approach to improve generalization ability of evolved rules. In: Proceedings of the ninth Brazilian symposium on neural networks, 2006 (SBRN’06), 23–27 October 2006, pp.18–23. New York: IEEE.

16.

Draa

Meshoul

. A quantum inspired learning cellular automaton for solving the travelling salesman problem. In: Proceedings of the 2010 12th international conference on computer modelling and simulation (UKSim), Cambridge, 24–26 March 2010, pp.45–50. New York: IEEE.

17.

Abdolzadeh

Rashidi

An approach of cellular learning automata to job shop scheduling problem. Int J Simulat Syst Sci Tech 2010; 34: 391–401.

18.

Antczak

Witkowski

. Using of evolving cellular automata for flexible job shop with makespan criterion. In: Proceedings of the 2009 IEEE international workshop on intelligent data acquisition and advanced computing systems: technology and applications (IDAACS 2009), Rende, 21–23 September 2009, pp.297–302. New York: IEEE.

19.

Baptiste

Le Pape

Nuijten

Constraint-based scheduling: applying constraint programming to scheduling problems, vol. 39. New York: Springer Science+Business Media, 2012.

20.

Rossi

Van Beek

Walsh

(eds) Handbook of constraint programming. Elsevier, 2006, http://cswww.essex.ac.uk/CSP/papers/CP_Handbook-20060315-final.pdf

21.

Rousseau

. One problem, two structures, six solvers, and ten years of personnel scheduling. In: O’Sullivan

(ed.) Principles and practice of constraint programming. Cham: Springer-Verlag, 2014, pp.4–5.

22.

Almeder

Hartl

RF.

A metaheuristic optimization approach for a real-world stochastic flexible flow shop problem with limited buffer. Int J Prod Econ 2013; 145: 88–95.

23.

Aytug

Lawley

MA.

Executing production schedules in the face of uncertainties: a review and some future directions. Eur J Oper Res 2005; 161: 86–110.

24.

Choi

Wang

Flexible flow shop scheduling with stochastic processing times: a decomposition-based approach. Comput Ind Eng 2012; 63: 362–373.

25.

Pinedo

Scheduling: theory, algorithms, and systems. Upper Saddle River, NJ: Prentice Hall, 1995.

26.

Shabtay

The just-in-time scheduling problem in a flow-shop scheduling. Eur J Oper Res 2012; 216: 521–532.

27.

Billio

Ferrara

Guegan

. Evaluation of regime switching models for real-time business cycle analysis of the euro area. J Forecasting 2013; 32: 577–586.

28.

Hamilton

JD.

Regime-switching models. In: Durlauf

Blume

(eds) Palgrave dictionary of economics. Hampshire: Palgrave Macmillan, 2005.

29.

Yin

Krishnamurthy

Regime switching stochastic approximation algorithm with application to adaptive discrete stochastic optimization. Ind Appl Math 2004; 14: 1187–1215.

30.

Dudek-Dyduch

Formalization and analysis of problems of discrete manufacturing processes, vol. 54. Krakow: Automatics, Scientific Bulletin of AGH University, 1990 (in Polish).

31.

Dudek-Dyduch

Learning based algorithm in scheduling. J Intell Manuf 2000; 11: 135–143.

32.

Dudek-Dyduch

Algebraic logical meta-model of decision processes—new metaheuristics. In: Rutkowski

Korytkowski

Scherer

. (eds) Lecture notes in computer science, vol. 9119. Berlin, Heidelberg: Springer-Verlag, 2015, pp.541–554.

33.

Dudek-Dyduch

Kucharska

Learning method for co-operation. In: Jȩdrzejowicz

Nguyen

Hoang

(eds) Lecture notes in computer science, vol. 6923. Berlin, Heidelberg: Springer-Verlag, 2011, pp.290–300.

34.

Kucharska

Dudek-Dyduch

Extended learning method for designation of co-operation. In: Nguyen

(ed.) Lecture notes in computer science, vol. 8615. Berlin, Heidelberg: Springer-Verlag, 2014, pp.136–157.

35.

Dudek-Dyduch

Dutkiewicz

Substitution tasks method for discrete optimization. In: Rutkowski

Korytkowski

Scherer

. (eds) Lecture notes in artificial intelligence, vol. 7895. Berlin, Heidelberg: Springer-Verlag, 2013, pp.419–430.

36.

Sękowski

Dudek-Dyduch

Knowledge based model for scheduling in failure modes. In: Lecture notes in computer science, vol. 7268. Berlin, Heidelberg: Springer-Verlag, 2012, pp.591–599.

37.

http://mistic.heig-vd.ch/taillard/problemes.dir/ordonnancement.dir/flowshop.dir/tai20_5.txt

Algebraic-logical meta-model based approach for scheduling manufacturing problem with defects removal

Abstract

Keywords

Introduction

Motivation and background

Flow-shop system with defects problem

ALMM approach for MDP

ALMM-based hybrid algorithm

Searching algorithm with the special local criterion

Local optimization of decision choice

Local optimization criterion modification

ALM switching method

General hybrid algorithm procedure

Algorithm for flow-shop system with defects

Analysis of the problem

Set of switching states

Distribution of problem for subproblems

ALM models for all subproblems

Algebraic-logical model of flow-shop system with time limits

State of system

Decisions

Transition function f A

Algebraic-logical model of flow-shop system with repairing machine

State of system

Decisions

Transition function

Types of switching

The switching function

Local criterion definition

Experiments and results

Conclusion

Footnotes

Acknowledgements

Declaration of conflicting interests

Funding

References

Transition function $f_{A}$