Exact algorithms for solving the constrained parallel-machine scheduling problems with divisible processing times and penalties

Jianping Li (), Runtao Xie (), Junran Lichen (), Guojun Hu (), Pengxiang Pan () and Ping Yang ()
Additional contact information
Jianping Li: Yunnan University
Runtao Xie: Yunnan University
Junran Lichen: Beijing University of Chemical Technology
Guojun Hu: Yunnan University
Pengxiang Pan: Yunnan University
Ping Yang: Yunnan University

Journal of Combinatorial Optimization, 2023, vol. 45, issue 4, No 3, 19 pages

Abstract: Abstract In this paper, we address the constrained parallel-machine scheduling problem with divisible processing times and penalties (the CPS-DTP problem), which is a further generalization of the parallel-machine scheduling problem with divisible processing times (the PS-DT problem). Concretely, given a set M of m identical machines and a set J of n independent jobs, each job has a processing time and a penalty, the processing times of these n jobs are divisible, and we implement these n jobs under the requirement that each job in J must be either continuously executed on one machine with its processing time, or rejected with its penalty that we must pay for. We may consider three versions of the CPS-DTP problem, respectively. (1) The constrained parallel-machine scheduling problem with divisible processing times and total penalties (the CPS-DTTP problem) is asked to find a subset A of J and a schedule T for jobs in A to satisfy the aforementioned requirement, the objective is to minimize the makespan of such a schedule T for jobs in A plus the summation of penalties paid for jobs not in A; (2) The constrained parallel-machine scheduling problem with divisible processing times and maximum penalty (the CPS-DTMP problem) is asked to find a subset A of J and a schedule T for jobs in A to satisfy the aforementioned requirement, the objective is to minimize the makespan of such a schedule T for jobs in A plus maximum penalty paid for jobs not in A; (3) The constrained parallel-machine scheduling problem with divisible processing times and bounded penalty (the CPS-DTBP problem) is asked to find a subset A of J and a schedule T for jobs in A to satisfy the aforementioned requirement and the summation of penalties paid for jobs not in A is no more than a fixed bound, the objective is to minimize the makespan of such a schedule T for jobs in A. As our main contributions, we design three exact algorithms to solve the CPS-DTTP problem, the CPS-DTMP problem and the CPS-DTBP problem, and these three algorithms run in time $$O((n\log n+nm)C)$$ O ( ( n log n + n m ) C ) , $$O(n^{2}\log n)$$ O ( n 2 log n ) and $$O((n\log n+nm)\log C)$$ O ( ( n log n + n m ) log C ) , respectively, where C is the optimal value of same instance for the PS-DT problem.

Keywords: Combinatorial optimization; Constrained parallel-machine scheduling; Divisible processing times; Penalties; Exact algorithms (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01028-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

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:spr:jcomop:v:45:y:2023:i:4:d:10.1007_s10878-023-01028-3

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01028-3

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().