In the competitive global marketplace, production scheduling plays a vital role in planning in manufacturing. Scheduling deals directly with the time to output products quickly and with a low production cost. This research examines case study of a Radio-Frequency Identification labeling department at Avery Dennison. The main objective of the company is to have a method that allows for the sequencing and scheduling of a set of jobs so it can be completed on or before the customer’s due date to minimize the number of late orders. This study analyzes the flexible flow shop scheduling problem with a sequence dependent setup by modifying the processing time and setup time to minimize the makespan on multiple machines. Based on the defined mathematical model, this study includes an alternative approach and application of heuristic algorithm with the input being big data. Both optimization programs are used in this study and compared to determine which method can better solve the company’s problems. The proposed algorithm is able to improve machine utilization with large-scale problems.
Planning and scheduling play a vital role in the supply chain in the manufacturing and service industry. It encompasses allocated, limited resources, as well as the activities that must be accomplished [
There are two types of scheduling environment, flow shop and job shop scheduling. Job shop scheduling means jobs are assigned to resources with a specific time. The flow shop scheduling problem is one of the most popular scheduling environments. The classical flow shop scheduling problem (FSP) involves a set of “n” jobs that need to be processed in a set of “m” machines in series. However, real production systems are rarely applied to a single machine at each stage. Therefore, in many situations, instead of having a series of machines, production has a series of stages of parallel machines to increase capacity and reduce the impact of bottleneck which is called flexible flow shop (FFS) scheduling. In
The job shop is a manufacturer’s operation that specializes in low-to medium-volume production and utilizes job or batch processes. By contrast, the flow shop specializes in medium-to high-volume production and utilities line or continuous flow processes. This environment is more suitable and prevalent in Vietnam, particularly in clothing and labeling production. The characteristic of these industries is that product diversity is low, but the volume is high. This research focuses on the scheduling problem for FFS setups.
In manufacturing, production scheduling must be done every day to satisfy the customer’s order. Even though other production parameters, such as operators, maintenance, and inventory, are under control, the manufacturing company may lose its ability to satisfy the planned production volume. If a production line has no optimal production sequence, the completion time of the jobs will be long and variable. This situation can seriously affect the service level with customers. The company should have production back-up plans to overcome unexpected problems in the production environment, such as machine breakdowns. Therefore, optimal production sequences are essential to the success of any manufacturing company. In many industries, such as pharmaceutics, automobile, and printing manufacturing, there are setup times on the equipment between two different jobs. Usually, it is assumed that the setup time is a part of the job processing time. However, in many cases, the production process can consist of several jobs and each job must follow a specific sequence of steps. Each step is processed on a workstation, which includes several different machines, and changing one job to another on a machine can incur considerable setup time. The current problem is how to control setup times effectively that they do not impact the whole process. Furthermore, the complexity of the problem increases when the manufacturing process involves parallel machines in each station (
This study aims to develop a mathematical model to solve the scheduling problem of the FFS shop manufacturing system with a sequence-dependent setup time and develop a new approach for large size problems using the heuristic algorithm. A comparison of the two approaches is made using a case study to find the optimal solution, as well as the proper use cases of each method. The result of this research can be expanded and applied for similar scheduling problems in FFS manufacturing systems.
Cortes et al. [
Setup time can be defined as the time to prepare the necessary resources to perform a task. In a production system, reducing the setup time in flexible machines is an important task for better shop performance. The reduction of setup times cannot be effectively improved without the standardization of the set-up procedures. Allahverdi et al. [
Kim et al. [
Linear programming is a mathematical method that is used to determine the best possible outcome or solution from a given set of parameters or list of requirements, which are represented in the form of linear relationships. Other papers have established the mathematical model to cope with the production scheduling problems. Entrup et al. [
Heuristic methods do not necessarily need to be perfect. With large problems, they can speed up the process of reaching a satisfactory solution. Heuristics is a flexible technique for making quick decisions, particularly when working with complex data. As a trade-off, heuristics is incapable of finding the optimal or best solution.
In the literature, some studies addressed flow shop scheduling using a heuristic algorithm to minimize the earliness and tardiness costs [
The research graph (
In this stage, the information of the manufacturing process is collected, and the scheduling problem of the process is identified. Then, potential solutions are considered based on the literature.
In this stage, a mathematical model of the scheduling problem is developed. CPLEX programming is used to code and run to get the optimal solution. Due to the data problem size, it is challenging to enumerate all of the data. Therefore, in this research, the tuple approach is applied to handle this. As the result is displayed, to check the accuracy and suitability of model, a Gantt chart is defined to check the sequence, setup time, and processing time. From this, we also know which job is late and the gap between each process.
After testing the mathematical model at the previous stage, the result should satisfy all constraints that fit with the real case study. However, due to the size of data and computational time, the heuristic method should be clarified to give a better solution.
This step is to show the result of heuristic method after running the model. Then, the results are analyzed, and the two proposed methods compared to recommend a suitable solution for the company.
In a standard mathematical model of FFS scheduling, three indices should be included such as jobs, stations, and machines. The input data to run this model are the setup time, processing time, and due date of jobs. The output of the model is covered by these decision variables, including enabling the job on the machine, the sequence of the job, beginning time, finishing time and total number of late orders.
The indexes notations are as follows:
The set notations are as follows:
The parameter notations are as follows:
The decision variable notations are as follows:
The objective is to minimize the makespan to deliver goods to customers just-in-time in production systems.
The general form includes the following assumptions:
• Jobs are independent, and no priorities are assigned to any job type
• All jobs are available for processing at time zero
• Breakdowns are not considered
The formulas are as follows:
Minimize Cmax
Subject to:
With:
• The objective function minimizes the makespan
• Constraint (1) calculates the total late orders
• Constraint (2) defines the makespan which is the time to complete a job.
• Constraint (3) ensures that every job at one station is only assigned once
• Constraint (4) guarantees that the finishing time of job i must be greater than sum of the beginning time and processing time
• Constraint (5) clarifies that for each job, the job must satisfy the workstation sequence constraint. Particularly, the beginning of job k would be after the job before it is done.
• Constraints (6), (7), (8) describe that only one of two job i and j is assigned on machine m and processed before the other.
• Constraint (9) ensures that the beginning of job j would be after that of job i including the processing time and setup time for job i.
• Constraint (10), (11) identify the lateness of order. One order is late if finishing time of job i at station a is larger than its due date.
To validate the FFS model, we used a small sample dataset to test the accuracy of the model of a setup time constraints and processing time constraints. There are three objects that have been taken into consideration for execution, which are the jobs, machines, and stations in process to complete orders. The structure of the data is given in
Number of Jobs | 5 |
---|---|
Number of Stations | 3 |
Number of Machines | 8 |
There are five jobs in the system; each job must be processed through all three stations and by sequence to finish task. To be more specific, the relationship of the job and station is defined in
Job | preStation | sucStation |
---|---|---|
1 | 1 | 2 |
1 | 2 | 3 |
2 | 1 | 2 |
2 | 2 | 3 |
3 | 1 | 2 |
3 | 2 | 3 |
4 | 1 | 2 |
4 | 2 | 3 |
5 | 1 | 2 |
5 | 2 | 3 |
Each workstation has several machines. As shown in
Machine | Station |
---|---|
1 | 1 |
2 | 1 |
3 | 1 |
4 | 2 |
5 | 2 |
6 | 2 |
7 | 3 |
8 | 3 |
Job | Last Station | Due date |
---|---|---|
1 | 3 | 20 |
2 | 3 | 16 |
3 | 3 | 10 |
4 | 3 | 25 |
5 | 3 | 30 |
Job | Machine | Processing time slot |
---|---|---|
1 | 1 | 3 |
1 | 2 | 2 |
1 | 3 | 6 |
1 | 4 | 7 |
1 | 5 | 5 |
1 | 6 | 2 |
1 | 7 | 3 |
1 | 8 | 6 |
2 | 1 | 5 |
2 | 2 | 4 |
2 | 3 | 7 |
2 | 4 | 6 |
2 | 5 | 3 |
2 | 6 | 1 |
2 | 7 | 2 |
2 | 8 | 11 |
3 | 1 | 8 |
3 | 2 | 9 |
3 | 3 | 10 |
3 | 4 | 4 |
3 | 5 | 3 |
3 | 6 | 2 |
3 | 7 | 6 |
3 | 8 | 2 |
4 | 1 | 4 |
4 | 2 | 3 |
4 | 3 | 5 |
4 | 4 | 6 |
4 | 5 | 3 |
4 | 6 | 5 |
4 | 7 | 8 |
4 | 8 | 9 |
5 | 1 | 10 |
5 | 2 | 4 |
5 | 3 | 5 |
5 | 4 | 8 |
5 | 5 | 3 |
5 | 6 | 6 |
5 | 7 | 5 |
5 | 8 | 6 |
preJob | sucJob | Machine | Setup time slots |
---|---|---|---|
1 | 2 | 1 | 5 |
1 | 3 | 1 | 2 |
1 | 4 | 1 | 6 |
1 | 5 | 1 | 5 |
2 | 1 | 1 | 4 |
2 | 3 | 1 | 10 |
2 | 4 | 1 | 7 |
2 | 5 | 1 | 9 |
3 | 1 | 1 | 10 |
3 | 2 | 1 | 10 |
3 | 4 | 1 | 5 |
3 | 5 | 1 | 2 |
4 | 1 | 1 | 3 |
4 | 2 | 1 | 8 |
4 | 3 | 1 | 1 |
4 | 5 | 1 | 3 |
5 | 1 | 1 | 6 |
5 | 2 | 1 | 2 |
5 | 3 | 1 | 7 |
5 | 4 | 1 | 2 |
1 | 2 | 2 | 6 |
1 | 3 | 2 | 2 |
1 | 4 | 2 | 3 |
1 | 5 | 2 | 5 |
2 | 1 | 2 | 7 |
2 | 3 | 2 | 7 |
2 | 4 | 2 | 9 |
2 | 5 | 2 | 5 |
3 | 1 | 2 | 3 |
3 | 2 | 2 | 6 |
3 | 4 | 2 | 1 |
3 | 5 | 2 | 6 |
4 | 1 | 2 | 1 |
4 | 2 | 2 | 9 |
4 | 3 | 2 | 4 |
4 | 5 | 2 | 2 |
5 | 1 | 2 | 5 |
5 | 2 | 2 | 5 |
5 | 3 | 2 | 9 |
5 | 4 | 2 | 1 |
1 | 2 | 3 | 10 |
1 | 3 | 3 | 2 |
1 | 4 | 3 | 1 |
1 | 5 | 3 | 2 |
2 | 1 | 3 | 3 |
2 | 3 | 3 | 4 |
2 | 4 | 3 | 9 |
2 | 5 | 3 | 4 |
3 | 1 | 3 | 7 |
3 | 2 | 3 | 6 |
3 | 4 | 3 | 9 |
3 | 5 | 3 | 6 |
4 | 1 | 3 | 4 |
4 | 2 | 3 | 2 |
4 | 3 | 3 | 1 |
4 | 5 | 3 | 8 |
5 | 1 | 3 | 5 |
5 | 2 | 3 | 9 |
5 | 3 | 3 | 6 |
5 | 4 | 3 | 2 |
1 | 2 | 4 | 3 |
1 | 3 | 4 | 5 |
1 | 4 | 4 | 3 |
1 | 5 | 4 | 3 |
2 | 1 | 4 | 7 |
2 | 3 | 4 | 6 |
2 | 4 | 4 | 9 |
2 | 5 | 4 | 4 |
3 | 1 | 4 | 1 |
3 | 2 | 4 | 5 |
3 | 4 | 4 | 7 |
3 | 5 | 4 | 1 |
4 | 1 | 4 | 4 |
4 | 2 | 4 | 8 |
4 | 3 | 4 | 10 |
4 | 5 | 4 | 1 |
5 | 1 | 4 | 9 |
5 | 2 | 4 | 10 |
5 | 3 | 4 | 6 |
5 | 4 | 4 | 9 |
1 | 2 | 5 | 4 |
1 | 3 | 5 | 7 |
1 | 4 | 5 | 2 |
1 | 5 | 5 | 5 |
2 | 1 | 5 | 2 |
2 | 3 | 5 | 10 |
2 | 4 | 5 | 2 |
2 | 5 | 5 | 2 |
3 | 1 | 5 | 3 |
3 | 2 | 5 | 1 |
3 | 4 | 5 | 7 |
3 | 5 | 5 | 1 |
4 | 1 | 5 | 2 |
4 | 2 | 5 | 7 |
4 | 3 | 5 | 4 |
4 | 5 | 5 | 7 |
5 | 1 | 5 | 4 |
5 | 2 | 5 | 10 |
5 | 3 | 5 | 2 |
5 | 4 | 5 | 7 |
1 | 2 | 6 | 9 |
1 | 3 | 6 | 1 |
1 | 4 | 6 | 9 |
1 | 5 | 6 | 7 |
2 | 1 | 6 | 10 |
2 | 3 | 6 | 10 |
2 | 4 | 6 | 2 |
2 | 5 | 6 | 1 |
3 | 1 | 6 | 4 |
3 | 2 | 6 | 4 |
3 | 4 | 6 | 6 |
3 | 5 | 6 | 8 |
4 | 1 | 6 | 9 |
4 | 2 | 6 | 3 |
4 | 3 | 6 | 4 |
4 | 5 | 6 | 3 |
5 | 1 | 6 | 2 |
5 | 2 | 6 | 10 |
5 | 3 | 6 | 7 |
5 | 4 | 6 | 4 |
1 | 2 | 7 | 2 |
1 | 3 | 7 | 2 |
1 | 4 | 7 | 7 |
1 | 5 | 7 | 4 |
2 | 1 | 7 | 3 |
2 | 3 | 7 | 9 |
2 | 4 | 7 | 5 |
2 | 5 | 7 | 1 |
3 | 1 | 7 | 8 |
3 | 2 | 7 | 6 |
3 | 4 | 7 | 3 |
3 | 5 | 7 | 8 |
4 | 1 | 7 | 3 |
4 | 2 | 7 | 7 |
4 | 3 | 7 | 3 |
4 | 5 | 7 | 6 |
5 | 1 | 7 | 8 |
5 | 2 | 7 | 9 |
5 | 3 | 7 | 5 |
5 | 4 | 7 | 5 |
1 | 2 | 8 | 1 |
1 | 3 | 8 | 8 |
1 | 4 | 8 | 10 |
1 | 5 | 8 | 7 |
2 | 1 | 8 | 6 |
2 | 3 | 8 | 10 |
2 | 4 | 8 | 5 |
2 | 5 | 8 | 4 |
3 | 1 | 8 | 7 |
3 | 2 | 8 | 6 |
3 | 4 | 8 | 5 |
3 | 5 | 8 | 10 |
4 | 1 | 8 | 4 |
4 | 2 | 8 | 4 |
4 | 3 | 8 | 8 |
4 | 5 | 8 | 4 |
5 | 1 | 8 | 9 |
5 | 2 | 8 | 1 |
5 | 3 | 8 | 4 |
5 | 4 | 8 | 8 |
The data are given in Worksheet with a defined name. CPLEX software was used to solve the flow shop scheduling model for this sample. After running all the data with the appropriate code, the model derived the optimal solution, which satisfied the requirements of the processing time, setup time and sequence constraints. In
Job | Machine | Processing time slots | X |
---|---|---|---|
1 | 2 | 2 | |
1 | 4 | 7 | |
1 | 7 | 3 | |
2 | 1 | 5 | |
2 | 6 | 1 | |
2 | 7 | 2 | |
3 | 2 | 9 | |
3 | 5 | 3 | |
3 | 8 | 2 | |
4 | 2 | 3 | |
4 | 5 | 3 | |
4 | 7 | 8 | |
5 | 3 | 5 | |
5 | 6 | 6 | |
5 | 8 | 6 |
To check the sequence of jobs on a machine, Y is defined as shown in
preJob | sucJob | Machine | Setup time slots | Y |
---|---|---|---|---|
1 | 3 | 2 | 2 | |
4 | 1 | 2 | 1 | |
4 | 3 | 2 | 4 | |
4 | 3 | 5 | 4 | |
5 | 2 | 6 | 10 | |
1 | 2 | 7 | 2 | |
4 | 1 | 7 | 3 | |
4 | 2 | 7 | 7 | |
5 | 3 | 8 | 4 |
The sequence of job is shown in details: Machine 1: Machine 2: Machine 3: Machine 4: Machine 5: Machine 6: Machine 7: Machine 8:
Job | Station | Beginning time slot | Finishing time slot |
---|---|---|---|
1 | 1 | 4 | 6 |
1 | 2 | 10 | 17 |
1 | 3 | 17 | 20 |
2 | 1 | 0 | 5 |
2 | 2 | 21 | 22 |
2 | 3 | 22 | 24 |
3 | 1 | 8 | 17 |
3 | 2 | 17 | 20 |
3 | 3 | 21 | 23 |
4 | 1 | 0 | 3 |
4 | 2 | 3 | 6 |
4 | 3 | 6 | 14 |
5 | 1 | 0 | 5 |
5 | 2 | 5 | 11 |
5 | 3 | 11 | 17 |
Job | lastStation | Due date | Late |
---|---|---|---|
1 | 3 | 20 | 0 |
2 | 3 | 16 | |
3 | 3 | 10 | |
4 | 3 | 25 | 0 |
5 | 3 | 30 | 0 |
Based on
After solving the numerical case study, we concluded that the proposed mathematical model is valid for solving the FFS scheduling case, especially for the setup time and non-identical machines. By checking the Gantt chart, setup time, and processing time, the results from the proposed model can provide the optimal solution.
This model was conducted in CPLEX 12.6 and run on Intel® CoreTM i3 running Windows 10. In comparison,
Number of Jobs | Number of machines | Number of stations | GAP with optimal | Computational time (s) |
---|---|---|---|---|
5 | 8 | 3 | 0% | 1.08 |
10 | 12 | 5 | 13.15% | 299.77 |
20 | 21 | 7 | N/A | N/A |
As the number of jobs increases from 5 to 10, the solving time rises relatively with 1.08 – 299.77 seconds. With more than 20 jobs, CPLEX could not give results immediately in a short time. Therefore, an improved method is needed to deliver an accurate solution for large scale data. CPLEX takes a long time to give the optimal solution. Future studies will focus on applying the tuple approach to enumerate all data and reduce the noticeable number of variables.
In this study, the proposed method focuses on solving FFS problem with the optimal solution in an acceptable computational time for larger data. In the future work, many other algorithms like genetic algorithm (GA), and ant colony optimization (ACO), and tabu search could be used for solving this kind of problem. Thus, other algorithms can be used to test and make comparisons. Additionally, a graphical user interface could be implemented to make it easier for users to operate.