EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

1918. Minimizing the number of late jobs and total late work with step-learning

Invited abstract in session WC-60: Machine Learning in Machine Scheduling, stream Project Management and Scheduling.

Wednesday, 12:30-14:00
Room: S09 (building: 101)

Authors (first author is the speaker)

1. Johnson Phosavanh
Discipline of Business Analytics, The University of Sydney
2. Daniel Oron
Business Analytics, The University of Sydney

Abstract

We study single-machine scheduling problems with step-learning, where an improvement in processing time is experienced if a job is started after a job-dependent learning-date. We consider minimizing two functions: the number of late jobs and the total late work, and we show that when at least a common due-date or common learning-date is assumed, the problem is NP-hard in the ordinary sense; however, when both are arbitrary, the problem becomes strongly NP-hard. For each of the problems where at least one of the dates is assumed to be common, we analyze the structure of an optimal job schedule with and without idle time and propose pseudo-polynomial time dynamic programming algorithms. We also show that the problem of minimizing the weighted number of late jobs with step-learning can be solved with a minor change to the algorithms for the unweighted case. In addition to this, we show that when a common due-date is assumed and no idle time is allowed, the problem of minimizing the total late work is equivalent to that of minimizing the makespan. Furthermore, we provide a more efficient algorithm to solve the problem of minimizing makespan under the assumption of a common learning-date than the one in the existing literature.

Keywords

Status: accepted

Back to the list of papers