Keywords

1 Introduction

A hybrid flow shop scheduling (HFSS) problem in a paint company is examined in this study. In the existing system, customer orders are planned based on experiences of the production planning department using MS Excel. Since customer orders are scheduled manually, time loss and mistakes occur. This situation causes uncertain production capacity, delay or early production of jobs, and accumulation of the products in the warehouse. Therefore, a user-friendly optimization tool for optimal scheduling of customer orders based on scientific methods is required.

In the context of this study, we aim to develop a tool for finding the optimal schedule for the production system to minimize the sum of tardiness and earliness of jobs. For this purpose, the symptoms are analyzed, and the appropriate mathematical model is developed. The developed mathematical model is solved with different job sizes using IBM ILOG CPLEX Optimization Studio Version 12.6.3 [1]. The problem is found to be NP-hard [2]. Therefore, a heuristic approach is decided to employ for solving larger job sizes. As a result of the comprehensive literature review, it is determined that the genetic algorithm (GA) gives the best solution for the HFSS problem [3]. Considering the constraints of the problem environment, a GA model, that assigns jobs to the relevant machines and gives the optimal production sequence as an output, is developed. The proposed model is solved and verified using toy problems which include five jobs. In addition to this, GA is employed for the solution of toy problems and verified. At last, the obtained solution method is integrated into a user-friendly decision support system (DSS).

2 Problem Definition

The data used in this study are collected from a paint company, which is agreed to deliver incoming orders within three days to the customers. The company implements both make-to-order and make-to-stock production strategies. The company produces 40% of incoming customer orders instantly and the remaining 60% is supplied from stock. The production continues for stock when the inventory falls below the desired level.

There are two kinds of production systems in the company; the co-grind system and the paste system. In the co-grind production system, there are five stages and one process at each stage. These are pre-mixing, grinding, sub-addition, quality control, and filling. Pre-mixing and grinding processes have machine capacity limitations. The second production system which is the paste system consists of only sub-addition, quality control, and filling processes. In the production system of the company, some machines in some operations are parallel, and these machines can be identical or unrelated. Also, each machine can process exactly one job at a time. Likewise, each job can be processed on exactly one machine in each operation. The flow of the process is the same for all jobs, but they may skip some processes. Besides, when the process starts, it cannot be interrupted. The literature review showed that the company’s production environment can be classified as a hybrid flow shop (HFS) production system and the scheduling problem can be classified as an HFSS problem. HFS consists of a flow line with several identical and unrelated parallel machines on some or all production stages. Multiple products are produced in such a flow line. While all the products follow the same linear path through the system, all of them may not visit all of the stages in production. On each of the stages, one of the parallel machines has to be selected for the production of a given product. The production of a product consists of multiple operations, one for each production stage. When an operation is started on a machine, it must be finished without interruption [4].

The scheduling of customer job orders according to their earliest due date (EDD) is studied in this paper. Flexibility is considered for special situations such as color transitions, rework, and instantaneous orders in scheduling. The objective is to minimize the sum of earliness and tardiness of the jobs. Ensuring on-time delivery of jobs is important for the company’s reputation and customer satisfaction. As a result of the determined schedule, the progress of the job orders at any time can also be observed. Besides, the company’s production capacity can be displayed through a systematic schedule using the DSS.

3 Literature Review

Scheduling is one of the problems that we encounter in many areas in life, which is about assigning and sorting jobs to machines considering the time factor [2]. This problem is important in manufacturing systems to ensure that orders are produced by their due date. The production environment of the company studied is classified as an HFS production system and the scheduling problem can be classified as an HFSS problem. The HFSS is a complex combinatorial problem with multiple parallel machines for some stages in many real-world applications [5].

