DOI: 10.14457/tu.the.2020.79
title: Dynamic dispatching rule based-heuristics for unrelated parallel machine scheduling problem with machine and sequence-dependent setup time

description: This study involves unrelated parallel machine scheduling with machine- and sequence-dependent setup time. Unrelated machines have different production rates, therefore, they provide different processing times of the same job on different machines. In addition, they are different in terms of the capability to process jobs, i.e. unrelated machines can process different subsets of alljobs. Moreover, setup time is different based on machine- and sequence of jobs to be processed on the machine. The system under study is modeled after a production at largest steel pipe manufacturer in Thailand. The system consists of 10 unrelated parallel machines that is used to produce 413 products that belong to 26 product families. On the average, the number of customerorders are ranged from 1,359 to 3,639 orders, and the variety of products in each customer order can be up to 40 products. System measures of performance considered in this study includemakespan (the completion of last job), the total tardiness, and the number of tardy jobs. Four mixed integer programming models are developed to represent the problem, one model for each measure of performance, and the other model for finding compromise solution thatconsider all three measures at the same time. These models can only be used to solve small problem instances to optimality. Optimal solutions of the small problem instances provide insight into thecharacteristics of the problem and the measures of performance. To handle large problem instance in the real system, dynamic dispatching rule-basedheuristic algorithm is developed. The algorithm features three single dispatching rules that are adapted to take into account the machine- and sequence-dependent setup times, and six combineddispatching rules with rule switching time. Computational experiments are performed on 18 large problem instances, where each instance is from a month of real production data, to determineeffective rule under different demand scenario. Since there are three measures of performance, effective rule depends on the weights of importance that a decision maker gives to the three measures. Therefore, an extensive multi-criteria decision making analysis is performed to identify conditions, characterized by the weights of importance, where each rule is the most effective.Our findings suggest that, among the three single rules there are two effective rules which are shortest completion time (SCT) and shortest completion time based on earliest due date (SC-EDD). Among the six combined rules, two effective rules are a combined SC-EDD and SCT withrule switching time of 200 hours (SC-EDD & SCT: 200), and a combined SCT and SC-EDD with 450 hours of rule switching time (SCT & SC-EDD: 450). Under low demand scenario, [SCT &SC-EDD: 450] is the most effective when the DM puts no more than 4% for weight of importance on the total tardiness, otherwise, [SC-EDD & SCT: 200] is the most effective. For high demandscenario, effective rule changes from SCT, to [SC-EDD & SCT: 200], to [SCT & SC-EDD: 450], and to SC-EDD, as the important weight of the total tardiness increases. The findings provide aguideline to choose the most effective rules, as a decision maker specifies their level of importance to each of the three measures of performance.