Top

Journal of Scheduling

Published in:

15-06-2020

Scheduling two projects with controllable processing times in a single-machine environment

Authors: Byung-Cheon Choi, Myoung-Ju Park

Published in: Journal of Scheduling | Issue 5/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

We consider two single-machine scheduling problems in which two competing projects share one common resource. Each project has multiple interim assessments, and its own jobs are ordered completely. A tardy job incurs a tardiness penalty cost which can be avoided by compressing some jobs, which requires an additional cost. The performance measure of each project is the total tardiness penalty cost plus the total compression cost. The first problem minimizes the weighted sum of the performance measures of two projects, and the second problem minimizes the performance measure of one project with a constraint on that of the other. We show that the first problem is solvable in strongly polynomial time and the second is weakly NP-hard. Furthermore, we analyze how the computational complexity of each problem changes if the number of projects is more than two.

previous article Serial-batching scheduling with two agents to minimize makespan and maximum cost

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Agnetis, A., Billaut, J. C., Gawiejnowicz, S., Pacciarelli, D., & Soukhal, A. (2014). Multiagent scheduling: Models and algorithms. Berlin: Springer.CrossRef

Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2004). Scheduling problems with two competing agents. Operations Research, 52, 229–242.CrossRef

Agnetis, A., Mirchandani, P. B., Pacciarelli, D., & Pacifici, A. (2007). Multi-agent single machine scheduling. Annals of Operations Research, 150, 3–15.CrossRef

Ahuja, R. K., Magnanti, T. L., & Orlin, J. B. (1993). Network flows: Theory, algorithms and applications.,New Jersy: Prentice Hall.

Arbib, C., Smriglio, S., & Servilio, M. (2004). A competitive scheduling problem and its relevance to UMTS channel assignment. Networks, 44, 132–141.CrossRef

Baker, K. R., & Smith, J. C. (2003). A multiple-criterion model for machine scheduling. Journal of Scheduling, 6, 7–16.CrossRef

Cheng, T. C. E., Chen, Z.-L., & Li, C.-L. (1996). Single-machine scheduling with trade-off between number of tardy jobs and resource allocation. Operations Research Letters, 19, 237–242.CrossRef

Cheng, T. C. E., Chen, Z.-L., Li, C.-L., & Lin, B. M.-T. (1998). Scheduling to minimize the total compression and late costs. Naval Research Logistics, 45, 67–82.CrossRef

Cheng, T. C. E., Ng, C. T., & Yuan, J. J. (2006). Multi-agent scheduling on a single machine to minimize total weighted number of tardy jobs. Theoretical Computer Science, 362, 273–281.CrossRef

Choi, B. C., & Chung, J. B. (2014). Complexity results for the linear time-cost tradeoff problem with multiple milestones and completely ordered jobs. European Journal of Operational Research, 236, 61–68.CrossRef

Choi, B. C., & Park, M. J. (2015). A continuous time-cost tradeoff problem with multiple milestones and completely ordered jobs. European Journal of Operational Research, 244, 748–752.CrossRef

Falk, J. E., & Horowitz, J. L. (1972). Critical path problems with concave cost-time curves. Management Science, 19, 446–455.CrossRef

Ford, L. R., & Fulkerson, D. R. (1962). Flows in networks. New Jersy: Princeton University Press.

Fulkerson, D. R. (1961). A network flow computation for project cost curves. Management Science, 7, 167–178.CrossRef

Garey, M. R., & Johnson, D. S. (1979). Computers and intractability: A guide to the theory of NP-completeness. San Francisco: Freeman.

Gerstl, E., & Mosheiov, G. (2014). Single machine just-in-time scheduling problems with two competing agents. Naval Research Logistics, 61, 1–16.CrossRef

Hall, N. G., & Potts, C. N. (2004). Rescheduling for new orders. Operations Research, 52, 440–453.CrossRef

Hassin, R. (1992). Approximation schemes for the restricted shortest path problem. Mathematics of Operations Research, 517, 36–42.CrossRef

