Computer Systems Science & Engineering DOI:10.32604/csse.2021.016578
Article

Scheduling Optimization Modelling: A Case Study of a Woven Label Manufacturing Company

Chia-Nan Wang1, Zhao-Hong Cheng2,*, Nguyen Ky Phuc Phan3 and Van Thanh Nguyen4

1Department of Industrial Engineering and Management, National Kaohsiung University of Science and Technology, Kaohsiung, 80778, Taiwan
2Department of International Business, National Kaohsiung University of Science and Technology, Kaohsiung, 80778, Taiwan
3Faculty of Industrial Engineering and Management, International University, Ho Chi Minh City, 70000, Vietnam
4Faculty of Commerce, Van Lang University, Ho Chi Minh City, 70000, Vietnam
*Corresponding Author: Zhao-Hong Cheng. Email: zhcheng@nkust.edu.tw
Received: 05 January 2021; Accepted: 17 February 2021

Abstract: Production scheduling involves all activities of building production schedules, including coordinating and assigning activities to each person, group of people, or machine and arranging work orders in each workplace. Production scheduling must solve all problems such as minimizing customer wait time, storage costs, and production time; and effectively using the enterprise’s human resources. This paper studies the application of flexible job shop modelling on scheduling a woven labelling process. The labelling process includes several steps which are handled in different work-stations. Each workstation is also comprised of several identical parallel machines. In this study, job splitting is allowed so that the power of work stations can be utilized better. The final objective is to minimize the total completion time of all jobs. The results show a significant improvement since the new planning may save more than 60% of lead time compared to the current schedule. The contribution of this research is to propose a flexible job shop model for scheduling a woven labelling process. The proposed approach can also be applied to support complex production scheduling processes under fuzzy environments in different industries. A practical case study demonstrates the effectiveness of the proposed model.

Keywords: Flexible job shop scheduling; Woven labelling; Garment industry; Optimization; Production scheduling

1  Introduction

Production systems aim to optimize resource use on a company’s production line including human resources, raw materials, the work-in process, machine use and so on. In the production process, a task or a job may be a single operation or collection of operations that must be processed on any one of the machines. In the flow shop model manufacturing environment, the completion of products (jobs) requires many different machine types and all jobs are performed at maximum once on a machine. All jobs have to follow the same sequences of machines as they are processed. Moreover, a product must be completed on a preceding machine before it can be activated on the subsequent ones.

Scheduling is a decision-making process that is used on a regular basis in many manufacturing, production and service industries [1–9]. Scheduling is used to allocate plant and machinery resources, human resources, production processes, and purchasing materials. In addition, it helps organizations, groups, or even individual to make significant decisions based on software related to scheduling, such as Gantt charts and timetables. It is an important tool for manufacturing and engineering, where it can have a great influence on the productivity of a process by establishing heuristic techniques and mathematical programming methods. Therefore, production will distribute limited resources in the most reasonable and economical way.

Today, the woven label industry has become a very competitive and unpredictable industry in which customers constantly demand low prices as well as high levels of service and flexibility. Flexible multi-product production processes have become commonly used as they help companies to respond to changing customer demands and thereby increase plant utilization. This is reasonable if a company can decrease the total completion time, and cut down production time by using scheduling techniques.

The woven label products move through five main stages: Weaving, ultrasonic splitting, sizing, joining, and cut and fold. In each stage work is dependent on the associated machine. During the weaving procedure, fiber polymer is processed. Labels are rolled and cut into a roll of five or six depending on the type of machine. There are two types of machines that produce labels. Large industrial looms are used for mass production, and once the required number of labels are produced they are all joined together in one long roll. These rolls are checked for quality and faults. If there are no problems, the next step is the ultrasonic splitting process. Ultrasonic splitting cuts the ribbon roll to a smaller size. Labels with special requirements are coated in wax to increase the hardness of the product during the coating process. The sizing stage separates the same size name labels into a group to be prepared to be joined into a long ribbon where each label indicates the same size. Next, the ribbon labels indicating the same size will be joined into one ribbon in the joining step. Finally, the ribbon label will be cut by machine to produce single label in the cut and fold stage. This study focuses solely on the scheduling from the splitting stage to the cut and fold stage since the weaving stage service is provided by another party, and is impossible to access and alter.

