IDEAS home Printed from https://ideas.repec.org/a/eee/ejores/v228y2013i1p24-32.html
   My bibliography  Save this article

Fast approximation schemes for Boolean programming and scheduling problems related to positive convex Half-Product

Author

Listed:
  • Kellerer, Hans
  • Strusevich, Vitaly

Abstract

We address a version of the Half-Product Problem and its restricted variant with a linear knapsack constraint. For these minimization problems of Boolean programming, we focus on the development of fully polynomial-time approximation schemes with running times that depend quadratically on the number of variables. Applications to various single machine scheduling problems are reported: minimizing the total weighted flow time with controllable processing times, minimizing the makespan with controllable release dates, minimizing the total weighted flow time for two models of scheduling with rejection.

Suggested Citation

  • Kellerer, Hans & Strusevich, Vitaly, 2013. "Fast approximation schemes for Boolean programming and scheduling problems related to positive convex Half-Product," European Journal of Operational Research, Elsevier, vol. 228(1), pages 24-32.
    • Handle: RePEc:eee:ejores:v:228:y:2013:i:1:p:24-32
    DOI: 10.1016/j.ejor.2012.12.028
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0377221713000027
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ejor.2012.12.028?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Janiak, Adam & Kovalyov, Mikhail Y. & Kubiak, Wieslaw & Werner, Frank, 2005. "Positive half-products and scheduling with controllable processing times," European Journal of Operational Research, Elsevier, vol. 165(2), pages 416-422, September.
    2. Xu, Zhou, 2012. "A strongly polynomial FPTAS for the symmetric quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 218(2), pages 377-381.
    3. Nicholas G. Hall & Marc E. Posner, 1991. "Earliness-Tardiness Scheduling Problems, I: Weighted Deviation of Completion Times About a Common Due Date," Operations Research, INFORMS, vol. 39(5), pages 836-846, October.
    4. T. Badics & E. Boros, 1998. "Minimization of Half-Products," Mathematics of Operations Research, INFORMS, vol. 23(3), pages 649-660, August.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Kellerer, Hans & Rustogi, Kabir & Strusevich, Vitaly A., 2020. "A fast FPTAS for single machine scheduling problem of minimizing total weighted earliness and tardiness about a large common due date," Omega, Elsevier, vol. 90(C).
    2. Halman, Nir & Kellerer, Hans & Strusevich, Vitaly A., 2018. "Approximation schemes for non-separable non-linear boolean programming problems under nested knapsack constraints," European Journal of Operational Research, Elsevier, vol. 270(2), pages 435-447.
    3. Dolgui, Alexandre & Kovalev, Sergey & Pesch, Erwin, 2015. "Approximate solution of a profit maximization constrained virtual business planning problem," Omega, Elsevier, vol. 57(PB), pages 212-216.
    4. Liqi Zhang & Lingfa Lu & Jinjiang Yuan, 2016. "Two-machine open-shop scheduling with rejection to minimize the makespan," OR Spectrum: Quantitative Approaches in Management, Springer;Gesellschaft für Operations Research e.V., vol. 38(2), pages 519-529, March.
    5. Baruch Mor & Dana Shapira, 2022. "Single machine scheduling with non-availability interval and optional job rejection," Journal of Combinatorial Optimization, Springer, vol. 44(1), pages 480-497, August.
    6. 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.
    7. Zhong, Xueling & Ou, Jinwen & Wang, Guoqing, 2014. "Order acceptance and scheduling with machine availability constraints," European Journal of Operational Research, Elsevier, vol. 232(3), pages 435-441.
    8. Oron, Daniel, 2021. "Two-agent scheduling problems under rejection budget constraints," Omega, Elsevier, vol. 102(C).
    9. Luo, Wenchang & Gu, Boyuan & Lin, Guohui, 2018. "Communication scheduling in data gathering networks of heterogeneous sensors with data compression: Algorithms and empirical experiments," European Journal of Operational Research, Elsevier, vol. 271(2), pages 462-473.
    10. Sergey Kovalev, 2015. "Maximizing total tardiness on a single machine in $$O(n^2)$$ O ( n 2 ) time via a reduction to half-product minimization," Annals of Operations Research, Springer, vol. 235(1), pages 815-819, December.
    11. Hans Kellerer & Vitaly A. Strusevich, 2016. "Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications," Annals of Operations Research, Springer, vol. 240(1), pages 39-94, May.

    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.
    1. Hans Kellerer & Vitaly A. Strusevich, 2016. "Optimizing the half-product and related quadratic Boolean functions: approximation and scheduling applications," Annals of Operations Research, Springer, vol. 240(1), pages 39-94, May.
    2. Kellerer, Hans & Rustogi, Kabir & Strusevich, Vitaly A., 2020. "A fast FPTAS for single machine scheduling problem of minimizing total weighted earliness and tardiness about a large common due date," Omega, Elsevier, vol. 90(C).
    3. Halman, Nir & Kellerer, Hans & Strusevich, Vitaly A., 2018. "Approximation schemes for non-separable non-linear boolean programming problems under nested knapsack constraints," European Journal of Operational Research, Elsevier, vol. 270(2), pages 435-447.
    4. Sergey Kovalev, 2015. "Maximizing total tardiness on a single machine in $$O(n^2)$$ O ( n 2 ) time via a reduction to half-product minimization," Annals of Operations Research, Springer, vol. 235(1), pages 815-819, December.
    5. Mikhail Y. Kovalyov & Marie-Claude Portmann & Ammar Oulamara, 2006. "Optimal testing and repairing a failed series system," Journal of Combinatorial Optimization, Springer, vol. 12(3), pages 279-295, November.
    6. Liu Guiqing & Li Kai & Cheng Bayi, 2015. "Preemptive Scheduling with Controllable Processing Times on Parallel Machines," Journal of Systems Science and Information, De Gruyter, vol. 3(1), pages 68-76, February.
    7. Philip Kaminsky & Onur Kaya, 2008. "Scheduling and due‐date quotation in a make‐to‐order supply chain," Naval Research Logistics (NRL), John Wiley & Sons, vol. 55(5), pages 444-458, August.
    8. Baals, Julian & Emde, Simon & Turkensteen, Marcel, 2023. "Minimizing earliness-tardiness costs in supplier networks—A just-in-time truck routing problem," European Journal of Operational Research, Elsevier, vol. 306(2), pages 707-741.
    9. Ali Kordmostafapour & Javad Rezaeian & Iraj Mahdavi & Mahdi Yar Farjad, 2022. "Scheduling unrelated parallel machine problem with multi-mode processing times and batch delivery cost," OPSEARCH, Springer;Operational Research Society of India, vol. 59(4), pages 1438-1470, December.
    10. Xu, Zhou, 2012. "A strongly polynomial FPTAS for the symmetric quadratic knapsack problem," European Journal of Operational Research, Elsevier, vol. 218(2), pages 377-381.
    11. Evgeny Gurevsky & Sergey Kovalev & Mikhail Y. Kovalyov, 2021. "Min-max controllable risk problems," 4OR, Springer, vol. 19(1), pages 93-101, March.
    12. John J. Clifford & Marc E. Posner, 2000. "High Multiplicity in Earliness-Tardiness Scheduling," Operations Research, INFORMS, vol. 48(5), pages 788-800, October.
    13. N. V. R. Mahadev & Aleksandar Pekeč & Fred S. Roberts, 1998. "On the Meaningfulness of Optimal Solutions to Scheduling Problems: Can an Optimal Solution be Nonoptimal?," Operations Research, INFORMS, vol. 46(3-supplem), pages 120-134, June.
    14. Mosheiov, Gur & Shadmon, Michal, 2001. "Minmax earliness-tardiness costs with unit processing time jobs," European Journal of Operational Research, Elsevier, vol. 130(3), pages 638-652, May.
    15. Zhi-Long Chen, 1997. "Scheduling with batch setup times and earliness-tardiness penalties," European Journal of Operational Research, Elsevier, vol. 96(3), pages 518-537, February.
    16. Cai, X., 1995. "Minimization of agreeably weighted variance in single machine systems," European Journal of Operational Research, Elsevier, vol. 85(3), pages 576-592, September.
    17. Feng Li & Zhi-Long Chen & Zhi-Long Chen, 2017. "Integrated Production, Inventory and Delivery Problems: Complexity and Algorithms," INFORMS Journal on Computing, INFORMS, vol. 29(2), pages 232-250, May.
    18. Francis Sourd, 2009. "New Exact Algorithms for One-Machine Earliness-Tardiness Scheduling," INFORMS Journal on Computing, INFORMS, vol. 21(1), pages 167-175, February.
    19. Mosheiov, Gur, 2004. "Simultaneous minimization of total completion time and total deviation of job completion times," European Journal of Operational Research, Elsevier, vol. 157(2), pages 296-306, September.
    20. Britta Schulze & Michael Stiglmayr & Luís Paquete & Carlos M. Fonseca & David Willems & Stefan Ruzika, 2020. "On the rectangular knapsack problem: approximation of a specific quadratic knapsack problem," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 92(1), pages 107-132, August.

    Corrections

    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:eee:ejores:v:228:y:2013:i:1:p:24-32. 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: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/locate/eor .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.