According to Chung et al. [6] flow shop scheduling problem is NP-hard when there are m machines and n jobs and the aim is to minimize total tardiness. Flow shop scheduling problems become more complex for multi-objective optimization models since multiple targets must be evaluated simultaneously [7]. The studies showed that as the number of jobs and machines increase, the mathematical model did not provide the optimal solution. Therefore, it is decided to use a heuristic algorithm that provides Solutions that are good and fast enough for large scale problems.

In the articles examined, taboo search, genetic algorithm, simulated annealing was studied for the flow shop scheduling problem, and comparisons were made between the algorithms. As a result, it has been observed that the GA gives the fastest and most effective solution to large-scale problems [8]. According to Alcan and Başligil [9], the GA is a method of searching and optimizing job schedules in a similar way to the evolutionary process observed in nature. At the same time, it is based on a random search, like all heuristic approaches. It looks for the best heuristic solution according to the principle of survival of the best in complex multi-dimensional search space. Based on these articles examined, it was decided that the optimum result could be obtained with GA for our problem and a heuristic model was developed using this approach.

4 Modeling and Solution Methodology

The mathematical model and GA metaheuristic method are developed for the HFSS problem. The developed mathematical model and GA are shown in this section.

4.1 Limitations and Assumptions

Limitations and assumptions are significant for the HFSS problem. The reason is that these factors can directly affect problem solutions. The assumptions of the study are listed below.

  • All machines are available at time t = 0.

  • All jobs are available at time t = 0.

  • The setup and transportation time are included in the processing time.

  • There is no machine failure which means that machines are available for processing continuously.

  • The idle time of the machine is negligible.

  • No preemption of operations is allowed.

  • The number of operators is assumed to be adequate.

  • There are no scrap products for reworked parts. These products are stored to be used in the next orders.

4.2 Mathematical Model

Indices and sets are defined before creating the mathematical model. The indices are i, j, l, and k. Indices i and j represent jobs, l represents the index for stages and k represents the index for machines at stages l. The parameters and variables of the model are identified below.

Indices, Sets, Parameters

n :

# of jobs

m :

# of operations

i :

j, index for jobs

k :

index for operations

M k :

number of machines at stage k

l :

index for machines at stage k (where 1…Mk)

P ik :

processing time of job i at stage k on machine l

O k :

the set of jobs to be processed at stage k

d i :

due date of job i

v i :

the amount(kilogram) of job i

N l :

the capacity of machine l at pre-mixing operation

W l :