The woven section changes the way scheduling of production is done in the finishing area. Scheduling for the finishing area is one of the most complicated planning problems for the factory because the finishing area includes more complex processes, which requires many human resources, machines, and complicated tasks. Before, every machine was fixed for each type of product; tasks were rarely shared between them and their utilization was based on orders from customers to determine the production order for each machine. This design meant that the machine was fixed for each type of product. As a result, utilization and efficiency were not high. The total cost of labor and machine idling time were too large under this system.

The objective of the study is to minimize the total completion time of the jobs that are sent to the Finishing Area by finding an optimal scheduling sequence based on the job processing time calculation. The model’s output will be evaluated with the current scheduling from the company to compare the differences. This study is applicable to woven label manufacturing companies and other companies that utilize the same or similar processes.

2  Literature Review

Scheduling is the process of organizing, controlling, and optimizing work and workloads in a production process or manufacturing process in the areas of supply chain and logistics, services, and production. The objectives of a scheduling process can take many different forms, such as minimizing the time to complete all activities [10,11], or minimizing total idle time [12,13], and so on.

The scheduling for parallel woven label lines is the same with the scheduling for the uniform parallel machines model. A number of machines in parallel are a generalization of the single machine model. Many production shop floors consist of several stages or work centers or workstations, each with a number of machines in parallel. The machines at a work center may be identical, so that a job can be processed on any one of the machines available. Parallel machine models are important for the same reason that single machine models are important: If one workstation experiences a bottleneck, then the schedule at that work center will determine the performance of the entire production system. Furthermore, because of the increased pressure towards line utilization, many manufacturers are faced with the needs to develop feasible schedules that complete each customer’s order in proper time and make sure that the usage of machines is not in efficient (balancing efficiency with customer demands).

The identical parallel machine scheduling problem requires a planned maintenance period on each machine to minimize the sum of completion times [14]. This paper is a first approach to this problem in that it proposes one of three methods to solve the problem at hand, namely mixed integer linear programming methods. Several constructive heuristics are proposed. Experimental results show that the methods offer satisfactory solutions.

The problem of scheduling jobs to minimize the sum of earliness and tardiness costs has been receiving increasing attention in recent years. Several authors have addressed the single-machine problem where all jobs have a known common due date [15–20]. Earliness and tardiness research scheduling with sequence dependent setups on uniform parallel machines [21] present a compact mathematical model to describe the computational experience and offer scheduling solutions for earliness and tardiness problems.

Based on the “Just in Time” principle (mixed model assembly sequencing at Toyota) and parallel machines model [22], the problem of scheduling a number of jobs on a number of parallel machines that operate at different speeds (known as uniform parallel machines) is considered. Bagchi et al. [23] considered the problem of minimizing squared deviations from a common due date and, a single machine with unequal earliness and tardiness penalties among jobs. These considerations have been shown to be NP complete [24]. The weight of a job does not depend on whether the job is early or late; however, weights may vary between jobs, thus this research described optimality conditions and presented a computationally efficient dynamic programming algorithm. When the weights are bounded by a polynomial function of the number of jobs, a fully polynomial approximation scheme is given.

Laguna et al. researched [25] a heuristic for the weighted earliness penalty problem with deadlines in parallel identical machines and approached a combination of elements of the solution methods known as the Greedy Randomized Adaptive Search Procedure (GRASP) and Tabu search. It also used a branch-and-bound post-processor to optimize individually the sequence of the jobs assigned to each machine.

According to the paper by Mehravaran and Logendran [26], the labor and machine components were integrated with products instead of only machines in non-permutation flow shops scheduling with dual resources. This is considered to be more difficult because of the range for finding the optimal sequence in non-permutation (n!)m is larger than this in permutation (n!). The labor structure can include many skill degrees with specific labor amounts within those degrees. Machines can bypass many stations. For any two consecutive jobs, the antecedent job can deeply affect the subsequent job set-up time.

A genetic algorithm for dual factors in a deterministic environment was developed by ElMaraghy et al. [27]. It was applied in a flexible manufacturing system with different labor skill levels, but the optimization was inadequate, in that it was not oriented to bicriteria scheduling and mathematical models. The algorithm was rooted in a genetic algorithm also designed by Chaudhry and Drake [28] to optimize the objective function by labor assignment with exact parallel machines.

