Exact and heuristic algorithms for scheduling on two identical machines with early work maximization. (June 2020)

• Record Type: Journal Article
• Authors: Chen, Xin; Wang, Wen; Xie, Pengyu; Zhang, Xingong; Sterna, Małgorzata; Błażewicz, Jacek
• Is Part Of: Computers & industrial engineering. Volume 144(2020)
• Publication Date: 2020-06
• Subjects: Scheduling -- Early work -- Identical machines -- Branch-and-bound algorithm -- Heuristic algorithm; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2020.106449
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: LPT has an approximation ratio 10 9 for common due date version. The lower bound of LPT's approximation ratio can be proven to 11 12 . A branch-and-bound algorithm is proposed for arbitrary due date version. The performances of the proposed algorithms are tested by numerical experiments. Abstract: Early work criterion is a new-proposed objective in the scheduling field, in which the early parts of jobs processed before their due dates are aimed to be maximized. In this paper, we consider such a criterion for scheduling on two identical machines. For the simplified model with a common due date of all jobs, we show that the classical LPT (Largest Processing Time first) heuristic is an approximation algorithm with the worst case ratio 10 9 . For the general model with arbitrary due dates, we propose a branch-and-bound algorithm equipped with several truncation rules, upper and lower bounds techniques, as well as dominance rules to solve small scale instances, while a genetic algorithm to solve big instances. Finally, the efficiencies of the proposed algorithms are validated by the numerical experiments, in which we show that the branch-and-bound algorithm can find the exact solutions within a reasonable time-consumption when an instance is small, and the genetic algorithm is an efficient approach when the problem instance turns to big.