1.INTRODUCTION
This paper introduces a singlemachine 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 finishedgoods (FG) inventories in the company’s micro filter business unit (WC 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 pileup. Phantom orders are here defined as speculative orders placed not by customers but by salespeople. Based on this problem identification, we formulated a singlemachine production planning model with a distinct due date, which minimizes the sum of earliness and tardiness penalties. Its solution heuristic was devised considering the WC MF’s operational requirements. The new system, consisting of scheduler and redesigned business process, was implemented in WC and decreased the FG inventory level by 24.5% within seven months (Figure 2).
1.1.Manufacturing system of WC
The manufacturing process of WC MF comprises six discrete processes: pleating, welding, endcapping, testing, bridging, and packaging. All six processes are semiautomated, 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 endcapping process. The workinprocess after endcapping is called the semifinished product. These products are then tested and passed to the bridging stage, at which requested options such as Orings 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 WC 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 WC MF, which operates in a maketoorder fashion, is timeconstrained and a single machine manufactures multiple items, we formulated a singlemachine multiitem capacitated lotsizing 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, singlelevel production system, and sequencedependent setup time. Trigeiro et al. (1989) studied a CLSP with sequenceindependent 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; DauzerePeres 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; KedadSidhoum 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 equalslack rule, we developed a heuristic for solving the E/T problem with distinct due dates.
1.2.3.Sequencing with SequenceDependent Setup Time
The manufacturing system of WC 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 sequencedependent 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 sequencedependent 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 mixedinteger linear programming formulation for production planning is described in Section 3, and our heuristic algorithm, the pushback 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 WC, and Section 7 concludes the paper with a summary and suggestions for future research.
2.PRODUCTION PLANNING PROBLEM IN WOONGJIN CHEMICAL
2.1.Company Introduction
WC 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. WC’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 WC 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. WC 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, WC 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, WC 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. WC 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, WC 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 WC MF production planner helped us to identify various business issues that were helpful in determining the appropriate solution approach.
2.2.1.Decrease in OnTime Deliveries
WC 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 ontime delivery rate.
2.2.2.Increase in number of product types
WC 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 sequencedependent. 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 realtime production planning and “whatif” analysis to answer such common questions: Is it possible to complete this new order by the required due date without affecting the ontime delivery of existing orders?
2.3.Problem Identification
The foregoing analysis allowed us to clarify the underlying causes of the excessive FG inventories. The WC 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 WC MF. Because most of the unit’s major customers wanted a quick delivery, but there was no realtime system for whatif 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 realtime whatif 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 singlemachine multiitem 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 orderdependent, 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 onethird 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 sequenceindependent. The unit E/T penalties are given as constant values. We formulate a mixedinteger 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 sequencedependent 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.MIXEDINTEGER LINEAR PROGRAMMING FORMULATION
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.
Indices
I set of products (i ∈ I)
J set of jobs (j ∈ J)
T set of time periods (t ∈ T)
Parameters
F_{jt} Penalty value for E/T when j is produced in time period t
d_{ij} Demand quantity of product i of job j
a_{i} Unit processing time of product i (unit: minutes)
c_{i} Setup time for product i (unit: minutes)
L_{t} Total available time in time period t (unit: minutes)
M_{it} Any large number greater than or equal to the total available time intime period t divided by unit processing time of product v (L_{t} / a_{i} )
S_{t} Maximum number of setup changes in time period t
Decision variable
x_{ijt} 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
z_{it} 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 F_{jt} 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 WC 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.
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 WC 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 $\left\text{1}\text{3}\right$ = 0.04 for earliness, whereas if job j is assigned to day 5 (t _{j} = 5), the penalty is 2$\left\text{5}\text{3}\right$ = 4 for tardiness. Because we know the unit penalties of earliness and tardiness and the D^{*}_{ j} for every job j, the values of F_{jt} can be calculated for all ts in a given planning horizon. In our implementation at WC MF, the penalty values were provided as a penalty matrix, comprising jobs in rows and time periods in columns.
3.3Mathematical Model
subject to
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 x_{ijt} 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 nonnegative or binary.
4.PROPOSED PUSHBACK HEURISTIC ALGORITHM
4.1.Requirements of the Heuristic
The following requirements needed to be satisfied in designing the solution method.

Easytounderstand 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 WC 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 realtime whatif analysis for due date promises and efficient production planning, the method need to find a reasonable solution within a few seconds.

Inhouse solution without using a commercial software: By the company policy, to develop an inhouse 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 inhouse 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 singlemachine multiitem 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} . Therefore,
Using Eq. (1) and Eq. (14), the objective function can be expressed as
Lemma 1.If the time resource (capacity) is unrestricted, producing job j at s _{j} for all j∈J is optimal for minimizing${\sum}_{j}{\mu}_{j}\left{t}_{j}\text{\u2212}{s}_{j}\right$ .
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 C_{j} denote the production completion time period of job j. C_{j} 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 C_{j} and dd _{j} , as follows.
The weighted absolute deviation between C_{j} and dd _{j} has been shown to be nontransitive (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 SLT_{j} = 3 and dd _{j} = 7 with SLT_{j} = 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 WC 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 firstpositioned 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 pushback algorithm to reduce the earliness penalty by pushing early jobs back to their ideal production time. Figure 5 illustrates the solution after the pushback procedure has been applied.
Lemma 2 (Pushback 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 nontardy 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 pushback will always have a smaller total penalty than the initial one because of the decrease in the earliness penalty.
Proof. Let ETB_{j} and ETA_{j} be the E/T penalties for job j before and after its pushback 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 pushback from t _{j} to D^{*}_{ j} is possible and D^{*}_{j} − t _{j} >0. Therefore, * 0. ETB_{j} = μ _{j}$\left{t}_{j}\text{\u2212}{D}_{j}^{\ast}\right$ >0. After the pushback procedure, the updated production time period, t′_{j} , becomes equivalent to D^{*}_{j} In this case, Then, ETA_{j} = μ _{j}$\left{{t}^{\prime}}_{j}\text{\u2212}{D}_{j}^{\ast}\right$ =0, and ETA_{j} < ETB_{j} . This complete the proof. □
4.3.Algorithm Procedure
In this subsection, we explain the procedure of the pushback heuristic in detail. Figure 6 presents a brief flowchart of the heuristic.
Step 1. Sequence jobs with the MST rule and the SPT rule.
11. Calculate the slack time of each job.
12. Sequence the jobs in nondecreasing order of their slack times (MST rule).
13. 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 nondecreasing 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.
21. Calculate the production time of each job in the sequence by using the calculation method in the Step 13.
22. Comparing the cumulative production time of the jobs in the sequence with the daily available time L_{t} , 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.
23. Store the time period of each job j as iniTM_{j} .
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 lastpositioned job, iniT_{[N]}, is later than its ideal production time period D^{*}_{[N]}, then terminate the algorithm because performing the pushback 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 pushback procedure. See Algorithm 1.
5.COMPUTATIONAL RESULTS
To be practicable and reliable in daily operations of WC 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 WC MF. The unit’s fiveyear (20072011) 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.
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 realtime production planning and whatif analysis.
5.2.Capacity
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 WC 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 WC 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 righthand 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.
6.MODEL EXECUTION
A prototype of our heuristic algorithm was executed in the actual factory operations of WC MF in July 2012. During the onemonth 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 WC 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 sevenmonth application of our system, from July 2012 to January 2013, visible outcomes were achieved as follows:

FG inventory level decreased by 24.51%,

Leadtime decreased by 23.34%, and

Ontime delivery rate increased by 3.21%.
The above numbers were calculated by sales and production departments of WC 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 leadtime was calculated by the time between the placement of an order and delivery of the ordered item, and the average leadtime 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 ontime 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 decisionmaking process;

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

change to 3day 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 orderreceived dates and due dates.
7.CONCLUSION
In this paper, we propose a heuristic algorithm for dealing with a singlemachine E/T production planning problem with distinct due dates and discuss its actual implementation of WC MF. We first introduced the business issues of WC 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 twostage model for production planning and sequencing. To solve the planning model, we devised a heuristic combining the MST and SPT rules with a pushback 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 WC MF. After the trial execution of our heuristic algorithm, it was successfully implemented enterprisewide 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 WC 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 WC MF because this number greatly affects the performance of our heuristic.