3  Mathematical Model

The goal of this study is the development of a mathematical model to find the optimal solution for the scheduling problem of a job shop production system. While heuristics methods are frequently employed to solve scheduling problems with great advantages in computation time regarding problems with large sizes, these methods usually do not provide the optimal solution to a problem at hand. Therefore, this study focuses on the linear programming approach to the problem.

3.1 Assumptions

• The centerfold lines are working in good performance condition, there are no machine breakdowns or interruptions to the operation.

• Each machine can only perform one job at a time.

• Each job can be split and tasks within a job may be performed by any machine.

• The last completion time of the machine is the total completion time of all jobs.

• Some of the data for processing time of a job on a machine is an assumption from capacity calculation and the, programmer since no actual run-time has occurred yet.

• Some of the cost is based on standard cost follow company policy.

3.2 Mathematical Model

The following annotations are used in our model formulations.

3.3 Parameters

j    Index of jobs, j=1…J

w    Index of workstation, w=1…W

t    Index of time periods, t=1…T

H   Set of tuples (j,w) . Each tuple show that job j must be processed on workstation w

K    Set of tuples (j,wp,ws) . Each tuple show that job j must be processed on workstation wp then ws

BigM  A very large number

pmj   Processing time of job j on machine m

Aj    Release time of job j

Dj    Due date of job j

Nw   Maximum number of machines on workstation w

3.4 Decision variables

Cmax  The make spans

Cj   Completion time of job j

Fwj   Finishing time of job j on workstation w

Bwj   Beginning time of job j on workstation w

Xwj   Binary variable Xwj=1

Uwjt   Binary variable. Uwjt=1 if at period t, t≥Bwj otherwise; Uwjt=0

Rwjt   Binary variable. Uwjt=1 if at period t, t≤Fwj otherwise; Rwjt=0

Vwjt   Binary variable. Uwjt=1 if at period t, Bwj≤t≤Fwj otherwise; Vwjt=0

The objective of this model is to minimize the make span which is shown as follows:

MinimizeCmax (1)

Subject to:

Swj≥Aj,∀(j,w)∈H (2)

Constraint (2) ensures that the starting time of a job on any workstation cannot be sooner than the job release time.

Fwj≤Dj,∀(j,w)∈H (3)

Constraint (3) claims that the finishing time of a job on any workstation must be later than the job due date.

Cmax≥Fwj,∀(j,w)∈H (4)

Constraint (4) states that the make span is the largest completion time of the whole job.

Sgj≥Fwj+1,∀(j,w,g)∈K (5)

Constrain (5) guarantees that each job must follow its required sequence, which is specified in K.

Fwj≥Swj+pwj−1,∀(j,w)∈H (6)

Constraint (6) ensures the finishing time of a job on a workstation must be smaller than or equal to its starting time plus processing time.

t≥Swj−1−BigM×(1−Uwjt),∀(j,w)∈H,∀t (7)

t≤Swj−1−BigM×Uwjt,∀(j,w)∈H,∀t (8)

Constraint (7–8) claim that Uwjt=1 if and only if t≥Swj , otherwise Uwjt=0 .

t≤Fwj+1+BigM×(1−Vwjt),∀(j,w)∈H,∀t (9)

t≥Fwj+1−BigM×Vwjt,∀(j,w)∈H,∀t (10)

Constraint (9–10) claim that Vwjt=1 if and only if t≤Fwj , otherwise Vwjt=0 .

Rwjt≤Uwjt,∀(j,w)∈H,∀t (11)

Rwjt≤Vwjt,∀(j,w)∈H,∀t (12)

Rwjt≥Uwjt+Vwjt−1,∀(j,w)∈H,∀t (13)

Constraints (11–13) guarantee that Rwjt=UwjtVwjt . As a result of that Rwjt can satisfy its definition.

∑j=1J⁡Rwjt≤Nw,∀t,∀w (14)

Constraint (14) ensures that at any period t, the number of jobs processed on a workstation must be smaller than its maximum number of machines.

4  Case Study

In our problem, there are five workstations, namely: Ultrasonic splitting, coating, sizing, joining, and the cut and fold station. These are numbered as 1, 2, 3, 4 and 5, respectively. The number of identical parallel machines in stations are respectively 5, 1, 4, 6, and 12. The approach is applied to the schedule for the CL (Center Fold) line, which has the largest capacity and receives most orders from the customer.

