Permutation flowshop scheduling with simple linear deterioration

ABSTRACT

This article addresses permutation flowshop scheduling problems with simple linear deterioration. The objectives are to minimize logarithm of the makespan, total logarithm of the completion time, total weighted logarithm of the completion time, and the sum of the quadratic job logarithms of the completion times. Approximation algorithms and their worst-case bounds are presented and analysed. Branch-and-bound algorithms are also proposed to solve the problems optimally. Computational experiments are performed to illustrate the algorithms.

KEYWORDS:

• Scheduling
• deteriorating job
• flowshop
• worst-case bound
• approximation algorithm

Disclosure statement

No potential conflict of interest was reported by the authors.

Additional information

Funding

This research was supported by the National Science Foundation of China [71673220, 71471120, 71501082]; the Support Program for Innovative Talents in Liaoning University of China [LR2016017]; and the Liaoning BaiQianWan Talents Program of China.