A Review on Scheduling Problems for Minimizing the Number of Late Jobs
1
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
In this paper, scheduling problems for minimizing the number of late jobs are examined. First, possible real world applications are listed to motivate the interests in these problems. Next, a problem classification scheme is provided. Then, a brief review of the problems, both deterministic and stochastic, that have been effectively solved, is presented. When stochastic scheduling problems are dealt with, they can be further classified in terms of the probabilistic distributions of due dates. After the review, we point out that there still remain some research problems whose solutions would have a beneficial impact on the practice. These would include analytical complexity, alternative performance measures, and parallel machines.
Abstract
In this paper, scheduling problems for minimizing the number of late jobs are examined. First, possible real world applications are listed to motivate the interests in these problems. Next, a problem classification scheme is provided. Then, a brief review of the problems, both deterministic and stochastic, that have been effectively solved, is presented. When stochastic scheduling problems are dealt with, they can be further classified in terms of the probabilistic distributions of due dates. After the review, we point out that there still remain some research problems whose solutions would have a beneficial impact on the practice. These would include analytical complexity, alternative performance measures, and parallel machines.
참고문헌 (20)
- Balut, S. J., "Scheduling to Minimize the Number of Late Jobs When Set-Up and Processing Times are Uncertain", Management Science, 19, pp.1283~1288 (1973)
- Blazewic, J., "Scheduling preemptible tasks on parallel processors with information loss", Technique et Science Informatiques, 3, pp.415~420 (1984)
- Blazewicz, J., "Open shop scheduling problems with late work criteria", Discrete Applied Mathematics, 134, pp.1~24 (2004)
- Blau, R. A., "N-Job,One Machine Sequencing Problems under Uncertainty", Management Science, 20, pp.101~109 (1973)
- Boxma, O. J., "Minimizing the Expected Weighted Number of Tardy Jobs in Stochastic Flow Shops", Operations Research Letters, 5, pp.119~126 (1986)
- Cai, X., "Stochastic Scheduling on Parallel Machines subject to Random Breakdowns to Minimize Expected Costs for Earliness and Tardy Jobs", Operations Research, 47, pp.422~437 (1999)
- De, P., "On the Minimization of the Weighted Number of Tardy Jobs with Random Processing Times and Deadline", Computers and Operations Research, 18, pp.457~463 (1991)
- Derman, C., "A Renewal Decision Problem", Management Science, 24, pp.554~561 (1978)
- Emmons, H., "Scheduling Stochastic Jobs with Due Dates on Parallel Machines", European Journal of Operational Research, 47, pp.49~55 (1990)
- Held, M., "A Dynamic Programming Approach to Sequencing Problems", J.SIAM, 10, pp.196~210 (1962)
- Jang, W., "Dynamic Scheduling of Stochastic Jobs on a Single Machine", European Journal of Operational Research, 138, pp.518~530 (2002)
- Karp, R. M., "Complexity of Computer Computations" (1972), Plenum Press
- Kise, H., "On Balut’s Algorithm and NP-Completeness for a Chance- Constrained Scheduling Prob", Management Science, 29, pp.384~388 (1983)
- Moore, M. J., "An N Job,One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs", Management Science, 15, pp.102~109 (1968)
- Parker, G. R, "Discrete Optimization" (1988), Academic Press Inc
- Potts, C. N., "Single machine scheduling to minimize total late work", Operations Research, 40, pp.586~595 (1991)
- Pinedo, M., "Stochastic Scheduling with Release Dates and Due Dates", Operations Research, 31, pp.559~572 (1983)
- Pinedo, M., "Scheduling: Theory, Algorithms, and Systems" (2002), Prentice-Hall Inc
- Sarin, S. C., "Sequencing Jobs on a Single Machine with a Common Due Date and Stochastic Processing Times", European Journal of Operational Research, 51, pp.188~198 (1991)
- Sterna, M., "Late work scheduling in shop systems" (2006), Publishing House of Poznan University of Technology