Rescheduling for new orders on a single machine with rejection

Kan Fang, Wenchang Luo, Michael L. Pinedo, Miaomiao Jin and Lingfa Lu

Journal of the Operational Research Society, 2024, vol. 75, issue 2, 346-360

Abstract: We consider a single machine rescheduling problem where a set of original jobs have been scheduled to minimize the total weighted completion time. However, before formal processing begins, a new set of jobs arrives and creates a disruption. The decision maker can reject a subset of the new jobs by paying certain rejection penalties, and reschedule the original and the remaining new jobs without excessively disrupting the original schedule, which is measured by the maximum completion time deviation for any original jobs between the original and adjusted schedules. The objective is to minimize the sum of total weighted completion time of the original jobs and the accepted new jobs in the adjusted schedule, the weighted maximum completion time deviation and the total rejection cost. We first provide a dynamic programming-based exact algorithm running in pseudo-polynomial time, and then propose a fully polynomial time approximation scheme. Given the NP-hardness for the studied problem, our result is the best possible from the approximation algorithm perspective. In addition, we conduct extensive computational experiments to evaluate the performance of our proposed methods, and provide some managerial insights on their applicability under different situations.

Date: 2024
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://hdl.handle.net/10.1080/01605682.2023.2197000 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tjorxx:v:75:y:2024:i:2:p:346-360

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/tjor20

DOI: 10.1080/01605682.2023.2197000

Access Statistics for this article

Journal of the Operational Research Society is currently edited by Tom Archibald

More articles in Journal of the Operational Research Society from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().