Slack due date assignment and scheduling stochastic jobs on a single machine

• Autorzy: Soroush H. M.
• Języki publikacji: EN

Abstrakty

EN

This paper solves the general case of the stochastic single machine scheduling problem where processing times are random variables and due dates are assigned using the slack method. Its objective is to identify the optimal sequence and optimal due dates which minimize the expected total weighted cost of assigning and missing due dates, with no restriction imposed on either cost. The paper presents an exact two-stage algorithm. The first stage (i) utilizes an adjacent precedence relation structure to determine an initial ordering of jobs, (ii) investigates the optimality of the initial job ordering, and (iii) when it cannot prove optimality. it tries to improve the initial ordering by moving jobs from their current positions to any other positions that ensure the precedence relations hold; thus, obtains an incumbent solution. The second stage, which uses the incumbent to show its optimality or search for the optimal solution, is a branch and bound. It utilizes the expected cost of the incumbent as an initial upper bound. It avoids investigating dominated branches by using the job precedence relations; thus, greatly reduces the size of the tree. Extensive computational results show that the incumbent solution obtained in the first stage of the algorithm provides a very tight upper bound cost which fathoms a significant number of non-dominated solutions in the second stage; thus, the proposed algorithm can solve large problems quickly on PC.

Słowa kluczowe

EN

sequencing; due-date assignment; single machine; stochastic

• Wydawca: Wydawnictwo Politechniki Poznańskiej
• Czasopismo: Foundations of Computing and Decision Sciences
• Rocznik: 2007
• Tom: Vol. 32, No. 2
• Strony: 153--181
• Opis fizyczny: Bibliogr. 20 poz.

Twórcy

autor

Soroush H. M.

• Department of Statistic and Operations Research, Kuwait University, PO Box 5969, Safat 13060, Kuwait,

Bibliografia

• [1] Adler, I., Alon, N., Ross. S.M., On the maximum number of Hamiltonian paths in tournaments, Random Structures and Algorithms, 18, 2001, 291-296.
• [2] Alidaee, B., Optimal assignment of slack due-date and sequencing in a single machine shop, Applied Mathematics Letters, 4, 1991, 9-11.
• [3] Alon, N, The maximum number of Hamiltonian paths in tournaments, Combinatorics, 10, 1990,319-324.
• [4] Baker, K., Scudder, G., Sequencing with earliness and tardiness penalties: a review, Operations Research, 38, 1990, 22-36.
• [5] Cheng, T.C.E., Optimal due-date determination and sequencing of n jobs on a single machine, Journal of the Operational Research Society, 35, 1984, 433-437.
• [6] Cheng, T.C.E., Optimal due-date assignment for a single machine sequencing problem with random processing times, International Journal of Systems Science. 17, 1986, 1039-1144.
• [7] Cheng, T.C.E., Optimal assignment of slack due-dates and sequencing of jobs with random processing times on a single machine, European Journal of Operational Research, 51, 1991, 348-353.
• [8] Cheng, T.C.E., Gupta, M.C., Survey of scheduling research involving due-date determination decisions, European Journal of Operational Research. 38, 1989, 156-166.
• [9] Cheng, T.C.E., Chen, Z.L., Shakhlevich, N.V., Common due date assignment and scheduling with ready times, Computers and Operations Research, 29, 2002, 1957-1967.
• [10] Cheng, T. C. E., Ng, C. T., Yuan, J. J., Liu, Z. H., Single machine scheduling to minimize total weighted tardiness, European Journal of Operational Research, 165, 2005,423-443.
• [11] Daniel, C.T.N., Cheng, T.C.E., Kovalyov, M.Y, Larn, S.S., Single machine scheduling with a variable common due date and resource-dependent processing times, Computers and Operations Research, 30, 2003, 1173 -1185.
• [12] Gordon, V.S.. Strusevich, V.A., Earliness penalties on a single machine subject to precedence constraints: SLK due date assignment, Computers and Operations Research, 26, 1999, 157-177.
• [13] Gupta, Y. P., Bector, C. R., Gupta, M. C, Optimal schedule on a single machine using various due date determination methods, Computers in Industry, 15, 1990, 245-254.
• [14] Kahlbacher, H.G., Scheduling with monotonous earliness and tardiness penalties, European Journal of Operational Research, 64, 1993, 258-277.
• [15] Karacapilidis, N. 1., Pappis, C. P., Optimal due date determination and sequencing of n jobs on a single machine using the SLK method, Computers in Industry, 21. 1993, 335-339.
• [16] Karacapilidis, N.I., Pappis, C.P., Form similarities of the CON and SLK due date determination methods, Journal of the Operational Research Society, 46, 1995, 762 - 770.
• [17] Oguz, C., Dincer, C., Single machine earliness-tardiness scheduling problems using the equal slack rule. Journal of the Operational Research Society, 45, 1994, 589-594.
• [18] Soroush, H.M., Sequencing and due date determination in the stochastic single machine problem with earliness and tardiness costs, European Journal of Operational Research, 113, 1999, 450-468.
• [19] Taylor, S.G., Bolander, S.F., Process flow scheduling principles, Production and Inventory Management Journal, 32, 1993, 67-7 3.
• [20] Xiangtong, Q., Tu, F.S., Scheduling a single machine to minimize earliness penalties subject to SLK due date determination, European Journal of Operational Research, 105,1998,502-508.