He, Y., Wei, Q., & Cheng, T. C. E. (2007). Single-machine scheduling with trade-off between number of tardy jobs and compression cost. Journal of Scheduling, 10, 303–310.CrossRef

Kelley, J. E. (1961). Critical path planning and scheduling: Mathematical basis. Operations Research, 9, 296–320.CrossRef

Lee, K. B., Choi, B. C., Leung, J. Y. T., & Pinedo, M. L. (2009). Approximation algorithms for multi-agent scheduling to minimize total weight completion time. Information Processing Letters, 109, 913–917.CrossRef

Leung, J. Y. T., Pinedo, M. L., & Wan, G. (2010). Competitive two-agent scheduling and its applications. Operations Research, 58, 458–469.CrossRef

Mor, B., & Mosheiov, G. (2017). A two-agent single machine scheduling problem with due-window assignment and a common flowallowance. Journal of Combinatorial Optimization, 33, 1454–1468.CrossRef

Perez-Gonzalez, P., & Framinan, J. M. (2014). A common framework and taxonomy for multicriteria scheduling problems with interfering and competing jobs: Multi-agent scheduling problems. European Journal of Operational Research, 235, 1–16.CrossRef

Roemer, T. A., & Ahmadi, R. (2004). Concurrent crashing and overlapping in product development. Operations Research, 52, 606–622.CrossRef

Shabtay, D., & Steiner, G. (2007). A survey of scheduling with controllable processing times. Discrete Applied Mathematics, 155, 1643–1666.CrossRef

Tseng, C.-T., Lia, C.-J., & Huang, K.-L. (2009). Minimizing total tardiness on a single machine with controllable processing times. Computers and Operations Research, 36, 1643–1666.CrossRef

Wan, G., Vakati, S. R., Leung, J. Y. T., & Pinedo, M. (2010). Scheduling two agents with controllable processing times. European Journal of Operational Research, 205, 528–539.CrossRef

Yin, Y., Cheng, S.-R., Cheng, T. C. E., Wang, D.-J., & Wu, C.-C. (2016). Just-in-time scheduling with two competing agents on unrelated parallel machines. Omega, 63, 41–47.CrossRef

Yin, Y., Cheng, T. C. E., Wang, D.-J., & Wu, C.-C. (2017). Two-agent flowshop scheduling to maximize the weighted number of just-in-time jobs. Journal of Scheduling, 20, 313–335.CrossRef

Yin, Y., Wang, Y., Cheng, T. C. E., Wang, D.-J., & Wu, C.-C. (2016). Two-agent single-machine scheduling to minimize the batch delivery cost. Computers and Industrial Engineering, 92, 16–30.CrossRef

Yin, Y., Wang, D.-J., Wu, C.-C., & Cheng, T. C. E. (2016). CON/SLK due date assignment and scheduling on a single machine with two agents. Naval Research Logistics, 63, 416–429.CrossRef

Yin, Y., Yang, Y., Wang, D., Cheng, T. C. E., & Wu, C.-C. (2018). Integrated production, inventory, and batch delivery scheduling with due date assignment and two competing agents. Naval Research Logistics, 65, 393–409.CrossRef

Title: Scheduling two projects with controllable processing times in a single-machine environment
Authors: Byung-Cheon Choi
Myoung-Ju Park
Publication date: 15-06-2020
Publisher: Springer US
Published in: Journal of Scheduling / Issue 5/2020
Print ISSN: 1094-6136
Electronic ISSN: 1099-1425
DOI: https://doi.org/10.1007/s10951-020-00658-3

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 5/2020

Dynamic speed scaling minimizing expected energy consumption for real-time tasks

Serial-batching scheduling with two agents to minimize makespan and maximum cost

Near-linear-time approximation algorithms for scheduling a batch-processing machine with setups and job rejection

Two-stage open-shop scheduling with a two-machine flow shop as a stage: approximation algorithms and empirical experiments

Scheduling a proportionate flow shop of batching machines

A decomposition heuristic for rotational workforce scheduling