IDEAS home Printed from https://ideas.repec.org/a/eee/proeco/v198y2018icp191-200.html
   My bibliography  Save this article

Single machine scheduling with controllable processing times and an unavailability period to minimize the makespan

Author

Listed:
  • Shabtay, Dvir
  • Zofi, Moshe

Abstract

We study a single machine scheduling problem, where job processing times are controllable, and there is a fixed machine unavailability interval. We assume that the job processing time is a convex decreasing function of the amount of resource allocated to its processing operation. We further assume that there is a budget restriction on the total resource allocation cost. Our aim is to find a job schedule that minimizes the makespan. We prove that the problem is NP-hard and develop both a constant factor approximation algorithm and a fully polynomial time approximation scheme (FPTAS) for solving it. The FPTAS is obtained despite the fact that we could not design a pseudo-polynomial time algorithm for finding the optimal solution.

Suggested Citation

  • Shabtay, Dvir & Zofi, Moshe, 2018. "Single machine scheduling with controllable processing times and an unavailability period to minimize the makespan," International Journal of Production Economics, Elsevier, vol. 198(C), pages 191-200.
    • Handle: RePEc:eee:proeco:v:198:y:2018:i:c:p:191-200
    DOI: 10.1016/j.ijpe.2017.12.025
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0925527317304310
    Download Restriction: Full text for ScienceDirect subscribers only
    File URL: https://libkey.io/10.1016/j.ijpe.2017.12.025?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. Allaoui, H. & Artiba, A. & Elmaghraby, S.E. & Riane, F., 2006. "Scheduling of a two-machine flowshop with availability constraints on the first machine," International Journal of Production Economics, Elsevier, vol. 99(1-2), pages 16-27, February.
    2. J. Breit & G. Schmidt & V. A. Strusevich, 2003. "Non-preemptive two-machine open shop scheduling with non-availability constraints," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 57(2), pages 217-234, May.
    3. Oron, Daniel, 2016. "Scheduling controllable processing time jobs with position-dependent workloads," International Journal of Production Economics, Elsevier, vol. 173(C), pages 153-160.
    4. Kacem, Imed & Chu, Chengbin, 2008. "Worst-case analysis of the WSPT and MWSPT rules for single machine scheduling with one planned setup period," European Journal of Operational Research, Elsevier, vol. 187(3), pages 1080-1089, June.
    5. Shabtay, Dvir & Kaspi, Moshe, 2002. "Optimization of the machining economics problem under the failure replacement strategy," International Journal of Production Economics, Elsevier, vol. 80(3), pages 213-230, December.
    6. Chung-Yee Lee & Lei Lei, 2001. "Multiple-Project Scheduling with Controllable Project Duration and Hard Resource Constraint: Some Solvable Cases," Annals of Operations Research, Springer, vol. 102(1), pages 287-307, February.
    7. Yang, Dar-Li & Lai, Chien-Jung & Yang, Suh-Jenq, 2014. "Scheduling problems with multiple due windows assignment and controllable processing times on a single machine," International Journal of Production Economics, Elsevier, vol. 150(C), pages 96-103.
    8. Kacem, Imed & Chu, Chengbin, 2008. "Efficient branch-and-bound algorithm for minimizing the weighted sum of completion times on a single machine with one availability constraint," International Journal of Production Economics, Elsevier, vol. 112(1), pages 138-150, March.
    9. Liao, Ching-Jong & Shyur, Der-Lin & Lin, Chien-Hung, 2005. "Makespan minimization for two parallel machines with an availability constraint," European Journal of Operational Research, Elsevier, vol. 160(2), pages 445-456, January.
    10. Schmidt, Gunter, 2000. "Scheduling with limited machine availability," European Journal of Operational Research, Elsevier, vol. 121(1), pages 1-15, February.
    11. Breit, Joachim, 2007. "Improved approximation for non-preemptive single machine flow-time scheduling with an availability constraint," European Journal of Operational Research, Elsevier, vol. 183(2), pages 516-524, December.
    12. Dvir Shabtay & George Steiner, 2008. "The single-machine earliness-tardiness scheduling problem with due date assignment and resource-dependent processing times," Annals of Operations Research, Springer, vol. 159(1), pages 25-40, March.
    13. Clyde L. Monma & Alexander Schrijver & Michael J. Todd & Victor K. Wei, 1990. "Convex Resource Allocation Problems on Directed Acyclic Graphs: Duality, Complexity, Special Cases, and Extensions," Mathematics of Operations Research, INFORMS, vol. 15(4), pages 736-748, November.
    14. Leyvand, Yaron & Shabtay, Dvir & Steiner, George, 2010. "A unified approach for scheduling with convex resource consumption functions using positional penalties," European Journal of Operational Research, Elsevier, vol. 206(2), pages 301-312, October.
    15. Michael A. Trick, 1994. "Scheduling Multiple Variable-Speed Machines," Operations Research, INFORMS, vol. 42(2), pages 234-248, April.
    16. Janiak, Adam & Kovalyov, Mikhail Y., 1996. "Single machine scheduling subject to deadlines and resource dependent processing times," European Journal of Operational Research, Elsevier, vol. 94(2), pages 284-291, October.
    17. Yaron Leyvand & Dvir Shabtay & George Steiner, 2010. "Optimal delivery time quotation to minimize total tardiness penalties with controllable processing times," IISE Transactions, Taylor & Francis Journals, vol. 42(3), pages 221-231.
    18. Daniel Oron, 2016. "Scheduling controllable processing time jobs in a deteriorating environment," Journal of the Operational Research Society, Palgrave Macmillan;The OR Society, vol. 67(3), pages 535-535, March.
    19. Imed Kacem, 2009. "Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval," Journal of Combinatorial Optimization, Springer, vol. 17(2), pages 117-133, February.
    20. Shabtay, Dvir & Bensoussan, Yaron & Kaspi, Moshe, 2012. "A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system," International Journal of Production Economics, Elsevier, vol. 136(1), pages 67-74.
    21. Liu, Peihai & Lu, Xiwen, 2016. "Integrated production and job delivery scheduling with an availability constraint," International Journal of Production Economics, Elsevier, vol. 176(C), pages 1-6.
    22. Sadfi, Cherif & Penz, Bernard & Rapine, Christophe & Blazewicz, Jacek & Formanowicz, Piotr, 2005. "An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints," European Journal of Operational Research, Elsevier, vol. 161(1), pages 3-10, February.
    23. Kayan, Rabia K. & Akturk, M. Selim, 2005. "A new bounding mechanism for the CNC machine scheduling problems with controllable processing times," European Journal of Operational Research, Elsevier, vol. 167(3), pages 624-643, December.
    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. Shabtay, Dvir, 2022. "Single-machine scheduling with machine unavailability periods and resource dependent processing times," European Journal of Operational Research, Elsevier, vol. 296(2), pages 423-439.
    2. 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.
    3. Sinisterra, Wilfrido Quiñones & Lima, Victor Hugo Resende & Cavalcante, Cristiano Alexandre Virginio & Aribisala, Adetoye Ayokunle, 2023. "A delay-time model to integrate the sequence of resumable jobs, inspection policy, and quality for a single-component system," Reliability Engineering and System Safety, Elsevier, vol. 230(C).
    4. Byung-Cheon Choi & Myoung-Ju Park, 2022. "Single-machine scheduling with resource-dependent processing times and multiple unavailability periods," Journal of Scheduling, Springer, vol. 25(2), pages 191-202, April.
    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. Rossit, Daniel A. & Vásquez, Óscar C. & Tohmé, Fernando & Frutos, Mariano & Safe, Martín D., 2021. "A combinatorial analysis of the permutation and non-permutation flow shop scheduling problems," European Journal of Operational Research, Elsevier, vol. 289(3), pages 841-854.

    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. Shabtay, Dvir, 2022. "Single-machine scheduling with machine unavailability periods and resource dependent processing times," European Journal of Operational Research, Elsevier, vol. 296(2), pages 423-439.
    2. Yaron Leyvand & Dvir Shabtay & George Steiner & Liron Yedidsion, 2010. "Just-in-time scheduling with controllable processing times on parallel machines," Journal of Combinatorial Optimization, Springer, vol. 19(3), pages 347-368, April.
    3. Shabtay, Dvir & Steiner, George & Zhang, Rui, 2016. "Optimal coordination of resource allocation, due date assignment and scheduling decisions," Omega, Elsevier, vol. 65(C), pages 41-54.
    4. Lili Zuo & Zhenxia Sun & Lingfa Lu & Liqi Zhang, 2019. "Single-Machine Scheduling with Rejection and an Operator Non-Availability Interval," Mathematics, MDPI, vol. 7(8), pages 1-8, July.
    5. Kellerer, Hans & Kubzin, Mikhail A. & Strusevich, Vitaly A., 2009. "Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval," European Journal of Operational Research, Elsevier, vol. 199(1), pages 111-116, November.
    6. Seyed Habib A. Rahmati & Abbas Ahmadi & Kannan Govindan, 2018. "A novel integrated condition-based maintenance and stochastic flexible job shop scheduling problem: simulation-based optimization approach," Annals of Operations Research, Springer, vol. 269(1), pages 583-621, October.
    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. Dvir Shabtay & Moshe Kaspi, 2006. "Minimizing the makespan in open‐shop scheduling problems with a convex resource consumption function," Naval Research Logistics (NRL), John Wiley & Sons, vol. 53(3), pages 204-216, April.
    9. Leyvand, Yaron & Shabtay, Dvir & Steiner, George, 2010. "A unified approach for scheduling with convex resource consumption functions using positional penalties," European Journal of Operational Research, Elsevier, vol. 206(2), pages 301-312, October.
    10. Lu Liu & Jian-Jun Wang & Xiao-Yuan Wang, 2016. "Single machine due-window assignment scheduling with resource-dependent processing times to minimise total resource consumption cost," International Journal of Production Research, Taylor & Francis Journals, vol. 54(4), pages 1186-1195, February.
    11. Dujuan Wang & Yunqiang Yin & T.C.E. Cheng, 2017. "A bicriterion approach to common flow allowances due window assignment and scheduling with controllable processing times," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(1), pages 41-63, February.
    12. Zhenpeng Li & Congdian Cheng, 2023. "The Expected Competitive Ratio on a Kind of Stochastic-Online Flowtime Scheduling with Machine Subject to an Uncertain Breakdown," Mathematics, MDPI, vol. 11(11), pages 1-12, May.
    13. Oron, Daniel, 2016. "Scheduling controllable processing time jobs with position-dependent workloads," International Journal of Production Economics, Elsevier, vol. 173(C), pages 153-160.
    14. Yedidsion, Liron & Shabtay, Dvir, 2017. "The resource dependent assignment problem with a convex agent cost function," European Journal of Operational Research, Elsevier, vol. 261(2), pages 486-502.
    15. Yim, Seho & Hong, Sung-Pil & Park, Myoung-Ju & Chung, Yerim, 2022. "Inverse interval scheduling via reduction on a single machine," European Journal of Operational Research, Elsevier, vol. 303(2), pages 541-549.
    16. 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.
    17. Kacem, Imed & Chu, Chengbin, 2008. "Efficient branch-and-bound algorithm for minimizing the weighted sum of completion times on a single machine with one availability constraint," International Journal of Production Economics, Elsevier, vol. 112(1), pages 138-150, March.
    18. Dvir Shabtay & George Steiner, 2007. "Optimal Due Date Assignment and Resource Allocation to Minimize the Weighted Number of Tardy Jobs on a Single Machine," Manufacturing & Service Operations Management, INFORMS, vol. 9(3), pages 332-350, March.
    19. Shabtay, Dvir & Bensoussan, Yaron & Kaspi, Moshe, 2012. "A bicriteria approach to maximize the weighted number of just-in-time jobs and to minimize the total resource consumption cost in a two-machine flow-shop scheduling system," International Journal of Production Economics, Elsevier, vol. 136(1), pages 67-74.
    20. Shi-Sheng Li & Ren-Xia Chen, 2022. "Minimizing total weighted late work on a single-machine with non-availability intervals," Journal of Combinatorial Optimization, Springer, vol. 44(2), pages 1330-1355, September.

    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:proeco:v:198:y:2018:i:c:p:191-200. 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/ijpe .

    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.