Journal Search Engine
Search Advanced Search Adode Reader(link)
Download PDF Export Citaion korean bibliography PMC previewer
ISSN : 1598-7248 (Print)
ISSN : 2234-6473 (Online)
Industrial Engineering & Management Systems Vol.14 No.4 pp.401-412

Production Planning Method Using the Push-back Heuristic Algorithm: Implementation in a Micro Filter Manufacturer in South Korea

Shin Woong Sung, Young Jae Jang*, Sung Wook Lee
Department of Industrial and Systems Engineering, Korea Advanced Institute of Science and Technology, Daejeon, Korea
Deloitte Analytics, Deloitte Anjin LLC, Seoul, Korea
Corresponding Author,
August 18, 2015 December 1, 2015 December 2, 2015


In this paper, we present a modeling approach to production planning for an actual production line and a heuristic method. We also illustrate the successful implementation of the proposed method on the production line. A heuristic algorithm called the push-back algorithm was designed for a single machine earliness/tardiness production planning with distinct due date. It was developed by combining a minimum slack time rule and shortest processing time rule with a push-back procedure. The results of a numerical experiment on the heuristic’s performance are presented in comparison with the results of IBM ILOG CPLEX. The proposed algorithm was applied to an actual case of production planning at Woongjin Chemical, a leading manufacturer of filter products in South Korea. The seven-month execution of our algorithm led to a 24.5% decrease in the company’s inventory level, thus demonstrating its practicality and effectiveness.



    This paper introduces a single-machine production planning problem with a distinct due date and its solution heuristic, which minimizes the sum of earliness and tardiness penalties. The problem was derived from an operational project at Woongjin Chemical Co., Ltd. (WC), a leading manufacturer of filter products and synthetic fibers in Korea. The project’s objective was to deal with the excessive unsold finished-goods (FG) inventories in the company’s micro filter business unit (W-C MF). The main contribution of this paper is to show how the proposed planning algorithm was developed and applied to solve an actual industrial problem. Through data and process analysis, we first identified that the unit’s inefficient planning process had increased the uncertainty about whether the customer orders would be produced on time (Figure 1). Finally, it had led salespeople to create phantom orders which were directly connected to the inventory pile-up. Phantom orders are here defined as speculative orders placed not by customers but by salespeople. Based on this problem identification, we formulated a single-machine production planning model with a distinct due date, which minimizes the sum of earliness and tardiness penalties. Its solution heuristic was devised considering the W-C MF’s operational requirements. The new system, consisting of scheduler and redesigned business process, was implemented in W-C and decreased the FG inventory level by 24.5% within seven months (Figure 2).

    1.1.Manufacturing system of W-C

    The manufacturing process of W-C MF comprises six discrete processes: pleating, welding, end-capping, testing, bridging, and packaging. All six processes are semi-automated, meaning that manual operations or handling are required for the machines to complete a job. In the pleating process, a combination of two or three chemical fabrics called media overlap with one another, and are entered into the pleating machine. The machine then pleats the media to widen the filtering area, with the pleated material cut to the required length. In the welding process, the two ends of the pleated media are attached by heat or ultrasonic waves before insertion into a plastic case. Each end of the case is sealed with a cap in the end-capping process. The work-in-process after endcapping is called the semi-finished product. These products are then tested and passed to the bridging stage, at which requested options such as O-rings are attached. Finally, the products are packed and stored in the warehouse as FG inventory.

    Figure 3 shows the average operation time of each process per day. It can be seen that the pleating process constitutes a bottleneck, as pleating takes far longer than the other manufacturing processes with regard to production time and setup time. In addition, every stockkeeping unit (SKU) in W-C MF is distinguished in the pleating process by raw materials and size. We thus concluded that if we could control the pleating process, then we could control the entire manufacturing operation. Accordingly, we decided to formulate a singlemachine planning model for the pleating process.

    1.2.Literature Review

    1.2.1.Production Planning and Sequencing

    Because the manufacturing system of W-C MF, which operates in a make-to-order fashion, is timeconstrained and a single machine manufactures multiple items, we formulated a single-machine multi-item capacitated lot-sizing problem (CLSP) for production planning. In line with the classification of a CLSP in Karimi et al. (2003), our problem has the following features: independent and deterministic demand, single-level production system, and sequence-dependent setup time. Trigeiro et al. (1989) studied a CLSP with sequence-independent setup time, decomposing the problem’s capacity constraint through Lagrangian relaxation. However, owing to its complexity and the practical computational issues involved, they did not address lot sequencing. The usual approach to dealing with both lot sizing and lot sequencing is to decompose them into two modules and then integrate them hierarchically (Drexl and Kimms, 1997; Lasserre, 1992; Dauzere-Peres and Lasserre, 1994). In other words, the lot sizing problem is solved first, and then lot sequencing is conducted for the previously allocated lots in each period. Several methodologies have been developed to deal with the integrated lot sizing and scheduling, such as iterative approach (Mateus et al., 2010) and cutting plane approach (Kis and Kovács, 2012). We also decomposed the problem into planning and sequencing and developed a twostage model: a planning model that allocates the jobs in each time period and a sequencing model that determines the daily production sequence for the day’s daily allocated jobs. This paper expands the simple model for production planning and sequencing first presented in Sung et al. (2013).

    1.2.2.Earliness and Tardiness Measures

    The objective of our mathematical model is to minimize the weighted sum of earliness and tardiness (E/T). A number of studies on the E/T scheduling problem consider distinct due dates (Baker and Scudder, 1990; Kedad-Sidhoum et al., 2008; Wan and Yen, 2002; Lee and Choi, 1995). According to Garey et al. (1988), the E/T scheduling problem with a distinct due date is NPcomplete. Fry et al. (1987) suggested a heuristic for solving the E/T scheduling problem with a distinct due date that is based on the adjacent pair wise interchange method with inserted idle time. The insertion of idle time is effective in reducing the earliness penalty because it prevents jobs from being produced too early in a greedy fashion. Oğuz and Dincer (1994) proposed an equalslack rule that provides a useful structure for the optimal solution of the E/T problem with inserted idle time. They proved that the objective function of the E/T problem can be expressed as the sum of the absolute deviation of the production time periods of jobs and their slack times, which is minimized when jobs are produced at their slack times. In consideration of such system properties as inserted idle time and the equal-slack rule, we developed a heuristic for solving the E/T problem with distinct due dates.

    1.2.3.Sequencing with Sequence-Dependent Setup Time

    The manufacturing system of W-C MF processes multiple types of products. Therefore, setup changes are required between different types of products, during whic h the raw materials and machine settings are changed. The amount of time needed to change the setup for a current product depends on the product that was produced previously, which is called sequence-dependent setup time. The setup time between two products of same types is much shorter than that between two products of different types because only a machine setup change is required between production runs of similar products, whereas both the machine setup and raw materials need to be changed between those of dissimilar products. Thus, we can efficiently utilize production capacity by sequence the jobs to minimize the total setup time. The industrial applications that deal with the sequence- dependent setup time have been reported by Ferreira et al. (2009)and Clark et al. (2010). The scheduling problem with sequence-dependent setup time can generally be formulated as a traveling salesman problem (TSP) (Baker and Trietsch, 2009). The cities in a TSP are treated as products, and the distances between them as setup times. TSP applications to job sequencing can be found in Fleischmann (1994) and Salomon et al. (1997). In this research, the sequencing model adopted to minimize the total setup time was solved by the “nearest unvisited city” rule (Conway et al., 2012).

    The remainder of the paper is organized as follows. The company and its business issues are introduced in Section 2. A mixed-integer linear programming formulation for production planning is described in Section 3, and our heuristic algorithm, the push-back heuristic, is discussed in Section 4. The computational results of the proposed heuristic are presented in Section 5. Section 6 outlines the quantitative and qualitative benefits of the heuristic’s execution in W-C, and Section 7 concludes the paper with a summary and suggestions for future research.


    2.1.Company Introduction

    W-C was founded in South Korea in 1972 and is now a leading manufacturer of filter products and synthetic fibers (Woongjin Chemical Co., Ltd., 2012). It operates eight overseas branches, including operations in the USA, China, the UAE, and Spain. W-C’s filter business was ranked fourth in the world in terms of market share in 2011 (Korea Investment and Securities Co., Ltd., 2011). One of its major filter business units is the aforementioned W-C MF. Micro filters (MF) are a basic filter type accounting for the major share of the overall filter market. They are widely used in such industrial processes as the manufacture of semiconductors and displays to remove contaminants. W-C has been in the MF manufacturing business longer than any other company in Korea, and operates the country’s largest MF production facility and quality control system in Gumi, Korea. To meet the diverse needs of customers, W-C MF focuses on producing various types of products. It maintains over 360 SKUs, the number of which continues to increase through on going R&D investments in new products.

    For many years, W-C MF has tried to reduce its FG inventory level. Excess inventory piles up as unsold stock, thus incurring significant costs. It sometimes reduces the inventory level by selling stock at discounted prices, but the effect is temporary. W-C MF recently conducted an internal investigation that led it to speculate that the reason for its excessive FG inventories was inefficient inventory management. However, the unit’s stakeholders were not fully convinced. Therefore, in March 2012, W-C embarked on a project entitled operational innovation to deal with the issue. The project’s first task was to identify the underlying causes of the accumulation of FG inventories, which are discussed in the next section.

    2.2.Business issues in Woongjin Chemical Micro Filter unit

    Data analyses and interviews with salespeople and the W-C MF production planner helped us to identify various business issues that were helpful in determining the appropriate solution approach.

    2.2.1.Decrease in On-Time Deliveries

    W-C MF had been receiving numerous complaints from client companies regarding late deliveries. Its ontime delivery performance had decreased every year, although its level of FG inventories continued to rise. This paradoxical situation made the unit’s salespeople nervous because their promotion opportunities and compensation and incentives were dependent on the on-time delivery rate.

    2.2.2.Increase in number of product types

    W-C MF focuses on developing new products to increase product diversity, and the number of product types increases every year. As a result, the unit’s SKUs were also increasingly diversified, leading to a rise in the number of setup changes required in the manufacturing process. We analyzed the unit’s historical production data, and found that the number of setup changes had increased every year, along with increases in product diversity. Those setup changes incur setup time, which is sequence-dependent. Although the production sequence greatly influenced the amount of setup time required, it was determined by assemblers based on their experience without any logical sequencing.

    2.2.3.Inefficient Production Planning

    Production planning for the upcoming week was performed every weekend using a Microsoft Excel spreadsheet. The planning process was based on the planner’s experience and normally took four to six hours. If even a small modification was required in the production schedule owing to a rush order, the whole planning process needed to be repeated. As a result, human errors such as omissions and redundancies in customer orders occurred frequently. Furthermore, because planning for the following week took place on Sunday, if an order was placed on Monday, it might have to wait a week to be scheduled. These production planning inefficiencies made it impossible for the planner to perform real-time production planning and “what-if” analysis to answer such common questions: Is it possible to complete this new order by the required due date without affecting the on-time delivery of existing orders?

    2.3.Problem Identification

    The foregoing analysis allowed us to clarify the underlying causes of the excessive FG inventories. The W-C MF business process saw customer orders sent from the sales department to the production department. Before orders were confirmed, their shipment due dates were decided, normally with input from the customer because customer satisfaction is key to the competitiveness of a supplier such as W-C MF. Because most of the unit’s major customers wanted a quick delivery, but there was no real-time system for what-if analysis to check whether a certain due date could be promised without affecting other orders, sales personnel had no choice but to set due dates as customer requests. Furthermore, the manual production planning method was unable to handle large numbers of orders with different due dates logically. Therefore, salespeople sometimes placed phantom orders to allow major customer orders to be dealt with in a timely manner. For example, if a client company seemed to place an order for “product A” in the first week of every month, the salespeople placed a phantom order for an estimated quantity of that product in the first week of every month. However, if the actual orders differed from their expectations, there was a chance that the completed products arising from phantom orders would become unsold FG inventory. If it were possible to inform the sales personnel whether customer orders could be completed by the requested due date in real time through an efficient production planning system, then they could better manage customer orders and reduce the need for phantom orders. As a result, we decided to develop a new system for production planning to enable real-time what-if analysis of customer orders and enhance the unit’s ability to respond to those orders. The new system consists of two parts: scheduler and business process. The scheduler model comprises production planning and sequencing.

    2.3.1.Stage 1: Production Planning

    The first stage of our model is a single-machine multi-item discrete CLSP with an E/T penalties and constraints on the number of setup changes. No preemptions are allowed, which means that once a job has started, it must be completed with no interruptions. The machine can process only one job at a time, and jobs cannot be split. A job is assigned to each customer order, which specifies the requested product, demand quantity, and due date. Different customer orders can contain identical products. Because the setup change is product- rather than order-dependent, the indices for customer order and product are handled separately. The unit of time is one day. The model allows multiple products to be produced in each time period, and is thus called the large bucket model (Drexl and Kimms, 1997). We assume that a job that is assigned to a day is fully produced in that day. If there is an order which exceeds one-third of the capacity of a day, it is divided into multiple jobs with the same due date by production manager before treated in the planning model. The planning horizon is set to be longer than the latest due date in the entire order set. To reduce the complexity, we assume that the setup time in the planning model is sequence-independent. The unit E/T penalties are given as constant values. We formulate a mixed-integer linear programming model that determines the optimal lot sizes for each customer order in each time period such that the sum of the E/T penalties is minimized. Details of the formulation are given in Section 3, and the heuristic used to solve the model in Section 4.

    2.3.2.Stage 2: Sequencing

    In the second stage of the model, we determine the production sequence for the daily allocated lot sizes while minimizing the daily total setup time. We considered a sequence-dependent setup time. The nearest unvisited city rule (Conway et al., 2012) was applied, which chooses the job with least setup time first and makes the sequence.


    3.1.Indices, Parameters, and Decision Variables

    The definitions and notations of the indices, parameters, and decision variables in our planning model are as follows.


    I set of products (iI)

    J set of jobs (jJ)

    T set of time periods (tT)


    Fjt Penalty value for E/T when j is produced in time period t

    dij Demand quantity of product i of job j

    ai Unit processing time of product i (unit: minutes)

    ci Setup time for product i (unit: minutes)

    Lt Total available time in time period t (unit: minutes)

    Mit Any large number greater than or equal to the total available time intime period t divided by unit processing time of product v (Lt / ai )

    St Maximum number of setup changes in time period t

    Decision variable

    xijt Production quantity of product i of job j in time period t

    y jt 1 if job j is allocated to time period t, and 0 otherwise

    zit 1 if product i is allocated to time period t, and 0 otherwise

    3.2.Penalty Value Fjt

    When a job j is produced in time period t, penalty Fjt is incurred if the job is early or late. Let t j denote the production time period of job j. The penalty value depends on the difference between production time period t j and ideal production time period D* j (Eq. (1) and Eq. (2)). The ideal production time period D* j is calculated by subtracting standard lead time SLT j from due date dd j (Eq. (3)). SLT j is the amount of time needed to complete the entire manufacturing process for a job j, the value given by W-C MF. We assume that the planning horizon begins with day 1. For example, if the due date of a job is day 6 and the standard lead time for the job is 3 days, then the ideal production start date is day 3. If the production of the job begins before or after day 3, it will incur a penalty.

    F jt = μ j t j D j
    μ j = unit   earliness  penalty  if  t j D j unit  tardiness  penalty  if  t j > D j
    D j = d d j SL T j

    In our model, we set the unit earliness penalty to 0.02/day and the unit tardiness penalty to 2/day, reflecting the requirements of W-C MF. The penalty increases rapidly for tardiness and relatively slowly for earliness. For example, if D* j is day 3 and the production of job j is assigned to day 1 (t j =1), the penalty is 0.02 1 3 = 0.04 for earliness, whereas if job j is assigned to day 5 (t j = 5), the penalty is 2 5 3 = 4 for tardiness. Because we know the unit penalties of earliness and tardiness and the D* j for every job j, the values of Fjt can be calculated for all ts in a given planning horizon. In our implementation at W-C MF, the penalty values were provided as a penalty matrix, comprising jobs in rows and time periods in columns.

    3.3Mathematical Model

    minimize j t F jt y jt

    subject to

    t x ijt = d ij  for  all  i j
    t y jt = for  all  j
    i j a i x ijt + i c i z it L for  all  t
    x ijt M it y jt  for  all  i , j , t
    j x ijt M it z it   for   i , t
    i z it S t   for   all   t
    x ijt 0   for   all   i , j , t
    y jt 0 , 1   for   all   j , t
    z it 0 , 1   for   all   i , t .

    Objective function (4) minimizes the sum of the earliness and tardiness penalties for all jobs. Constraint (5) specifies that the sum of the production quantities of product i of job j should be equal to demand. Constraint (6) prevents a job from splitting, reflecting the assumption. Constraint (7) denotes the resource constraint requiring that the sum of the processing time and the setup time of a time period t be less than or equal to the total available time of the time period t. Constraint (8) shows the relationship between production quantity xijt and binary variable y jt . It indicates that the production quantity of product i of job j at time period t can have a nonzero value only when y jt is 1. Note that y jt is used in the objective functions with its penalty value. Similarly, constraint (9) represents the relationship between the production quantity of product i at time period t and its associated setup changes. It determines whether the setup change for product i is occurred in time period t. Constraint (10) represents a managerial preference for limiting the number of daily setup changes, since frequent setup changes increase the fatigue level of assemblers. Finally, constraints (11), (12), and (13) require that the decision variables are non-negative or binary.


    4.1.Requirements of the Heuristic

    The following requirements needed to be satisfied in designing the solution method.

    • Easy-to-understand method: Generally, the change from existing method to new one is uncomfortable. If the new method is difficult to understand, people tend to be more reluctant to accept it. As the entire W-C MF factory was to operate according to the new method, the method for production planning needed to be understandable and intuitive for those working in the production department.

    • Fast computation time: To enable real-time what-if analysis for due date promises and efficient production planning, the method need to find a reasonable solution within a few seconds.

    • In-house solution without using a commercial software: By the company policy, to develop an in-house solution was recommended rather than to purchase the commercial optimization software. It was because most of the commercial software are proprietary, which means that users cannot see the underlying algorithms in detail, and moreover, it requires certain level of technical knowledge to effectively utilize the commercial software. In case of using an in-house solution developed with a logical process, it would be easier to fully utilize it and modify it whenever necessary.

    These requirements made it necessary to develop a suitable heuristic rather than rely on a commercial solver. We thus devised a heuristic to solve a single-machine multi-item CLSP with an E/T penalty and distinct due date.

    4.2.Algorithm Development

    We analyzed the problem with the following properties and lemmas.

    Property 1. The amount of time between ideal production time period D*j and the start of actual production is closely related to the concept of “slack time,” which measures the urgency of a job. Because the slack time of job j (s j ) is usually calculated by subtracting the time required to complete it (SLT j ) from its due date (dd j ), we can use Eq. (3) to obtain the value of s j . The-refore,

    s j = D j = d d j SL T j

    Using Eq. (1) and Eq. (14), the objective function can be expressed as

    j μ j t j s j

    Lemma 1.If the time resource (capacity) is unrestricted, producing job j at s j for all j∈J is optimal for minimizing j μ j t j s j .

    Proof. If job j is produced at its slack time s j , t j becomes equivalent to s j . If the capacities are unrestricted, every job can be allocated to its slack time and the total penalty becomes 0, which is optimal. This completes the proof. □

    Property 2. Let Cj denote the production completion time period of job j. Cj is calculated by the sum of production time period t j and standard lead time SLT j . The objective function (Eq. (15)) can be converted to the sum of weighted absolute deviation between Cj and dd j , as follows.

    j μ j t j + SL T j d d j
    = j μ j C j d d j

    The weighted absolute deviation between Cj and dd j has been shown to be non-transitive (Fry et al., 1987), which means that we needed to carry out full enumeration to guarantee a global optimum and were prevented from conducting a permutation to form a schedule without idle time inserted (which is called the dominant set). It was therefore beneficial to insert idle time between jobs to improve our objective function (Fry et al., 1987).

    Property 3. Two or more jobs may have the same s j . For example, in the cases of both dd j = 5 with SLTj = 3 and dd j = 7 with SLTj = 7, slack time s j is 2. Therefore, minimizing Eq. (15) for certain common slack times is similar to minimizing the weighted absolute deviation between production time periods and a common due date (Garey et al., 1988). For the common due date problem, the shortest processing time (SPT) rule is optimal for the tardiness measure (Baker and Trietsch, 2009). The SPT rule sequences the jobs with their processing times in ascending order.

    Property 4. The minimum slack time (MST) rule is a scheduling method by which jobs are sequenced by the nondecreasing order of their slack times. In the case of all due dates being sufficiently spread out, the MST rule is optimal for the tardiness measure (Pinedo, 2012). Owing to the managerial requirements of W-C MF, the earliness penalty is far less than the tardiness penalty (α = 0.02, β = 2), which implies that decreasing the tardiness penalty is a higher priority than decreasing the earliness penalty.

    Based on these features of our problem, we designed our heuristic by combining the MST and SPT rules to obtain a good initial solution for the tardiness measure. The sequence followed the MST rule first, and the SPT rule was then applied to jobs with the same degree of slack. Subsequently, from the first-positioned job, we allocated the sequenced jobs to each time period by calculating their processing time and setup time in accordance with the total available time. Figure 4 shows the resulting initial solution of our heuristic. Each block represents a set of jobs with the same slack time. Note that the jobs are allocated at the beginning of the time period in a greedy fashion, possibly incurring earliness costs. Inserting idle time between jobs would improve the objective function with respect to the earliness penalty (Fry et al., 1987). Accordingly, we devised a heuristic algorithm called the push-back algorithm to reduce the earliness penalty by pushing early jobs back to their ideal production time. Figure 5 illustrates the solution after the push-back procedure has been applied.

    Lemma 2 (Push-back heuristic).Given an initial solution sequenced by the MST rule and SPT rule, if there exists slack time between the production time period of a non-tardy job j (t j ) and its ideal production time period ( (D*j ), we can push that job back from t j to D*j . The new solution after such push-back will always have a smaller total penalty than the initial one because of the decrease in the earliness penalty.

    Proof. Let ETBj and ETAj be the E/T penalties for job j before and after its push-back to D*j By definition, if there exists slack time between the ideal production time period for job j (D*j) and its actual production time period (t j ), a push-back from t j to D* j is possible and D*jt j >0. Therefore, * 0. ETBj = μ j t j D j >0. After the push-back procedure, the updated production time period, t′j , becomes equivalent to D*j In this case, Then, ETAj = μ j t j D j =0, and ETAj < ETBj . This complete the proof. □

    4.3.Algorithm Procedure

    In this subsection, we explain the procedure of the push-back heuristic in detail. Figure 6 presents a brief flowchart of the heuristic.

    Step 1. Sequence jobs with the MST rule and the SPT rule.

    1-1. Calculate the slack time of each job.

    1-2. Sequence the jobs in non-decreasing order of their slack times (MST rule).

    1-3. For the jobs with the same slack time, calculate their production times by multiplying their unit processing times and demand quantities and adding their setup time. Then, sequence the jobs in non-decreasing order of their calculated production times (SPT rule) within the sequence with the same slack time.

    Step 2. Allocate the sequenced jobs to time periods.

    2-1. Calculate the production time of each job in the sequence by using the calculation method in the Step 1-3.

    2-2. Comparing the cumulative production time of the jobs in the sequence with the daily available time Lt , allocate the jobs in the sequence to the time periods while ensuring that the resource constraint (Constraint (7)) and the maximum setup number constraint (Constraint (10)) are not violated. The initial solution is generated through this procedure.

    2-3. Store the time period of each job j as iniTMj .

    Step 3. Check the terminating condition: iniT[N] > D*[N].

    Let N be the number of jobs (N > 0). If the production time period of the last-positioned job, iniT[N], is later than its ideal production time period D*[N], then terminate the algorithm because performing the push-back procedure is impossible and thus the procedure cannot improve the objective value.

    Step 4. Set the parameters and the variables for the pushback procedure.

    Step 5. Apply the push-back procedure. See Algorithm 1.


    To be practicable and reliable in daily operations of W-C MF, the heuristic should be fast, less than a few seconds, and perform well. Therefore, we measured the computation time of the heuristic and compared the objective values with those obtained from commercial optimization software, IBM ILOG CPLEX. We first generated input data based on actual datasets from W-C MF. The unit’s five-year (2007-2011) historical sales order data were used to generate the parameters and jobs (customer orders), including products, demand quantities, and due dates. The total time available in each time period is 1,440 minutes, the maximum number of daily setup changes is 15, and the earliness and tardiness penalties are 0.02/day and 2/day, respectively. The major performance measures of the heuristic are the quality of objective value and the computation time. Specifically, the quality of objective value is calculated by comparing it with the one from CPLEX, which is represented as “Difference” in percentage terms (Eq. (18)). The unit of computation time is seconds.

    Difference (%) = (Objective value of heuristic - that of CPLEX) (objective value of CPLEX) × 100

    A series of sensitivity analyses were performed on the number of jobs (problem size) and such parameters as capacity, the number of products, and the maximum setup number. Note that the goal of the computational experiment is not to show that the performance of our method is better than that of the commercial software but to demonstrate that our method quickly creates a feasible schedule that has a reasonable objective value. The proposed heuristic was programmed using Java and executed on a 3.20GHz AMD Phenom II X4 955 processor with 4.00GB of RAM. The mathematical model was implemented in Java, with an external call to IBM ILOG CPLEX V12.1.

    5.1.Number of Jobs

    By changing the number of jobs, which is the size of the problem, we were able to check the performance of the heuristic. The number of jobs in a given planning horizon is normally 100. As shown in Table 1, the performance of our heuristic is generally near optimal when the number of jobs is small and deviates from optimal by about 10% in the other cases. Our heuristic gives a solution within 0.2 seconds in all cases, which is sufficiently quick for real-time production planning and what-if analysis.


    We then changed the total time available for each time period, which constitutes the capacity of the time resource. The actual total time available at W-C MF is 1,440 minutes, and we increased and decreased the current value. Within the realistic capacity range in Table 2, our heuristic performs generally well. The percentage difference does not fall below 6.9% because the limit on the number of setup changes prevents the heuristic from utilizing the capacity fully. The computation time of our heuristic is always less than 0.2 seconds. The computation time of CPLEX, in contrast, tends to increase dramatically with an increase in capacity because it requires a number of enumerations to find the optimal solution within tight constraints.

    5.3.Number of products

    Table 3 shows our heuristic to perform better for a large number of products than for a small number because of the decrease in effort to combine the products of the same type when the number of products is large. Because W-C MF will continue to diversify its product range, the use of our heuristic is advantageous. The computation time is still within 0.2 seconds.

    5.4.Maximum setup number

    Finally, we changed the maximum number of setup changes from 12 to 22, which is the right-hand side of Constraint (10). It can be seen in Table 4 that as the maximum setup number increases, the objective value of our heuristic improves because the effect of increasing the maximum setup number is similar to that of increasing the capacity.


    A prototype of our heuristic algorithm was executed in the actual factory operations of W-C MF in July 2012. During the one-month test period, we provided production schedule using our heuristic (Figure 7), and the factory operated in accordance with our suggestions. The factory manager and assemblers were initially doubtful about our schedule owing to its unfamiliarity. However, once they understood how the heuristic operates and realized that it could improve factory operations, they accepted its practicality and offered useful feedback. The heuristic algorithm was then updated to reflect their additional requirements, and finally approved by W-C MF for full utilization as the core system in production planning and sequencing. We implemented our heuristic in the form of a decision support system that generates input data, executes the algorithm, and prints out the schedule (Figure 8). We also redesigned the business process in line with the optimized decision logic to help users to adjust to the system more quickly. Automation of the production planning process eliminated the manual process, and the new algorithmic processes were added.

    During the seven-month application of our system, from July 2012 to January 2013, visible outcomes were achieved as follows:

    • FG inventory level decreased by 24.51%,

    • Lead-time decreased by 23.34%, and

    • On-time delivery rate increased by 3.21%.

    The above numbers were calculated by sales and production departments of W-C MF. They had checked the FG inventory level in a week and compared the average level in July 2012 with the one in January 2013. The lead-time was calculated by the time between the placement of an order and delivery of the ordered item, and the average lead-time of an order in a month had decreased 23.34% from July 2012 to January 2013. The departments had also compared the monthly average rate of on-time delivery between July 2012 and January 2013, the ratio of the number of orders that meet their due dates to the number of total orders in a month.

    These significant improvements were realized owing to the:

    • decrease in phantom orders effected by bridging the communication gap between the sales and production departments and improving the transparency of the decision-making process;

    • improvement in the efficiency of the production planning process whereby the production schedule could now be planned within a few minutes with what-if analysis quickly performed by changing the input data in real time; and

    • change to 3-day production planning, which improved the company’s ability to respond to custommer orders.

    It may seem that the improvement would be due to the decrease of the workload or orders. However, the number of orders, the number of products, and the tightness of due dates were steady from January 2012 to January 2013. The tightness of due dates was measured by the average length between order-received dates and due dates.


    In this paper, we propose a heuristic algorithm for dealing with a single-machine E/T production planning problem with distinct due dates and discuss its actual implementation of W-C MF. We first introduced the business issues of W-C MF and the solution approach to resolving its core issue: its large FG inventory. We identified the underlying causes of this inventory issue through data analysis and interviews with the production planner and salespeople. After establishing the project’s direction, we developed a two-stage model for production planning and sequencing. To solve the planning model, we devised a heuristic combining the MST and SPT rules with a push-back procedure in consideration of the problem’s characteristics. Computational experiments on our heuristic with various criteria demonstrated its reliability and practicality for use in the actual operations of W-C MF. After the trial execution of our heuristic algorithm, it was successfully implemented enterprise-wide and decreased the unit’s FG inventory level by 24.5%.

    Further research is necessary to improve the pushback heuristic by further decreasing its divergence from optimal performance. Because the heuristic was unable to efficiently reduce the setup time, we need to add a novel procedure that will combine products of the same type while minimizing the penalty to save production time. In addition, further calibration of the E/T penalty values is necessary because those used herein were given by W-C MF without consideration of actual costs or financial data. Finally, there is a need to develop an analytical model for the maximum setup number to validate the number given by W-C MF because this number greatly affects the performance of our heuristic.



    Legacy planning process causing inventory pile-up.


    Impact of new planning system


    Operating time of each manufacturing step per day (The exact figures are confidential and are thus omitted here).


    Initial solution.


    Solution after applying the push-back procedure.


    Flowchart of push-back heuristic algorithm.


    Template for new production schedule.


    Push-back procedure

    Comparison of optimality and computation time: Number of jobs

    Comparison of optimality and computation time: Capacity

    Comparison of optimality and computation time: Number of products

    Comparison of optimality and computation time: Maximum allowable setup number


    1. Baker KR , Scudder GD (1990) Sequencing with earliness and tardiness penalties: a review , Operations Research, Vol.38 ; pp.22-36
    2. Baker KR , Trietsch D (2013) Principles of sequencing and scheduling , John Wiley and Sons,
    3. Clark AR , Morabito R , Toso EA (2010) Production setup-sequencing and lot-sizing at an animal nutrition plant through ATSP subtour elimination and patching , Journal of scheduling, Vol.13 ; pp.111-121
    4. Conway RW , Maxwell WL , Miller LW (2012) Theory of scheduling, Courier Corporation,
    5. Dauzere-Peres S , Lasserre JB (1994) Integration of lotsizing and scheduling decisions in a job-shop , European Journal of Operational Research, Vol.75 ; pp.413-426
    6. Drexl A , Kimms A (1997) Lot sizing and scheduling- survey and extensions , European Journal of Operational Research, Vol.99 ; pp.221-235
    7. Ferreira D , Morabito R , Rangel S (2009) Solution approaches for the soft drink integrated production lot sizing and scheduling problem , European Journal of Operational Research, Vol.196 ; pp.697-706
    8. Fleischmann B (1994) The discrete lot-sizing and scheduling problem with sequence-dependent setup costs , European Journal of Operational Research, Vol.75 ; pp.395-404
    9. Fry TD , Armstrong RD , Blackstone JH (1987) Minimizing weighted absolute deviation in single machine scheduling , IIE transactions, Vol.19 ; pp.445-450
    10. Garey MR , Tarjan RE , Wilfong GT (1988) One-processor scheduling with symmetric earliness and tardiness penalties , Mathematics of Operations Research, Vol.13 (2) ; pp.330-348
    11. Karimi B , Ghomi SF , Wilson JM (2003) The capacitated lot sizing problem: a review of models and algorithms , Omega, Vol.31 ; pp.365-378
    12. Kis T , Kovács A (2012) A cutting plane approach for integrated planning and scheduling , Computers and Operations Research, Vol.39 ; pp.320-327
    13. Korea Investment and Securities Co., Ltd (2011) Woongjin chemical(0080000). Company Report.,
    14. Lasserre JB (1992) An integrated model for job-shop planning and scheduling , Management Science, Vol.38 ; pp.1201-1211
    15. Lee CY , Choi JY (1995) A genetic algorithm for job sequencing problems with distinct due dates and general early-tardy penalty weights , Computers and Operations Research, Vol.22 ; pp.857-869
    16. Mateus GR , Ravetti MG , de Souza MC , Valeriano TM (2010) Capacitated lot sizing and sequence dependent setup scheduling: an iterative approach for integration , Journal of Scheduling, Vol.13 ; pp.245-259
    17. Oğuz C , Dincer C (1994) Single machine earliness- tardiness scheduling problems using the equal- slack rule , Journal of the Operational Research Society, ; pp.589-594
    18. Pinedo ML (2012) Scheduling: theory, algorithms, and systems , Springer Science and Business Media,
    19. Salomon M , Solomon MM , Van Wassenhove LN , Dumas Y , Dauzere-Peres S (1997) Solving the discrete lotsizing and scheduling problem with sequence dependent set-up costs and set-up times using the traveling salesman problem with time Windows , European Journal of Operational Research, Vol.100 ; pp.494-513
    20. Sung SW , Jang YJ , Lee DS (2013) Production Planning and Sequencing Optimization at Woongjin Chemical , Proceedings of the 14th Asia Pacific Industrial Engineering and Management Systems Conference,
    21. Trigeiro WW , Thomas LJ , McClain JO (1989) Capacitated lot sizing with setup times , Management science, Vol.35 ; pp.353-366
    22. Wan G , Yen BPC (2002) Tabu search for single machine scheduling with distinct due windows and weighted earliness/tardiness penalties , European Journal of Operational Research, Vol.142 ; pp.271-281
    23. Woongjin Chemical Co., Ltd (2012) Website of Woongjin Chemical. i,
    Do not open for a day Close