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. 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.
    2. 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.
    3. 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.
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. George B. Dantzig, 1957. "Discrete-Variable Extremum Problems," Operations Research, INFORMS, vol. 5(2), pages 266-288, April.
    10. 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.
    11. 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.
    12. F. Biélen & N. Demoulin, 2007. "Waiting time influence on the satisfaction-loyalty relationship in services," Post-Print hal-00254951, HAL.
    13. 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.
    14. 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.
    15. 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.
    16. 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.
    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. 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.
    2. 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.
    3. 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).
    4. 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.
    5. 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.
    6. 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.
    7. 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.
    8. 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.
    9. 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).
    10. 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.
    11. 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.
    12. Shuyu Zhou & Yeming (Yale) Gong & René de Koster, 2016. "Designing self-storage warehouses with customer choice," International Journal of Production Research, Taylor & Francis Journals, vol. 54(10), pages 3080-3104, May.
    13. Wishon, Christopher & Villalobos, J. Rene, 2016. "Robust efficiency measures for linear knapsack problem variants," European Journal of Operational Research, Elsevier, vol. 254(2), pages 398-409.
    14. Jinwen Ou & Xueling Zhong, 2017. "Order acceptance and scheduling with consideration of service level," Annals of Operations Research, Springer, vol. 248(1), pages 429-447, January.
    15. Mohamadreza Dabiri & Mehdi Yazdani & Bahman Naderi & Hassan Haleh, 2022. "Modeling and solution methods for hybrid flow shop scheduling problem with job rejection," Operational Research, Springer, vol. 22(3), pages 2721-2765, July.
    16. Xueling Zhong & Jinwen Ou, 2017. "Improved approximation algorithms for parallel machine scheduling with release dates and job rejection," 4OR, Springer, vol. 15(4), pages 387-406, December.
    17. Lei, Deming & Guo, Xiuping, 2015. "A parallel neighborhood search for order acceptance and scheduling in flow shop environment," International Journal of Production Economics, Elsevier, vol. 165(C), pages 12-18.
    18. Shah, Ruchit & Reed, Patrick, 2011. "Comparative analysis of multiobjective evolutionary algorithms for random and correlated instances of multiobjective d-dimensional knapsack problems," European Journal of Operational Research, Elsevier, vol. 211(3), pages 466-479, June.
    19. R. Micale & C. M. La Fata & M. Enea & G. La Scalia, 2021. "Regenerative scheduling problem in engineer to order manufacturing: an economic assessment," Journal of Intelligent Manufacturing, Springer, vol. 32(7), pages 1913-1925, October.
    20. Mavrotas, George & Florios, Kostas & Figueira, José Rui, 2015. "An improved version of a core based algorithm for the multi-objective multi-dimensional knapsack problem: A computational study and comparison with meta-heuristics," Applied Mathematics and Computation, Elsevier, vol. 270(C), pages 25-43.

    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.