Premium
Algorithms for a two‐machine flowshop problem with jobs of two classes
Author(s) -
Jeong BongJoo,
Kim YeongDae,
Shim SangOh
Publication year - 2020
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12530
Subject(s) - tardiness , mathematical optimization , computer science , scheduling (production processes) , branch and bound , job shop scheduling , upper and lower bounds , heuristic , retard , class (philosophy) , algorithm , mathematics , artificial intelligence , schedule , psychology , mathematical analysis , psychiatry , operating system
We consider a problem of scheduling jobs of two classes of urgencies in a two‐machine flowshop with the objective of minimizing total tardiness of one class for urgent jobs and the maximum completion time of the other class for non‐urgent jobs. Urgent jobs are an important consideration in the real manufacturing systems, but it has not been studied due to the difficulty of the problem. In this research, a branch‐and‐bound (B&B) algorithm is proposed through developing lower bounds, dominance properties, and heuristic algorithms for obtaining an initial feasible solution. To evaluate the performance of the proposed algorithms, computational experiments on randomly generated instances are performed. Results of the experiments show that the suggested B&B algorithm can solve problems with up to 20 jobs in a reasonable amount of CPU time.