Abstract
We identify two classes of machine scheduling problems with time lags that possess Polynomial-Time Approximation Schemes (PTASs). These classes together, one for minimizing makespan and one for minimizing total completion time, include many well-studied time lag scheduling problems. The running times of these approximation schemes are polynomial in the number of jobs, but exponential in the number of machines and the ratio between the largest time lag and the smallest positive operation time.
These classes constitute the first PTAS results for scheduling problems with time lags.
Article PDF
Similar content being viewed by others
References
Achugbue, J. O., & Chin, F. Y. (1982). Scheduling the open shop to minimize mean flow time. SIAM Journal on Computing, 11, 709–720.
Ageev, A. A. (2008). A 3/2-approximation for the proportionate two-machine flow shop scheduling with minimum delays. Lecture Notes in Computer Science, 4927, 55–66.
Baptiste, P., & Timkovsky, V. G. (2004). Shortest path to nonpreemptive schedules of unit-time jobs on two identical parallel machines with minimum total completion time. Mathematical Methods of Operations Research, 60(1), 145–153.
Brucker, P., Knust, S., Cheng, T. C. E., & Shakhlevich, N. V. (2004). Complexity results for flow-shop and open-shop scheduling problems with transportation delays. Annals of Operations Research, 129(1), 81–106.
Bruno, J., Jones III, J. W., & So, K. (1980). Deterministic scheduling with pipelined processors. IEEE Transactions on Computers, 29(4), 308–316.
Dell’Amico, M. (1996). Shop problems with two machines and time lags. Operations Research, 44(5), 777–787.
Dell’Amico, M., & Vaessens, R. J. M. (1995). Flow and open shop scheduling on two machines with transportation times and machine-independent processing times is NP-hard. Materiali di discussione, 1, 141.
Fishkin, A. V., Jansen, K., & Mastrolilli, M. (2002). A PTAS for shop scheduling with release dates to minimize the average weighted completion time (Technical Report: IDSIA-19-02).
Garey, M. R., Johnson, D. S., & Sethi, R. (1976). The complexity of flowshop and jobshop scheduling. Mathematics of Operations Research, 1(2), 117–129.
Gonzalez, T., & Sahni, S. (1976). Open shop scheduling to minimize finish time. Journal of the ACM, 23(4), 665–679.
Graham, R. L., Lawler, E. L., Lenstra, J. K., & Kan, A. H. G. R. (1979). Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics, 5(2), 287–326.
Gupta, J. N. D. (1996). Comparative evaluation of heuristic algorithms for the single machine scheduling problem with two operations per job and time-lags. Journal of Global Optimization, 9(3), 239–253.
Hall, L. A. (1994). A polynomial approximation scheme for a constrained flow-shop scheduling problem. Mathematics of Operations Research, 19(1), 68–85.
Jackson, J. R. (1956). An extension of Johnson’s results on job lot scheduling. Naval Research Logistics Quarterly, 3(3), 201–203.
Johnson, S. M. (1954). Optimal two-and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1), 61–68.
Karuno, Y., & Nagamochi, H. (2003). A better approximation for the two-machine flowshop scheduling problem with time lags. In Algorithms and computation: 14th international symposium, ISAAC 2003, Kyoto, Japan, December 15–17, 2003: Proceedings.
Kern, W., & Nawijn, W. N. (1991). Scheduling multi-operation jobs with time lags on a single machine. In 2nd Twente workshop on graphs and combinatorial optimization pp. 81–86 (SEEN 92-24905 15–64).
Kovalyov, M. Y., & Werner, F. (1997). A polynomial approximation scheme for problem F2/r j /C max . Operations Research Letters, 20(2), 75–79.
Mitten, L. G. (1959). Sequencing n jobs on two machines with arbitrary time lags. Management Science, 5(3), 293–298.
Potts, C. N., & Whitehead, J. D. (2007). Heuristics for a coupled-operation scheduling problem. Journal of the Operational Research Society, 58(10), 1375–1388.
Rayward-Smith, V. J., & Rebaine, D. (1992). Open shop scheduling with delays. Informatique Théorique et Applications (Imprimé), 26(5), 439–448.
Rebaine, D. (2004). Scheduling the two-machine open shop problem with non-symmetric time delays. In Congres ASAC 2004, Quebec, Canada.
Rebaine, D., & Strusevich, V. A. (1999). Two-machine open shop scheduling with special transportation times. The Journal of the Operational Research Society, 50(7), 756–764.
Strusevich, V. A. (1999). A heuristic for the two-machine open-shop scheduling problem with transportation times. Discrete Applied Mathematics, 93(2–3), 287–304.
Strusevich, V. A., & Rebaine, D. (1995). Two-machine open shop with transportation times. In ECCO VIII, May 8–10, Poznan, Poland.
Timkovsky, V. G. (1997). A polynomial-time algorithm for the two-machine unit-time release-date job-shop schedule-length problem. Discrete Applied Mathematics, 77(2), 185–200.
Yu, W. (1996). The two-machine flow shop problem with delays and the one-machine total tardiness problem. Eindhoven University of Technology.
Yu, W., Hoogeveen, H., & Lenstra, J. K. (2004). Minimizing makespan in a two-machine flow Shop with delays and unit-time operations is NP-hard. Journal of Scheduling, 7(5), 333–348.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
Open Access This is an open access article distributed under the terms of the Creative Commons Attribution Noncommercial License (https://creativecommons.org/licenses/by-nc/2.0), which permits any noncommercial use, distribution, and reproduction in any medium, provided the original author(s) and source are credited.
About this article
Cite this article
Zhang, X., van de Velde, S. Polynomial-time approximation schemes for scheduling problems with time lags. J Sched 13, 553–559 (2010). https://doi.org/10.1007/s10951-009-0134-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10951-009-0134-8