On the minmax common-due-date problem: extensions to position-dependent processing times, job rejection, learning effect, uniform machines and flowshops. Issue 3 (4th March 2021)

• Record Type: Journal Article
• Authors: Mosheiov, Gur; Pruwer, Sharon
• Is Part Of: Engineering optimization. Volume 53:Issue 3(2021)
• Page Start: 408
• Page End: 424
• Publication Date: 2021-03-04
• Subjects: Scheduling -- position-dependent processing times -- job rejection -- uniform machines -- flowshop; Engineering design -- Periodicals; Mathematical optimization -- Periodicals; 620.0042
• DOI: 10.1080/0305215X.2020.1735380
• Languages: English
• ISSNs: 0305-215X

Abstract

Abstract : A classical single machine minmax common due-date assignment (CON) problem is studied. The problem is extended (independently) to the following settings: (1) general position-dependent job processing times are assumed, and an efficient O ( n 4 ) solution procedure is introduced; (2) the option of job rejection is allowed, and this case is shown to be solved in O ( n 5 ); (3) a deterioration effect is considered, and an O ( n 2 ) solution algorithm is proposed; (4) parallel uniform machines are considered; and (5) the machine setting is that of a permutation flowshop. The last two settings are known to be NP hard, and efficient heuristic procedures are introduced and shown numerically to produce very small optimality gaps.