Scheduling of step-improving jobs with an identical improving rate

Abstract

Job processing times change over time in real-life production and manufacturing systems due to various factors including machine or worker learning, machine deterioration, production system upgrades or technological shocks. For step-improving processing times, job processing times are reduced by a certain rate if they start to process at, or after, a common critical date, which has wide applicability in real-world settings, such as data gathering networks and production systems with part-time workers. This paper considers single machine scheduling of minimizing total weighted completion time with step-improving jobs. The problem is shown to be intractable. Both exact and heuristic algorithms are developed, and the approximability of the heuristic algorithm is shown for a special case of the problem. Finally, computational experiments show that the proposed algorithms provide very effective and efficient solutions.

Keywords:

• Scheduling
• step-improving processing times
• dynamic programming
• approximation

Disclosure statement

No potential conflict of interest was reported by the author(s).

Correction Statement

This article has been republished with minor changes. These changes do not impact the academic content of the article.

Additional information

Funding

This work was supported by Global Research Network program through the Ministry of Education of the Republic of Korea and the National Research Foundation of Korea (NRF-2019S1A2A2031006).