The current scheduling method of the company faces several limitations. These limitations make it so that multiple orders cannot be finished within one day. As a result of this, late delivery is unavoidable. Furthermore, it also creates more difficulties periods of shift change. Fig. 1 shows a Gantt chart based on the current scheduling of the company in the woven section with 25 jobs and each time slot equal to 30 minutes.

Figure 1: Gantt charts based on current planning in woven section

From the chart, it can be seen that the total completion time for 25 jobs is extremely large, i.e., 107 time slots. This is much larger than the available number of time slots in one day, i.e., 48 slots per day. Moreover, the idle time in one group of machines between two jobs is also very large.

With the current approach, there are a total of three jobs, i.e., 14, 24 and 25, which cannot be finished within one day. As a result of this, these jobs cannot meet the delivery schedule for the customers. To improve the performance of the whole system, the new approach is applied. Before scheduling, the pre-processing step is employed. In this step, some similar jobs with small order quantities are grouped together while jobs with large order quantities are split into smaller jobs. Tab. 1 gives the result of grouping and splitting jobs in the preprocessing.

Table 1: The result of grouping and splitting jobs in the pre-processing stage

The processing time of a job on a workstation is calculated as a ratio of job order quantities to the machine’s productivity in a workstation. The release time and due date of all jobs are set to 0 and 48, respectively. Tab. 2 gives the summary of required sequences of jobs and their processing times on proper workstations.

Table 2: Workstation sequence and job processing times on workstations

With whole parameters, the model is constructed and solved using a CPLEX solver. Fig. 2 shows the results obtained by applying the proposed approach.

Figure 2: Gantt charts based on proposed approach

The problem is solved in CPLEX within just nine seconds, and the span of the whole job is only 40 time slots. This result shows a significant improvement of the entire performance. All jobs can be finished within one day. Utilization of machines in workstations also increases considerably. Tab. 3 shows the completion time of the 25 original jobs converted to new jobs.

Table 3: Starting time and completion time of 25 original jobs converted to new jobs

The new proposed approach can save up to 67 time slots. In the new plan, machine utilization improves significantly while the schedule is compacted. As a result of this, a new batch of jobs can be scheduled very quickly. For example, with the new approach, workstation one is completely idle after time slot 15 while in the old process, it was only free after time slot 27. Workstation one is thus available for the next day’s planning order after the first shift is finished. A similar improvement also occurs in other workstations.

5  Conclusion

This study proposes a general mathematical model for job shop scheduling when each workstation has several identical parallel machines. A case study relating to the woven label manufacturing company is also presented so that the correctness of the model can be verified. In this research, the current situation of AD company is mentioned, which has five machine groups and different machine sequences assigned to each job. The problem was then solved using CPLEX with the main target of minimizing production time. The range of 25 jobs collected from the production department was applied, and the result needed only nine seconds to present the optimal solution. From analysis, it is clear that the approach not only suggests a better plan to reduce wasted time, and enhance productivity, but also gives the supervisors or staff a flexible tool to gain insight into their production scheduling, so they can easily control and adjust their planning to suit different circumstances.

From an academic viewpoint, our model is very comprehensive and has a high versatility, which is easy to integrate or expand to other models. The advantage of this method is that it favors known constant and assigns the jobs to specific machines in a workstation. It reduces considerably the number of variables since it does not need to track to which machine jobs are assigned. This framework can be used to create benchmark problems for other related heuristic and meta heuristic algorithms of flow shop and job shop problems. However, there are certain disadvantages to this linear approach to the scheduling problem, most notable of which is the long computational time of problems with a large number of jobs. Therefore, the model should be applied for cases with a proper number of jobs to ensure the efficiency of the scheduling process. Future study can focus on the incorporation of the proposed model with the tuple method so that the efficiency of the model can be increased.

Funding Statement: This research was partly supported by the National Kaohsiung University of Science and Technology, and MOST 109-2622-E-992-026 from the Ministry of Sciences and Technology in Taiwan.

Conflicts of Interest: The authors declare that they have no conflicts of interest to report regarding the present study.

This work is licensed under a Creative Commons Attribution 4.0 International License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.