Approximation algorithms for the W-prize-collecting scheduling problem on a single machine with submodular rejection penalties
Author
Abstract
Suggested Citation
DOI: 10.1007/s10878-025-01314-2
Download full text from publisher
As the access to this document is restricted, you may want to search for a different version of it.
References listed on IDEAS
- Yuhui Sun & Wei Yu & Zhaohui Liu, 2023. "Approximation algorithms for some min–max and minimum stacker crane cover problems," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-25, January.
- Guo, Jia & Bard, Jonathan F., 2024. "Weekly scheduling for freight rail engineers & trainmen," Transportation Research Part B: Methodological, Elsevier, vol. 183(C).
- Hongye Zheng & Suogang Gao & Wen Liu & Weili Wu & Ding-Zhu Du & Bo Hou, 2022. "Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 343-353, August.
- Ao Zhao & Qian Liu & Yang Zhou & Min Li, 2023. "Approximation Algorithms for Matroid and Knapsack Means Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 40(01), pages 1-16, February.
- Jiaxuan Zhang & Suogang Gao & Bo Hou & Wen Liu, 2023. "An approximation algorithm for the clustered path travelling salesman problem," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-12, May.
- Shiming Li & Wei Yu, 2023. "Approximation Algorithms for the Maximum-Weight Cycle/Path Packing Problems," Asia-Pacific Journal of Operational Research (APJOR), World Scientific Publishing Co. Pte. Ltd., vol. 40(04), pages 1-16, August.
- Jiang, Yiwei & Wu, Mengjing & Chen, Xin & Dong, Jianming & Cheng, T.C.E. & Blazewicz, Jacek & Ji, Min, 2024. "Online early work scheduling on parallel machines," European Journal of Operational Research, Elsevier, vol. 315(3), pages 855-862.
- Xing Chai & Wenhua Li & C. T. Ng & T. C. E. Cheng, 2023. "Approximation algorithms for batch scheduling with processing set restrictions," Journal of Scheduling, Springer, vol. 26(6), pages 523-533, December.
- Jianping Li & Pengxiang Pan & Junran Lichen & Lijian Cai & Wencheng Wang & Suding Liu, 2023. "Approximation algorithms for solving the heterogeneous Chinese postman problem," Journal of Combinatorial Optimization, Springer, vol. 45(1), pages 1-15, January.
- Bo Hou & Tianjiao Guo & Suogang Gao & Guanghua Wang & Weili Wu & Wen Liu, 2024. "W-prize-collecting scheduling problem on parallel machines," Journal of Combinatorial Optimization, Springer, vol. 48(3), pages 1-9, October.
- Xiaofei Liu & Weidong Li, 2020. "Approximation Algorithm for the Single Machine Scheduling Problem with Release Dates and Submodular Rejection Penalty," Mathematics, MDPI, vol. 8(1), pages 1-11, January.
Most related items
These are the items that most often cite the same works as this one and are cited by the same works as this one.- Qi Wang & Bo Hou & Gengsheng Zhang & Yisheng Zhou & Wen Liu, 2025. "Approximation algorithms for the partition set cover problem with penalties," Journal of Combinatorial Optimization, Springer, vol. 49(5), pages 1-15, July.
- Xiaofei Liu & Man Xiao & Weidong Li & Yaoyu Zhu & Lei Ma, 2023. "Algorithms for single machine scheduling problem with release dates and submodular penalties," Journal of Combinatorial Optimization, Springer, vol. 45(4), pages 1-18, May.
- Guojun Hu & Pengxiang Pan & Suding Liu & Ping Yang & Runtao Xie, 2024. "The prize-collecting single machine scheduling with bounds and penalties," Journal of Combinatorial Optimization, Springer, vol. 48(2), pages 1-13, September.
- Zhichao Geng & Lingfa Lu, 2025. "Multiple identical serial-batch machines scheduling with release dates and submodular rejection penalties," Journal of Combinatorial Optimization, Springer, vol. 49(2), pages 1-27, March.
- Bo Hou & Tianjiao Guo & Suogang Gao & Guanghua Wang & Weili Wu & Wen Liu, 2024. "W-prize-collecting scheduling problem on parallel machines," Journal of Combinatorial Optimization, Springer, vol. 48(3), pages 1-9, October.
- Hongye Zheng & Suogang Gao & Wen Liu & Weili Wu & Ding-Zhu Du & Bo Hou, 2022. "Approximation algorithm for the parallel-machine scheduling problem with release dates and submodular rejection penalties," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 343-353, August.
- Xinmeng Guo & Wei Yu & Zhaohui Liu, 2025. "Approximating the maximum weight cycle/path partition in graphs with weights one and two," Journal of Combinatorial Optimization, Springer, vol. 49(5), pages 1-26, July.
More about this item
Keywords
Scheduling problem; Submodular rejection penalty; W-prize-collecting; Approximation algorithm; Primal-dual;All these keywords.
Statistics
Access and download statisticsCorrections
All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:jcomop:v:49:y:2025:i:5:d:10.1007_s10878-025-01314-2. See general information about how to correct material in RePEc.
If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.
If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .
If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.
For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .
Please note that corrections may take a couple of weeks to filter through the various RePEc services.