January 6, 2013 at 2:24 pm
I have a theoretical question that sprang from, of all things, looking at my public library holds this morning. 😎 I'd classify myself as a Beginner-bordering-on-Intermediate-level TSQL programmer, so I'm constantly looking for theoretical challenges. 🙂
Anyway, I wanted to post this in case there was anything in the scenario and logic below that is overcomplicated? Or missing? Or wrong? Please let me know. 🙂
A little background info:
My library system is this great system with several branches. Books can be checked out for up to a month.
In this system, you can place holds and then suspend them (so that you move up in the queue, but don't receive your holds until you activate them)... when an item becomes available, it always goes to the first active hold in the queue. (It's a wonderful system... frankly, I don't know how anybody lives without it!)
Anyway, how holds are managed (apparently... I don't work at the library and only have a patron's view of how it works), is that when a person returns an item to one of the branches, it gets checked in, and then the system checks to see if there are any active holds. If there are, it prints a slip with patron name and pick-up branch of the first active hold. The library clerk then sticks that slip in the book, and if the pick-up branch is not the same as the current branch, the book then goes into a crate marked for the destination branch. The book gets marked in the catalog as, "in transit from such-and-such branch to such-and-such branch". This crate then gets picked up by somebody and taken to the destination branch, and the library clerk there checks in all the books on the crate and puts them on the hold shelf (at which point, the book is now marked as "on hold"). This "in transit" time can take anywhere from 1 to 5 days.
Once a book is marked as "on hold," the patron has up to a week to pick it up, before the hold expires and goes to the next active hold.
If the pick-up branch for the next active hold is the same as the current branch, obviously, there is no "in transit" time. The item gets checked in, the slip gets printed, and the book goes right on the hold shelf, ready to be picked up by the patron who placed the hold.
This morning, I was looking at a very popular book. This book is so popular, in fact, that the library system has 66 copies of it, and there are currently about 330 holds, about 310 of which are currently active. Two of the copies were marked as "in transit," as of this morning (the rest are all either "on hold" or "checked out"). One was marked, "In transit from [Branch A] to [Branch B] since 1/5/2013." The other was marked as, "In transit from [Branch C] to [Branch A] since 1/5/2013." Note that Branch A is the origin in one and the destination in another. Which basically means that a book got checked in yesterday there and got put into a crate for another branch, and later on the same day, another copy of the same book got checked in at another branch and got put into a crate bound for... the first branch.
... and I had a thought. 😀 With 66 copies of this book, Branch B can wait another... 2 days, maybe... for their hold if it means saving Branch A a bunch of time and essentially getting the book into the hands of one of its patrons a lot sooner. Getting onto the hold shelf sooner means getting checked out sooner, which means an earlier due date, which means getting returned sooner, which means getting sent to the next patron on the list sooner. Multiply that times 330 holds, and this could really, really speed up getting that book to everybody who's waiting for it.
But how to do it?
What I thought was: take the number of copies, and divide by 4 (4 weeks being the amount of time a book may be checked out), and round down to the nearest integer (unless that number is 0, in which case, use 1). This would provide a reasonable number of holds that may be skipped in favor of being able to put the book straight onto the hold shelf and not in transit (based on the number of copies, and therefore an approximation of how long a person should have to wait for their hold - on average, at most, this will result in a person at the top of the queue maybe having to wait another week). So the system should check that many of the top holds in the queue, looking for any that are in the current branch. But there should also be a limit to how many times a given hold at or near the top of the queue may be skipped... and I figured that "number of copies/4" actually works well for that limit as well. But if a hold is skipped, then anything ahead of it in the queue needs to be marked as having been skipped somehow.
So here's what I thought it could do:
Let's say the book isn't terribly popular, and only has 1 or 2 copies in the system and maybe 4 holds. In this case, the system should check the first (1) active hold to see if it's in the current branch, and if not, then send it to the first active hold (effectively, always sending to the first active hold, which is precisely what a book with only 1 or 2 available copies should do).
Now let's use the previous example, of the book with 66 copies in the system and about 310 active holds. In this case, the system should do the following after a book is checked in at branch A:
- If the number of active holds is 0, send the book back to its home branch to be put on the shelf. Otherwise, proceed with the following:
- Check the first 16 (66/4, rounded down to the nearest integer) active holds in the system (or the number of total active holds, whichever is less), looking for any holds marked for pick-up at Branch A.
-- If none are found in the first 16, go ahead and send to the first active hold in the queue.
-- If, OTOH, one is found, then:
--- Check all of the higher items in the queue for any holds that have already been skipped 16 or more times.
---- If there are any, then that's too many times to be skipped. Send the book to the first active hold in the queue.
---- If there aren't any, then:
----- Place the hold that's at the current branch.
----- For all holds that were higher up in the queue, increment the number of times they were skipped by one.
So... how could this be done?
Here's my pseudocode with pseudo-logic, written with TSQL 2008 in mind. It assumes the book has just been checked in (and therefore doesn't worry about that). Hopefully my imaginary table structure is intuitive to everybody. Again, I'd appreciate you reading my long convoluted post and helping me learn, by letting me know if there's anything in the logic, code, or handling that's overcomplicated, expensive, or wrong, or just could be done better in another way. 🙂
Please ignore minor errors and kindly correct major ones; this is pseudocode after all! 😀
(Oh, I should probably mention that in our system, you typically place holds for books. You don't place holds for specific copies. If there are multiple copies of the same book and you are at the top of the queue, you just get the first available copy. There is a way to place a hold for a specific copy of a book, but I'm just going to ignore that for the purpose of this exercise, especially since, in all the times that I've placed holds, I've never had reason to place a hold for a specific copy. Also, I'm assuming that queue position is based solely on the time and date that the hold was placed in the system, because that's how the system has always behaved.)
CREATE PROCEDURE udp_GetNextActiveHoldForBook
(
@BookID int,
@CurrentBranchID int,
@BookCopyID int,
@DestinationBranchID int=0 OUTPUT,
@DestinationPersonID int=0 OUTPUT
)
AS
BEGIN
SET NOCOUNT ON;
DECLARE @CountActiveHolds int, @CountCopiesDiv4 int
DECLARE @CheckLocalHoldDatePlaced datetime, @CheckLocalHoldID int=0
DECLARE @SendToHoldID int=0
-- Check to see if there are any active holds. If not, send to the book copy's home branch.
SELECT @CountActiveHolds = Count(*) FROM BookHolds WHERE BookID = @BookID AND IsActive = 1 AND IsWaiting = 1
IF @CountActiveHolds = 0
BEGIN
SELECT @DestinationBranchID = HomeBranchID FROM BookCopies WHERE BookCopyID = @BookCopyID
RETURN
END
-- get the number of copies of the book, divide by 4. This number will be:
-- - The number of active holds at the top of the queue to check for another hold at the current branch
-- - The maximum number of times a hold at the top of the queue may be skipped over.
-- If 0, then 1 (must always be at least one)
SELECT @CountCopiesDiv4 = CASE WHEN Floor(Count(*)/4) = 0 THEN 1 ELSE Floor(Count(*)/4) FROM BookCopies WHERE BookID = @BookID;
-- check the top holds in the system (however many are in @CountCopiesDiv4) for any in the current branch. Grab the first one in the queue.
SELECT TOP (1) @CheckLocalHoldID = HoldID, @CheckLocalHoldDatePlaced = DateHoldPlaced FROM
(SELECT ROW_NUMBER() OVER(ORDER BY DateHoldPlaced) AS RowNum, HoldID, BranchID, DateHoldPlaced
FROM BookHolds
WHERE BookID = @BookID AND IsActive = 1 AND IsWaiting = 1)
WHERE RowNum <= @CountCopiesDiv4 AND BranchID = @CurrentBranchID
ORDER BY RowNum;
IF @CheckLocalHoldID = 0 -- no local holds found near the top of the queue. Grab the first active hold in the queue.
BEGIN
SELECT TOP (1) @SendToHoldID = HoldID, @DestinationBranchID = BranchID, @DestinationPersonID = PersonID
FROM BookHolds
WHERE BookID = @BookID AND IsActive = 1 AND IsWaiting=1
ORDER BY DateHoldPlaced;
UPDATE BookHolds SET IsWaiting = 0 WHERE HoldID = @SendToHoldID;
RETURN;
END
ELSE -- A local hold was found. Check all holds higher in the queue and make sure none have been skipped too many times.
BEGIN
DECLARE @CheckTooManySkips int=0
SELECT @CheckTooManySkips = Count(*)
FROM BookHolds
WHERE BookID = @BookID AND IsActive = 1 AND IsWaiting = 1 AND DateHoldPlaced < @CheckLocalHoldDatePlaced AND SkipCount >= @CountCopiesDiv4
IF @CheckTooManySkips > 0 -- Too many skips in at least one higher item in the queue. Send to first hold in the list.
BEGIN
SELECT TOP (1) @SendToHoldID = HoldID, @DestinationBranchID = BranchID, @DestinationPersonID = PersonID
FROM BookHolds
WHERE BookID = @BookID AND IsActive = 1 AND IsWaiting=1
ORDER BY DateHoldPlaced;
UPDATE BookHolds SET IsWaiting = 0 WHERE HoldID = @SendToHoldID;
RETURN;
END
ELSE -- Grab the first LOCAL queue item. Update the skip counts for everything higher up in the queue.
SELECT @SendToHoldID = HoldID, @DestinationBranchID = BranchID, @DestinationPersonID = PersonID
FROM BookHolds
WHERE HoldID = @CheckLocalHoldID;
UPDATE BookHolds SET IsWaiting = 0 WHERE HoldID = @SendToHoldID;
UPDATE BookHolds SET SkipCount = (SkipCount + 1)
WHERE BookID = @BookID AND IsActive = 1 AND IsWaiting = 1 AND DateHoldPlaced < @CheckLocalHoldDatePlaced
END
END
END
Is this right? Is there a better way? Many thanks for input! :w00t:
January 7, 2013 at 11:57 am
I didn't review the code, because I think the problem may need some redefinition. There seem to be three considerations: (1) efficiency (where efficiency = book in the hands of a patron, rather than on a shelf or in transit), (2) fairness/good service to patrons (where fairness/good service = serving hold requests in the order received without anyone waiting too long for the book), and (3) manageability - minimizing the administrative burden on the library staff and systems (you didn't expressly mention this one, but it should be implicit, since a system that achieves the first two goals still fails if it is untenable in practice). Finding the balance can be challenging.
IMHO, your proposal does not accomplish the fairness objective well enough. If I understand the logic correctly, a patron waiting to read one of 66 copies of a book could theoretically see 16 people who requested a hold AFTER him get a copy of the book BEFORE him. I think most library patrons would grumble if they came out on the short end of that stick, and I would not want to try to explain the system you laid out to an angry caller who found out that three or four friends who requested the book after he did have their copies while he's still waiting.
I think I might achieve a better balance of the three considerations with something like a "hold clearinghouse" process. As part of the check-in process, titles with active holds are marked as "on hold - pending transfer" and set aside. At a set time each day, the system processes all holds. Each copy is matched to a hold request, with hold requests fulfilled in the order received and copies at a given branch assigned to hold requests at that branch when possible (in which case the library staff notify the appropriate patrons) and transit slips printed for copies that must be transferred to another branch to satisfy a hold request (in which case library staff route the book appropriately).
This process would run somewhere around halfway to two-thirds of the way through the business day. Librarians could notify patrons with "same branch" hold requests well before closing time, possibly allowing them enough time to collect their copies that day. Books that must be transferred to serve hold requests could possibly be collected from the sending branch the same day (depending on pick-up and delivery schedules, of course), hastening their arrival at the recipient branch.
On reflection, this doesn't sound much different than the system in place, as you described it. However, it does avoid the most asinine scenarios. For example, the library owns two copies of a book, and patron A requests a hold on it at branch 1 on Feb. 1 and patron B requests a hold at branch 2 on Feb. 2. One day, a copy is returned to branch 2 at 9 a.m. The system assigns it to patron A's hold at branch 1 and the librarians route it accordingly. At 10 a.m., a copy is returned to branch 1, and the system assigns it to the next active hold, patron B's, and the librarians route it accordingly. Later that day, one copy is shipped from branch 2 to branch 1 while the other copy is shipped from branch 1 to branch 2.
Here is my assessment of my system with respect to the three considerations it must serve.
Efficiency: 6 out of 10. The number of unnecessary transfers will be lower, but books are effectively out of circulation until the clearinghouse process runs; books may be transferred more frequently
Fairness/good service: 8 out of 10. Hold requests are served in the order of receipt, but inefficiencies may still result in longer waits for everyone.
Manageability: 8 out of 10. Library staff can process the hold list just once a day, but there must be storage space for the "on hold - pending transfer" shelf and each book must be handled twice (once when checked in and shelved on the "on hold - pending transfer" shelf and once when library staff processes the hold list.
Thanks for the interesting problem!
Jason Wolfkill
Viewing 2 posts - 1 through 1 (of 1 total)
You must be logged in to reply to this topic. Login to reply