## 1 Introduction  
Parallel machine scheduling (PMS) is a classic problem in the literature. In general, PMS can be classified into three categories according to the types of machines, namely, identical machines, uniform machines, and unrelated machines [1]. This research deals with the PMS problem for identical machines in which the processing time of a job is the same for all machines [2]. The objective is to minimize the makespan and total tardiness. The motivation for this study is a practical problem at a plastic pallet manufacturing company in Taiwan. The main manufacturing process for the plastic pallets is injection molding. At the company, there are several identical injection molding machines. Each plastic pallet only needs to be processed by one of these machines. When a machine completes one batch of a product, additional resources are required for the changeover if a different product is to be produced subsequently. The main purpose of a changeover is to change the molds. The weights of the molds are between 10 and 20 tons, and the heaviest can be as much as 24 tons. A thirty-five-ton crane is used to move the molds. For reasons of safety, the molds are moved slowly and at least two operators must be involved. While one worker is operating the crane, the other has to watch and ensure all situations are safe. After the molds are fixed in the machines, the machines require a series of adjustments. All operations are executed slowly, so it takes 6 to 8 h to exchange a mold. There is only one crane, and only one team can undertake the mold exchange operation, so only one machine can be changed at a time. Moreover, in order to avoid accidents, changeovers can only happen on a day shift, so there can only be one changeover per day. The company has a make-to-stock strategy. Because of the lack of inventory space, no safety stocks are kept for any products. Once an order for a product is received, if there is insufficient inventory to fill the order, the company will arrange to produce the product. Because of the resources needed to change molds, production batch sizes are always larger than the quantity of the received order and determined on the basis of historical demand data; a product with higher demand is produced in larger batches. Additional product is stored in the warehouse for future orders. The last day on which the mold must be exchanged in order to produce product \(i\), \(LS_{i}\), can be estimated from the due date of the most recent order for which there is insufficient inventory to satisfy the order. In order to satisfy requests from customers, the day that machine exchanges the mold for product \(i\), \(DS_{i}\), should be earlier than \(LS_{i}\). Figure 1 illustrates the case in which the inventory of product \(i\) is too low for the new order and \(DS_{i}\) < \(LS_{i}\). In Figure 1, the quantity of the order for product \(i\) is \(A_{i}\), which is larger than the current inventory. In order to satisfy the order, the machine mold is changed on day \(DS_{i}\). After the 8 h changeover, the machine starts to produce a batch and the inventory increases. There is more inventory than \(Ai\) on the due date, when quantity \(Ai\) is delivered to the customer and the inventory is reduced. The machine continues to produce the product and the inventory increases again. When the total current production output equals the production batch, the machine stops producing product \(i\). The total production time for product \(i\) is \(PT_{i}\). If \(DS_{i}\) > \(LS_{i}\), the inventory will be less than \(A_{i}\) on the due date. The whole order will be late, and it will be delivered to the customer once the inventory is equal to \(A_{i}\). The tardiness of the order can be calculated by \(DS_{i}-LS_{i}\), and the total tardiness for the order is \(A_{i}\) (\(DS_{i}-LS_{i}\)). The inventory status for delayed orders is illustrated in Figure 2.  
Typically, the identical PMS problem is an NP-hard problem [3].