Single-Machine Scheduling with Rejection and an Operator Non-Availability Interval

Lili Zuo, Zhenxia Sun, Lingfa Lu and Liqi Zhang
Additional contact information
Lili Zuo: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
Zhenxia Sun: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
Lingfa Lu: School of Mathematics and Statistics, Zhengzhou University, Zhengzhou 450001, China
Liqi Zhang: College of Information and Management Science, Henan Agricultural University, Zhengzhou 450002, China

Mathematics, 2019, vol. 7, issue 8, 1-8

Abstract: In this paper, we study two scheduling problems on a single machine with rejection and an operator non-availability interval. In the operator non-availability interval, no job can be started or be completed. However, a crossover job is allowed such that it can be started before this interval and completed after this interval. Furthermore, we also assume that job rejection is allowed. That is, each job is either accepted and processed in-house, or is rejected by paying a rejection cost. Our task is to minimize the sum of the makespan (or the total weighted completion time) of accepted jobs and the total rejection cost of rejected jobs. For two scheduling problems with different objective functions, by borrowing the previous algorithms in the literature, we propose a pseudo-polynomial-time algorithm and a fully polynomial-time approximation scheme (FPTAS), respectively.

Keywords: scheduling with rejection; machine non-availability; operator non-availability; dynamic programming; FPTAS (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2019
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
https://www.mdpi.com/2227-7390/7/8/668/pdf (application/pdf)
https://www.mdpi.com/2227-7390/7/8/668/ (text/html)

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:gam:jmathe:v:7:y:2019:i:8:p:668-:d:251924

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().