Scheduling and due-date assignment problems with job rejection

• Autorzy: Mosheiov G. , Sarig A.
• Języki publikacji: EN

Abstrakty

EN

Scheduling with rejection reflects a very common scenario, where the scheduler may decide not to process a job if it is not profitable. We study the option of rejection in several popular and well-known scheduling and due-date assignment problems. A number of settings are considered: due-date and due-window assignment problems with job-independent costs, a due-date assignment problem with job-dependent weights and unit jobs, minimum total weighted earliness and tardiness cost with job-dependent and symmetric weights (known as TWET), and several classical scheduling problems (minimum makespan, flow-time, earliness-tardiness) with position-dependent processing times. All problems (excluding TWET) are shown to have a polynomial time solution. For the (NP-hard) TWET, a pseudo-polynomial time dynamic programming algorithm is introduced and tested numerically.

Słowa kluczowe

EN

scheduling; due-date assignment; earliness/tardiness; dynamic programming

PL

planowanie; terminowość zadania; wcześniej/później; programowanie dynamiczne

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2009
• Tom: Vol. 34, No. 3
• Strony: 193--208
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Mosheiov G.

autor

Sarig A.

• School of Business Administration and Department of Statistics, The Hebrew University, Jerusalem, Israel

Bibliografia

• [1] Bartal Y., Leonardi S., Marchetti Spaccamela A., Sgall J., Stougie L., Multiprocessor scheduling with rejection. SIAM Journal of Discrete Mathematical, 13, 2000, 64-78.
• [2] Cheng T.C.E., Ding Q., Lin B.M.T., A concise survey of scheduling with time-dependent processing times. European Journal of Operational Research, 152, 2004, 1-13.
• [3] Engels D.W., Karger D.R., Kolliopoulos S.G., Sengupta S., Uma R.N., Wein J., Techniques for scheduling with rejection. Proceeding of the 6th European Symposium on Algorithms (ESA' 98), Springer LNCS 1461, 1998, 490-501.
• [4] Gordon V., Proth J.M., Chu C., A survey of the state of the art of common due date assignment and scheduling research. European Journal of Operational Research, 139, 2002, 1-25.
• [5] Hall N.G., Posner M.E., Earliness-tardiness scheduling problems. I: Weighted deviation of completion times about a common due-date. Operational Research, 39, 1991,836-846.
• [6] Hoogeveen H., Skutella M., Woeginger G.J., Preemptive scheduling with rejection. Mathematical Programming, 94, 2003, 361-374.
• [7] 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.
• [8] Mosheiov G., Yovel U., Minimizing weighted earliness-tardiness and due-date cost with unit processing-time jobs. European Journal of Operational Research, 172, 2006, 528-544.
• [9] Panwalkar S.S., Smith M.S., Seidmann A., Common due-date assignment to minimize total penalty for the one machine scheduling problem. Operations Research, 30, 1982, 391-399.
• [10] Sengupta S., Algorithms and approximation schemes for minimum lateness/tardiness scheduling with rejection. Algorithm and data structures, Springer LNCS 2748, 2003, 79-90.