Scheduling a set of jobs with convex piecewise linear cost functions on a single-batch-processing machine

Hongbin Zhang, Yu Yang and Feng Wu

Omega, 2024, vol. 122, issue C

Abstract: We investigate a general single-batch-processing machine scheduling problem of minimizing the total costs of all jobs with general convex piecewise linear cost functions, where the processing time, due dates, and sizes of jobs are non-uniform. Since the studied problem is NP-hard and the objective is irregular, we adopt a practical 3-step method that starts from a specific job sequence, finds the optimal and near-optimal schedules of the given job sequence, and then iteratively improves the schedules. For the restricted problem where the job sequence is given, we propose a dynamic programming algorithm to obtain the optimal schedule. To further reduce the running time, we also devise a span-limit tree search (SLTS) approach to find the near-optimal schedule. We then design a local search method to improve the solutions solved by SLTS. Finally, we design a branch and bound algorithm with a lower bound method for small-sized instances. All proposed methods are based on our analysis of the mathematical properties of the scheduling problem, and extensive numerical experiments are conducted to demonstrate their effectiveness and efficiency.

Keywords: Scheduling; Convex piecewise linear cost function; Non-identical due dates; Dynamic programming; Branch and bound (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (2)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0305048323001226
Full text for ScienceDirect subscribers only

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:eee:jomega:v:122:y:2024:i:c:s0305048323001226

Ordering information: This journal article can be ordered from
http://www.elsevier.com/wps/find/supportfaq.cws_home/regional
https://shop.elsevie ... _01_ooc_1&version=01

DOI: 10.1016/j.omega.2023.102958

Access Statistics for this article

Omega is currently edited by B. Lev

More articles in Omega from Elsevier
Bibliographic data for series maintained by Catherine Liu ().