IDEAS home Printed from https://ideas.repec.org/a/pal/jorsoc/v68y2017i9d10.1057_s41274-017-0238-z.html
   My bibliography  Save this article

Maximizing total job value on a single machine with job selection

Author

Listed:
  • Joonyup Eun

    (Vanderbilt University Medical Center)

  • Chang Sup Sung

    (Korea Advanced Institute of Science and Technology (KAIST))

  • Eun-Seok Kim

    (Middlesex University)

Abstract

This paper describes a single-machine scheduling problem of maximizing total job value with a machine availability constraint. The value of each job decreases over time in a stepwise fashion. Several solution properties of the problem are developed. Based on the properties, a branch-and-bound algorithm and a heuristic algorithm are derived. These algorithms are evaluated in the computational study, and the results show that the heuristic algorithm provides effective solutions within short computation times.

Suggested Citation

  • Joonyup Eun & Chang Sup Sung & Eun-Seok Kim, 2017. "Maximizing total job value on a single machine with job selection," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 68(9), pages 998-1005, September.
    • Handle: RePEc:pal:jorsoc:v:68:y:2017:i:9:d:10.1057_s41274-017-0238-z
    DOI: 10.1057/s41274-017-0238-z
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1057/s41274-017-0238-z
    File Function: Abstract
    Download Restriction: Access to full text is restricted to subscribers.
    File URL: https://libkey.io/10.1057/s41274-017-0238-z?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. Mohammad Reisi-Nafchi & Ghasem Moslehi, 2015. "Integrating two-agent scheduling and order acceptance problems to maximise total revenue by bounding each agent penalty function," International Journal of Services and Operations Management, Inderscience Enterprises Ltd, vol. 20(3), pages 358-384.
    2. Simon Thevenin & Nicolas Zufferey & Marino Widmer, 2016. "Order acceptance and scheduling with earliness and tardiness penalties," Journal of Heuristics, Springer, vol. 22(6), pages 849-890, December.
    3. J-B Wang & J-J Wang & P Ji, 2011. "Scheduling jobs with chain precedence constraints and deteriorating jobs," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 62(9), pages 1765-1770, September.
    4. Voutsinas, Theodore G. & Pappis, Costas P., 2002. "Scheduling jobs with values exponentially deteriorating over time," International Journal of Production Economics, Elsevier, vol. 79(3), pages 163-169, October.
    5. George B. Dantzig, 1957. "Discrete-Variable Extremum Problems," Operations Research, INFORMS, vol. 5(2), pages 266-288, April.
    6. Nicholas G. Hall & Marc E. Posner, 2001. "Generating Experimental Data for Computational Testing with Machine Scheduling Applications," Operations Research, INFORMS, vol. 49(6), pages 854-865, December.
    7. Martello, Silvano & Pisinger, David & Toth, Paolo, 2000. "New trends in exact algorithms for the 0-1 knapsack problem," European Journal of Operational Research, Elsevier, vol. 123(2), pages 325-332, June.
    8. Mohammad Reisi-Nafchi & Ghasem Moslehi, 2015. "Two-agent order acceptance and scheduling to maximise total revenue," European Journal of Industrial Engineering, Inderscience Enterprises Ltd, vol. 9(5), pages 664-691.
    9. Ou, Jinwen & Zhong, Xueling & Wang, Guoqing, 2015. "An improved heuristic for parallel machine scheduling with rejection," European Journal of Operational Research, Elsevier, vol. 241(3), pages 653-661.
    10. F. Biélen & N. Demoulin, 2007. "Waiting time influence on the satisfaction-loyalty relationship in services," Post-Print hal-00254951, HAL.
    11. Zhang, Xiandong & (Yale) Gong, Yeming & Zhou, Shuyu & de Koster, René & van de Velde, Steef, 2016. "Increasing the revenue of self-storage warehouses by optimizing order scheduling," European Journal of Operational Research, Elsevier, vol. 252(1), pages 69-78.
    12. S-W Lin & K-C Ying, 2013. "Increasing the total net revenue for single machine order acceptance and scheduling problems using an artificial bee colony algorithm," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 64(2), pages 293-311, February.
    13. Slotnick, Susan A., 2011. "Order acceptance and scheduling: A taxonomy and review," European Journal of Operational Research, Elsevier, vol. 212(1), pages 1-11, July.
    14. Borges, Adilson & Herter, Márcia Maurer & Chebat, Jean-Charles, 2015. "“It was not that long!†: The effects of the in-store TV screen content and consumers emotions on consumer waiting perception," Journal of Retailing and Consumer Services, Elsevier, vol. 22(C), pages 96-106.
    15. Xiandong Zhang & Yeming Gong & Shuyu Zhou & René de Koster & Steef van de Velde, 2016. "Increasing the Revenue of Self-Storage Warehouses by Optimizing Order Scheduling," Post-Print hal-02313355, HAL.
    16. 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.
    Full references (including those not matched with items on IDEAS)

    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. Tarhan, İstenç & Oğuz, Ceyda, 2022. "A matheuristic for the generalized order acceptance and scheduling problem," European Journal of Operational Research, Elsevier, vol. 299(1), pages 87-103.
    2. Li, Xin & Ventura, Jose A., 2020. "Exact algorithms for a joint order acceptance and scheduling problem," International Journal of Production Economics, Elsevier, vol. 223(C).
    3. Hanane Krim & Nicolas Zufferey & Jean-Yves Potvin & Rachid Benmansour & David Duvivier, 2022. "Tabu search for a parallel-machine scheduling problem with periodic maintenance, job rejection and weighted sum of completion times," Journal of Scheduling, Springer, vol. 25(1), pages 89-105, February.
    4. Xin Li & José A. Ventura & Kevin A. Bunn, 2021. "A joint order acceptance and scheduling problem with earliness and tardiness penalties considering overtime," Journal of Scheduling, Springer, vol. 24(1), pages 49-68, February.
    5. Boysen, Nils & Briskorn, Dirk & Schwerdfeger, Stefan, 2019. "Matching supply and demand in a sharing economy: Classification, computational complexity, and application," European Journal of Operational Research, Elsevier, vol. 278(2), pages 578-595.
    6. Wang, Xiuli & Zhu, Qianqian & Cheng, T.C.E., 2015. "Subcontracting price schemes for order acceptance and scheduling," Omega, Elsevier, vol. 54(C), pages 1-10.
    7. Sbihi, Abdelkader, 2010. "A cooperative local search-based algorithm for the Multiple-Scenario Max-Min Knapsack Problem," European Journal of Operational Research, Elsevier, vol. 202(2), pages 339-346, April.
    8. Shi, Ye & Yu, Yugang & Dong, Yuxuan, 2021. "Warehousing platform’s revenue management: A dynamic model of coordinating space allocation for self-use and rent," European Journal of Operational Research, Elsevier, vol. 293(1), pages 167-176.
    9. Ou, Jinwen & Zhong, Xueling, 2017. "Bicriteria order acceptance and scheduling with consideration of fill rate," European Journal of Operational Research, Elsevier, vol. 262(3), pages 904-907.
    10. Belleh Fontem & Megan Price, 2021. "Joint client selection and contract design for a risk-averse commodity broker in a two-echelon supply chain," Annals of Operations Research, Springer, vol. 307(1), pages 111-138, December.
    11. Mhand Hifi & Hedi Mhalla & Slim Sadfi, 2005. "Sensitivity of the Optimum to Perturbations of the Profit or Weight of an Item in the Binary Knapsack Problem," Journal of Combinatorial Optimization, Springer, vol. 10(3), pages 239-260, November.
    12. Paola Cappanera & Marco Trubian, 2005. "A Local-Search-Based Heuristic for the Demand-Constrained Multidimensional Knapsack Problem," INFORMS Journal on Computing, INFORMS, vol. 17(1), pages 82-98, February.
    13. Toth, Paolo, 2000. "Optimization engineering techniques for the exact solution of NP-hard combinatorial optimization problems," European Journal of Operational Research, Elsevier, vol. 125(2), pages 222-238, September.
    14. Simon Thevenin & Nicolas Zufferey & Marino Widmer, 2016. "Order acceptance and scheduling with earliness and tardiness penalties," Journal of Heuristics, Springer, vol. 22(6), pages 849-890, December.
    15. Lei He & Mathijs Weerdt & Neil Yorke-Smith, 2020. "Time/sequence-dependent scheduling: the design and evaluation of a general purpose tabu-based adaptive large neighbourhood search algorithm," Journal of Intelligent Manufacturing, Springer, vol. 31(4), pages 1051-1078, April.
    16. Ayodeji, Yusuf & Rjoub, Husam & Özgit, Hale, 2023. "Achieving sustainable customer loyalty in airports: The role of waiting time satisfaction and self-service technologies," Technology in Society, Elsevier, vol. 72(C).
    17. Garaus, Marion & Wagner, Udo, 2019. "Let me entertain you – Increasing overall store satisfaction through digital signage in retail waiting areas," Journal of Retailing and Consumer Services, Elsevier, vol. 47(C), pages 331-338.
    18. Zhe Yuan & Haoxuan Xu & Yeming (Yale) Gong & Chengbin Chu & Jinlong Zhang, 2017. "Designing public storage warehouses with high demand for revenue maximisation," International Journal of Production Research, Taylor & Francis Journals, vol. 55(13), pages 3686-3700, July.
    19. Zhong, Xueling & Fan, Jie & Ou, Jinwen, 2022. "Coordinated scheduling of the outsourcing, in-house production and distribution operations," European Journal of Operational Research, Elsevier, vol. 302(2), pages 427-437.
    20. Peihai Liu & Xiwen Lu, 2020. "New approximation algorithms for machine scheduling with rejection on single and parallel machine," Journal of Combinatorial Optimization, Springer, vol. 40(4), pages 929-952, November.

    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:pal:jorsoc:v:68:y:2017:i:9:d:10.1057_s41274-017-0238-z. 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.palgrave-journals.com/ .

    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.