An application of unrelated parallel machine scheduling with sequence-dependent setups at Vestel Electronics

• Published in: Computers & operations research 2019-11, Vol.111, p.130-140
• Main Authors: Ekici, Ali, Elyasi, Milad, Özener, Okan Örsan, Sarıkaya, Merve Burcu
• Format: Article
• Language: English
• Subjects: Algorithms; Assembly lines; Compatibility; Decision making; Electronics; Electronics industry; Matheuristic; Operations research; Production scheduling; Schedules; Scheduling; Search algorithms; Sequence-dependent setups; Sequential scheduling; Set partitioning; Tabu search; Television; Unrelated parallel machines; Workload; Workloads
• ISSN: 0305-0548; 1873-765X; 0305-0548
• DOI: 10.1016/j.cor.2019.06.007

•Vestel Electronics faces a variant of parallel machine scheduling in TV production.•A set partitioning approach and a tabu search-based matheuristic are proposed.•Proposed approaches provide production schedules better than the current practice. In this paper, we analyze a variant of the unrelated parallel machine scheduling problem with the objective of minimizing the total tardiness and earliness in the presence of sequence-dependent setups, unequal release times, machine-job compatibility restrictions and workload balance requirements. This study is motivated by the production scheduling operations at a television manufacturer, Vestel Electronics. Vestel produces LCD/LED TVs and has a significant market share in the consumer electronics sector in Europe. TV manufacturing is planned based on a make-to-order strategy, and Vestel uses 15 assembly lines to produce 110 different product groups and 3817 different models. Once the orders are received, production scheduling is performed at the beginning of each month, and the goal is to satisfy the demand on time as much as possible. The decision maker has to consider several factors including job-assembly line compatibility, the release and due dates of the jobs and a workload balance among different assembly lines when forming the production schedule. To address this problem, we propose a wide range of heuristics including (i) a sequential algorithm, (ii) a tabu search algorithm, (iii) a random set partitioning approach, and (iv) a novel matheuristic approach utilizing the local intensification and global diversification powers of a tabu search algorithm. Through a computational study, we observe that all the proposed approaches not only significantly outperform the current practice but also provide solutions with around 5% less optimality gap compared to a benchmark algorithm in the literature.