Property of symmetry for some single processor scheduling problems with due interval assignment

• Autorzy: Janiak A. , Marek M.
• Języki publikacji: EN

Abstrakty

EN

In this paper, we consider two single processor scheduling problems, in which a due interval should be assigned to each job. The due interval is a generalization of a due date and describes a time interval in which a job should be finished. Both problems considered have different mathematical models of the due intervals and the same criterion in which we minimize the weighted sum of the total earliness, the total tardiness and me due interval size. At first, we prove some properties of the optimal solution and we construct an optimal algorithm to solve the first problem. Next, we establish a property of symmetry, which helps us to solve the second problem based on the solution of the first one.

Słowa kluczowe

EN

single processor scheduling problem; scheduling; minimisation; mathematical model; symmetry property; interval assignment

• Wydawca: Oficyna Wydawnicza Politechniki Wrocławskiej
• Czasopismo: Systems Science
• Rocznik: 2004
• Tom: Vol. 30, no 2
• Strony: 97--107
• Opis fizyczny: Bibliogr. 11 poz., rys.

Twórcy

autor

Janiak A.

• Institute of Engineering Cybernetics, Wrocław University of Technology, Janiszewskiego 11/17, 50-372, Poland

autor

Marek M.

• Institute of Engineering Cybernetics, Wrocław University of Technology, Janiszewskiego 11/17, 50-372, Poland

Bibliografia

• [1] Cheng T. C. E., Gupta M. C., Survey of scheduling research involving due date determination decision, European Journal of Operational Research, Vol. 38, 1989, 156-166.
• [2] Chengbin C., Gordon V., Proth J.-M., A survey of the state-of-the-art of common due date assignment and scheduling research, European Journal of Operational Research, Vol. 139, 2002, 1-25.
• [3] Chengbin C., Gordon V., Proth J.-M., Due date assignment and scheduling: SLK, TWK and other due date assignment models. Production Planning & Control, Vol. 13, No. 2, 2002, 117-132.
• [4] Graham R. L., Lawler E. L., Lenstra J. K., Rinnooy Kan A. H. G., Optimization and approximation in deterministic sequencing and scheduling: a survey, Ann. Discrete Math., Vol. 5, 1979, 287-326.
• [5] Hardy G. H., Lhtlewood J. E., Polya G., Inequalities, Cambridge University Press, New York, 1934.
• [6] Janiak A., Marek M., Single machine scheduling problem with optimal due interval assignment, Lecture Notes of Silesia University of Technology, Automation 129, Gliwice 2000, 145-155 (in Polish).
• [7] Janiak A., Marek M., Multi-machine scheduling problem with optimal due interval assignment subject to generalized sum type criterion. Operations Research Proceedings 2001, Springer-Verlag 2002, 207-212.
• [8] Kramer F.-J., Lee C.-Y., Due window scheduling for parallel machine. Mathematical and Computer Modeling 20, 1994, 69-89.
• [9] Liman S. D., Panwalkar S. S., Thongmee S., Determination of common due window location in a single machine scheduling problem, European Journal of Operational Research 93, 1996, 68-74.
• [10] Liman S. D., Panwalkar S. S., Thongmee S., Common due window size and location determination in a single machine scheduling problem. Journal of the Operational Research Society 49, 1998, 1007-1010.
• [11] Panwalkar S. S., Smith M. L., Seidmann A., Common due date assignment to minimize total penalty for the one machine scheduling problem. Operations Research 30, 1982, 391-399.