the capacity of machine l at grinding operation

  • Decision Variables

  • \( C_{i } = \) Completion time of job i

  • \( E_{i} = \) Earliness of job i

  • \( T_{i} = \) Tardiness of job i

  • \( S_{ikl} = \) Starting time of job i at stage k on machine l

  • \( Y_{ijkl} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {{\text{if}}\, {\text{job}}\, {\text{j}}\, {\text{is}}\, {\text{processed}}\, {\text{immediately}}\, {\text{after}}\, {\text{job}}\, {\text{i }}\,{\text{at}}\, {\text{stage}}\, {\text{k}}\, {\text{on}}\, {\text{machine}}\, {\text{l}}} \hfill \\ {0, } \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. \)

  • \( X_{ikl} = \left\{ {\begin{array}{*{20}l} {1,} \hfill & {{\text{if}}\, {\text{job}}\, {\text{i}}\, {\text{is }}\,{\text{processed}}\, {\text{at }}\,{\text{stage}}\, {\text{k}}\, {\text{on}}\, {\text{machine}}\, {\text{l}}} \hfill \\ 0 \hfill & {\text{otherwise}} \hfill \\ \end{array} } \right. \)

Mathematical Model

Minimize

$$ \mathop \sum \limits_{i = 1}^{n} \left( {E_{i} + T_{i} } \right) $$
(1)

Subject to:

$$ \begin{array}{*{20}l} {C_{i } = \mathop \sum \limits_{k = 1}^{m} \mathop \sum \limits_{l = 1}^{{M_{k} }} (S_{ikl} + P_{ikl} . X_{ikl} )} \hfill & {\forall i} \hfill \\ \end{array} $$
(2)
$$ \begin{array}{*{20}c} {S_{ikl} \le M \left( {X_{ikl} } \right)} & {\forall i \in O_{k} , k, l} \\ \end{array} $$
(3)
$$ \begin{array}{*{20}c} {\mathop \sum \limits_{l = 1}^{{M_{k} }} X_{ikl} = 1} & {\forall i \in O_{k} ,l} \\ \end{array} $$
(4)
$$ \begin{array}{*{20}c} {T_{i} \ge C_{i} - d_{i} } & {\forall i} \\ \end{array} $$
(5)
$$ \begin{array}{*{20}c} {E_{i} \ge d_{i} - C_{i} } & {\forall i} \\ \end{array} $$
(6)
$$ \begin{array}{*{20}c} {S_{ikl} \ge S_{jkl} + P_{jkl} - M.y_{ijkl} - M.\left( {1 - x_{jkl} } \right) - M.\left( {1 - x_{ikl} } \right)} & {\forall {\text{j }}, {\text{i}} \ne {\text{j }}, {\text{k }},{\text{l}}} \\ \end{array} $$
(7)
$$ \begin{array}{*{20}c} {X_{ikl } + X_{jkl } \ge 2 \left( {Y_{ijkl} + Y_{jikl } } \right)} & {\forall {\text{j }}, {\text{i}} \ne {\text{j }}, {\text{k }},{\text{l}}} \\ \end{array} $$
(8)
$$ \begin{array}{*{20}c} {X_{ikl } + X_{jkl } \le Y_{ijkl} + Y_{jikl } + 1} & {\forall {\text{j }}, {\text{i}} \ne {\text{j }}, {\text{k }},{\text{l}}} \\ \end{array} $$
(9)
$$ \begin{array}{*{20}c} {\mathop \sum \limits_{l = 1}^{{M_{k} }} S_{ikl} \ge \mathop \sum \limits_{l = 1}^{{M_{k - 1} }} S_{ik - 1l} + P_{ik - 1l} } & {\forall i,l > 1} \\ \end{array} $$
(10)
$$ \begin{array}{*{20}c} {v_{i} . X_{i1l} \le N_{L} } & {\forall i \in O_{k} , k, l} \\ \end{array} $$
(11)
$$ \begin{array}{*{20}c} {v_{i} . X_{i2l} \le W_{L} } & {\forall i \in O_{k} , k, l} \\ \end{array} $$
(12)
$$ \begin{array}{*{20}c} {S_{ikl} \ge 0} & {\forall i, k,l} \\ \end{array} $$
(13)
$$ \begin{array}{*{20}c} {C_{i} \ge 0} & {\forall i} \\ \end{array} $$
(14)
$$ \begin{array}{*{20}c} {x_{ikl} \in \left\{ {0,1} \right\}} & {\forall i \in O_{k} ,k,l} \\ \end{array} $$
(15)
$$ \begin{array}{*{20}c} {y_{ikl} \in \left\{ {0,1} \right\}} & {\forall (i,{\text{j}}) \in O_{k} ,k,l} \\ \end{array} $$
(16)
$$ \begin{array}{*{20}c} {T_{i } \ge 0} & {\forall i} \\ \end{array} $$
(17)
$$ \begin{array}{*{20}c} {E_{i } \ge 0} & {\forall i} \\ \end{array} $$
(18)

In this model, the objective function minimizes the sum of the earliness and tardiness of all jobs (1). Constraint (2) calculates the total completion time of all jobs from the first stage to the last stage. Constraint (3) forces that the starting time of each job on machines that do not process the job becomes 0. Constraint (4) specifies job assignments to machines at each stage. Constraint (5) calculates the tardiness of all jobs. Constraint (6) calculates the earliness of all jobs. Constraint (7) controls the completion time of each pair of jobs if they are processed by the same machine at each stage. Constraint sets (8) and (9) show the relationship between decision variables X and Y. Constraint (10) guarantees that the job on the next stage cannot start before it is completed on the previous stage. Constraint (11) provides that according to the weight of all jobs should be assigned to the appropriate machine of the first stage. Constraint (12) provides that according to the weight of all jobs should be assigned to the appropriate machine of the second stage. Finally, Constraint (13), (14), (15), (16), (17), and (18) define the boundaries of decision variables.

The developed mathematical model is solved with IBM ILOG CPLEX Optimization Studio using the real data which are collected from the factory for 3, 5, 7 and 10 job sizes. The solutions and computational time of these different job sizes are shown in Table 1 for comparison.

Table 1. Comparison for different job order scenarios
Full size table

As can be seen in Table 1, the computational time of the mathematical model increases as the number of jobs increase. When the number of jobs is 3, the computational time is 0.6 s. On the other hand, when the number of jobs is 10, the computational time takes about 30 h which is not practical to use in a production environment that requires responding to the orders quickly. As a result, the problem gets harder to solve as the number of jobs increases, and this method remains inefficient for larger job sizes. For this reason, a heuristic algorithm is employed for the solution of larger problems.

4.3 Genetic Algorithm

Genetic Algorithm (GA) was developed by John Holland in 1965. Holland has adapted Darwin’s Theory of Evolution and the principle of “Survival of the fittest” to the process of optimization [10]. This heuristic approach aims to find the global optimum or close to global optimum solutions using the genetic code logic in the living systems. The theory of evolution has been successful in the optimization process and proposed a solution in many areas such as sorting, scheduling, assignment, planning, and transportation problems. The genetic algorithm flow adapted to our problem considering the proposed mathematical model and machine capacity constraints. Fitness function is the objective function of our mathematical model and the algorithm achieves the objective function value by assigning jobs in a sequence considering the model constraints. Solution representation is, in this case, the best order to assign jobs to the related machines. Co-grind and paste production system flow is constructed in the constraints and the algorithm distinct them from the product code and production time entered as the order input. The initial population is created depending on the number of jobs being scheduled. This type of coding is called “permutation encoding.” Every chromosome is a string of numbers and in that case, each string represents a job sequence. The number of jobs is represented with job ID and each job has a unique number. This ID represents the gene and a chromosome is represented by all the order ID’s that are being scheduled. With this coding system, a random initial population is created considering the number of jobs to be scheduled. The selection criterion used in this algorithm is fitness-based Elitism. When a child enters this operation, by far all generated chromosomes fitness values are calculated and the individuals with the highest fitness function value (least fit members) tend to be replaced by a better-fit child. For this reason, the fittest member of this population can not be replaced. If individuals with the same least fitness function value exist, the decision to remove which individual from the population is random. The population of selected and remaining individuals is considered as the new population. For the crossover operation, single-point, two-point and uniform methods are added into the algorithm. As a result of parameter analysis uniform crossover is selected as a crossover type. There is a 50% chance that an offspring will inherit the gene of Parent 1 and the same implies for Parent 2. In this way, the first offspring is created. Then for the second offspring, the genes are inherited from the exact opposite parent chosen to create the first offspring. To mutate an individual two positions on the chromosome are selected at random, and the values are interchanged. This type of mutation is called “swap mutation.” A mutated individual represents a new job sequence to be assigned to the machines for processing. If the child does not include all different genes, the number of iterations is increased, and the algorithm goes back to the crossover operator until all genes are different in the offspring. The termination criterion is determined as the number of the population entered before running the algorithm. When the termination criterion is satisfied, the chromosome which has the lowest fitness function value is given as the best result according to the algorithm.

5 Verification and Validation

The developed mathematical model is solved with toy data which included 5 jobs, using IBM ILOG CPLEX Optimization Studio. In the context of this study, the problem with small data sets is called a toy problem. Then, the same toy data are used to solve the scheduling problem manually and this result is compared with the results from IBM ILOG CPLEX Optimization Studio. Both solutions provide the same results and the model is verified. The 5 jobs sorted according to their earliest due date are 3–1–5–4–2, respectively. Then, these sorted jobs are assigned to the available machines in that operation according to the machine capacity constraints. Figure 1 demonstrates in which operations that the jobs are processed, to which machines the jobs are assigned, and the processing times of the jobs are displayed. Also, the completion time of jobs can be calculated through the Gantt Chart.

Fig. 1.
figure 1

Gantt chart for toy data

Full size image

Table 2 below shows the parameters of the toy problem and the results of the solution. The objective function value which is solved in 2.12 s with toy data of 5 jobs is 1930 min by using IBM ILOG CPLEX Optimization Studio.

Table 2. Calculation of objective function
Full size table

After verification of the model, the problem is solved using the real data obtained from the time study is used to validate the heuristic method. The solution is used to validate the proposed heuristic method. For the validation, we compared the outputs of two different programs which are IBM ILOG CPLEX Optimization Studio Version 12.6.3 and Excel Visual Basic for Applications (VBA) Version 16.37 [11]. These programs are run on a computer that has 16 GB RAM. The comparison is shown below in Table 3.

Table 3. Results by CPLEX and Heuristics
Full size table

Table 3 shows the results obtained by the calculation using IBM CPLEX and heuristic method with the same data for validation. CPLEX gave up the result until 10 jobs, it ran about 5 days for the solution of larger job sizes, then the program gave memory error and stopped. To explain briefly, the computational time is exponentially increased for 10 jobs in CPLEX and it fails to give results for larger problems. Therefore, we compared the results of the CPLEX and heuristic method up to 10 jobs. It can be seen that the heuristic algorithm returns nearly optimal solution when compared to the solution obtained by CPLEX. Since the factory has daily 20 orders on average, the genetic algorithm is chosen to solve this problem.

6 Decision Support System and Computational Results

A decision support system (DSS) is designed to show the most appropriate customer orders schedule. The designed DSS responds to changes made by the user instantly. This section consists of information about DSS in detail.

6.1 Decision Support System (DSS)

Decision Support System (DSS) is designed to help the user in the planning process. When designing DSS, it is considered to respond to changes made by the user instantly. With this dynamic system, scheduling can be easily made and help the production planning department on decision making.

There are five main pages which are “Welcome Page”, “Orders”, “Results”, “Gantt”, and “Learning Data”. “Welcome Page”, as shown in Fig. 2, includes buttons that execute three main operations namely data entry, solve, and result. In data entry operations, there are six buttons. The first button is “Add Order”. When clicked on this button, there are two options for data entry that asks for all input data. Inputs are either entered by the user or read from a file. These inputs are “Order ID”, “Portfolio Code”, “Color Code”, “Production Amount”, “Due Date”, and “Processing Times” of five different production operations. The entered inputs are written on the “Orders” page. The second button is “Change Order”. It asks the “Order ID” to be changed. The entered ID is kept fixed, but the other inputs can be changed. The third button is “Delete Order. This button helps to remove the desired input data of entered “Order ID”. The fourth button of the data entry operation is “Delete All Orders”. This button deletes all the input data on the “Orders” page. The solve operation has a run button that executes the Genetic Algorithm using entered input data on the “Orders” page. The last operation which is “Result” has three buttons. The first button which is “Show Results” opens the “Results” page that shows the sequence of the orders, assignments to the machine, and computational results. The second button is “Show Gantt.” When clicked to this button, it opens the “Gantt” page where the job schedule is visualized. The last button of this operation is “PDF Results”. This button reads the data on the “Results” page. Then, it converts them to a PDF file and saves this file to the desired location on the computer. Also, on the “Welcome Page,” there is a “Help” button that has a user’s manual. This user’s manual includes a detailed description of the operations.

Fig. 2.
figure 2

DSS welcome page

Full size image

On the “Orders” page, which is accessible by “Go to Orders Page” button, the parameters of the genetic algorithm are located. The parameters are population number, mutation probability, and crossover-type that can be changed manually. Also, process names, machine information, and machine capacity constraints are available. If there is a change in machine or operation number, they can also be updated manually. Also, the objective function and makespan of the solution are displayed under the parameters of GA. On the “Learning Data” page, which is accessible by “Learning Data” button, the data obtained from our time study is available. With these data, the processing times can also be calculated. When the portfolio code and production amount are entered as an order on the “Orders” page, recommended processing times are given. The processing times are calculated as the average of the obtained data with the same portfolio code and ±10% of the entered production amount. When all operations are completed, the result of scheduling is seen clearly and converted to a PDF file. This file can be e-mailed to the related departments to create systematic information flow. With this Decision Support System, weekly or monthly schedules can be created in short notice. This provides a systematic schedule for the company and decreases wasted time and errors occurred while manual scheduling.

6.2 Computational Results

The parameters of the genetic algorithm should be analyzed to find the parameters that give the best performance before the implementation of this algorithm. Population size must be large enough to include diverse chromosomes but on the contrary, when the population size exceeds a certain value the efficiency of the algorithm decreases. Therefore, parameter optimization is crucial for the performance of the genetic algorithm. In this study, for 15 job size and swap mutation type; population size, crossover-type, and mutation probability will be changed then the objective function will be compared to determine the parameters that give the best performance. The values obtained from this study are shown in Table 4 below.

Table 4. Parameter optimization for GA
Full size table

To compare the DSS schedule with the factory schedule the input values of 15 consecutive orders produced are asked from the factory. With the input data obtained from the recent production, the objective function and makespan are calculated. Then input data of produced 15 consecutive orders is solved by the Genetic Algorithm to achieve a better production sequence. Then objective function and makespan values are compared to see the improvement. Our objective function is to minimize the sum of earliness and tardiness of orders. When makespan is expanded within the due date of orders, the objective function is reduced. To illustrate the numerical results, with a 9.8% expansion of makespan, without exceeding the due date, 17.3% improvement of objective function value is obtained as shown in Table 5.

Table 5. Comparison of solutions with the initial conditions
Full size table

7 Conclusions and Future Work

In this study, a mathematical model and a genetic algorithm are developed, and a decision support system is designed for the customer order scheduling problem in the hybrid flow shop production environment. The problem is solved both with the proposed model and a heuristic algorithm that considers the proposed model. The company where this project is carried out in collaboration has two different production systems which are co-grind and paste production systems. Also, there are five operations namely pre-mixing, grinding, sub-addition, quality control, and filling processes in the production area.

Before the project, the customer order scheduling used by the company is generated based on experience without any systematic method. This situation caused using production time inefficiently, excess stock formation, customer dissatisfaction, lack of communication between departments, and undetermined production capacity. Besides, it could not possible to observe which stage the product is at any time. Because of these reasons, the company needed systematic scheduling.

In this study, it is aimed to generate efficient scheduling which shows jobs sequence and assignment to the machines. These sorting and assigning of jobs are scheduled by means that minimize the sum of earliness and tardiness.

At the end of the project, a suitable mathematical model is developed, and a heuristic method is proposed for solving larger job sizes. A user-friendly decision support system is created using Microsoft Excel Visual Basic for Applications (VBA) to remove the problems. Thus, a solution method has been generated that increases the efficiency, meets the demands of the company, and minimizes the total of the earliness and tardiness of the jobs.

As future work; if the company’s existing production system changes such as the number of machines, the number of processes, the new system can be updated on DSS. Thus, the company can easily reach new scheduling. Also, the stock levels can be integrated into the DSS to ease the planning process. Finally, the obtained schedule can be modified for the project-based productions of the company.