US007263495B2
`
`US 7,263,495 B2
`(10) Patent No.:
`a2) United States Patent
`Rodriguez
`(45) Date of Patent:
`Aug. 28, 2007
`
`
`(54) ORDER SCHEDULING SYSTEM AND
`METHODOLOGY
`
`(75)
`
`Inventor:
`
`John Rodriguez, Capitola, CA (US)
`
`(73) Assignee: LightSurf Technologies, Inc., Santa
`Cruz, CA (US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 860 days.
`
`(*) Notice:
`
`(21) Appl. No.: 09/865,916
`(22)
`Filed:
`May 24, 2001
`.
`oo
`Prior Publication Data
`US 2003/0018502 Al
`Jan. 23, 2003
`
`(65)
`
`10/2003 Friesen .....cscesssseeeeesees 707/102
`6,636,863 Bl
`.......0.... 705/26
`2001/0042023 A1* 11/2001 Andersonet al.
`
`2/2002 Kamath et al... .. 705/26
`2002/0026373 A1l*
`8/2002 Clendinninget al.
`....... TOT/101
`2002/0107861 Al*
`FOREIGN PATENT DOCUMENTS
`
`JP
`
`10-40255 A *
`2/1998
`OTHER PUBLICATIONS
`ATIS, hash function definition, T1.523-2001, Copyright © Alliance
`for Telecommunications Industry Solutions, 2001 (1 page).*
`Definition of “Bit
`array”
`from http://en.wikipedia.org/wiki/
`Bit_array, retrieved from the Internet on Aug. 26, 2006.*
`* cited by examiner
`Primary Examiner—Susanna M.Diaz
`(74) Attorney, Agent, or Firm—Blakely, Sokoloff, Taylor &
`Zafman, LLP; Judith A. Szepesi
`
`(51)
`
`Int. Cl.
`GO6F 9/46
`705/8
`(52) US. Cl
`(58) Field of Classification Search .......0..0.00.... 705/7,
`705/8
`See application file for complete search history.
`
`(2006.01)
`
`(56)
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`5,319,542 A
`5,402,336 A *
`5,715,314 A
`5,745,681 A
`5,819,285 A
`oooeat ‘
`029,
`6,317,722 BL
`
`6,594,641 BI*
`6,628,307 Bl
`6,629,079 Bl
`
`... 705/27
`6/1994 King et al...
`
`we 705/8
`3/1995 Spiegelhoff etal.
`
`.. 705/78
`2/1998 Payne et al.
`........
`4/1998 Levineet al. 0.0... 709/200
`
`10/1998 Damicoet al.
`.........., 707/104.1
`5)0G aue ansrteeeeeteeeceneneessen
`ezos et
`al.
`.....
`te
`....
`705/14
`11/2001 Jacobi etal.
`
`
`7/2003 Southam ..............08 705/26
`9/2003) Fair wo... cc ceeeceeeeeeeceeeeeee 345/763
`9/2003 Spiegel et al. we 705/26
`
`(57)
`
`ABSTRACT
`,
`i
`.
`An order scheduling system providing a method for distrib-
`uting product orders to multiple fulfillers is described. This
`method, which solves the common business problem of
`scheduling order shipments, is optimal because it minimizes
`the number of orders across fulfillers,
`thus minimizing
`shipping costs. It is also fair because orders are distributed
`equally across fulfillers if that fulfiller has the product
`available. To schedule orders, a data structure is defined
`whose rows are represented by a hash table of Fulfillers
`(HF), where each column is a hash table of Products (HP)
`and where each index of HPisitself a bit vector (VP,). This
`gives a three-dimensional data structure. The method oper-
`ates by performing bitwise ANDing (&) operationsofthe bit
`vectors,
`to generate an Order bit vector representing the
`sos
`.
`:
`foraparticularreceived0‘rem configuration/constraints)
`
`.
`
`16 Claims, 14 Drawing Sheets
`
`
`
`800) ROUTINELY UPDATE FULFILLER BIT VECTORS
`
`
`
`ato
`
`“|
`
`6207)
`
`330
`
`~~)
`
`640
`
`650
`
`~~)
`
`8601
`
`8707
`
`
`
`DETERMINE SELECTION CRITERIA FOR
`FULFILLER PRECEDENCE
`
`ORDER ENGINE GETS AN XML ORDER
`FULFILLMENT REQUEST
`
`|
`
`CREATE ORDER AND ORDER ITEM BIT
`VECTORS
`
`DETERMINE IF SINGLE FULFILLER CAN FILL
`THIS ORDER
`
`SPLIT ORDER PLACES ORDERITEMS WITH
`SORTED FULFILLERS
`
`DISPATCH SUB-ORDERS FROM maMensionnd]
`FULFILLMENT DATA
`
`OPTIONALLY MODIFY FULFILLER SORT-ORDER |
`BEFORE NEXT FULFILLMENT ORDER
`
`PROVI-1019 - Page 1
`
`PROVI-1019 - Page 1
`
`

`

`U.S. Patent
`
`Aug.28, 2007
`
`Sheet 1 of 14
`
`US 7,263,495 B2
`
`60
`
`50
`
`40
`
`30
`
`PORTABLE
`
`10
`
`20
`
`DISPLAY UNITS
`
`FEASIBLE
`REGION
`
`DESKPRO
`
`1
`FIG.
`(PRIOR ART)
`
`PROVI-1019 - Page 2
`
`PROVI-1019 - Page 2
`
`

`

`U.S. Patent
`
`Aug. 28, 2007
`
`Sheet 2 of 14
`
`US 7,263,495 B2
`
`
`
`GlaONISSSIONdIVHLNSAD
`
`00€
`
`£0¢c0e
`
`LOGole
`
`JISVAOWSY(s)LINNSNOMGaN
`
`
`seyows(Nd9)FOVAMSLNI
`
`
`
`
`
`gaxis
`
`SYaAINd
`
`
`
`SOAOVHOLSsONiNODporno>
`
`SNOILVOIIddV6
`
`
`
`S31ldvivdo1z
`
`9LZ
`
`ONILNIOdBVORASYOAdIA
`
`
`
`AOIAadYaLdvav
`
`CuVvOdA
`
`(LYVYOIxd)
`
`80z90ZANOWAWN
`
`OZGIA
`
`
`
`YaLNIYdAV1dSIG
`
`2020%Goz
`
`PROVI-1019 - Page 3
`
`LZ
`
`PROVI-1019 - Page 3
`
`
`
`

`

`U.S. Patent
`
`Aug. 28, 2007
`
`Sheet 3 of 14
`
`US 7,263,495 B2
`
`301a
`
`APPLICATION
`PROGRAM 1
`
`301d
`
`
`(e.g., WINDOWS 9X/NT/2000/XP, SOLARIS, UNIX, LINUX, MAC OS, OR LIKE) 310
`
`
`
`
`OPERATING SYSTEM
`
`(MICROCODE)
`
`DISPLAY MONITOR
`NETWORK INTERFACE
`COMM PORT
`KEYBOARD
`MODEM
`MOUSE
`DISKS
`PRINTER
`
`FIG. 3
`
`PROVI-1019 - Page 4
`
`PROVI-1019 - Page 4
`
`

`

`U.S. Patent
`
`Aug. 28, 2007
`
`Sheet 4 of 14
`
`US 7,263,495 B2
`
`Hashtable
`
`HP
`
`Hashtable
`
`Vector
`
`HF
`
`FIG. 4A
`
`PROVI-1019 - Page 5
`
`PROVI-1019 - Page 5
`
`

`

`U.S. Patent
`
`Aug. 28, 2007
`
`Sheet 5 of 14
`
`US 7,263,495 B2
`
`
`
`
`
`FIG. 4C
`
`PROVI-1019 - Page 6
`
`PROVI-1019 - Page 6
`
`

`

`U.S. Patent
`
`Aug. 28, 2007
`
`Sheet 6 of 14
`
`US 7,263,495 B2
`
`500
`
`550
`
`<—_——_Yr
`
`cDS|
`DATABASE
`
`SERVER
`
`ORDER
`PARSER
`
`ORDER
`CNGINE
`
`PROCESSING
`
`XML REQUESTS
`
`(e.9., VIA HTTP, FTP)
`
`ORDER
`SCHEDULER
`
`ORDER
`
`FIG. 5A
`
`PROVI-1019 - Page 7
`
`PROVI-1019 - Page 7
`
`

`

`U.S. Patent
`
`Aug. 28, 2007
`
`Sheet 7 of 14
`
`US 7,263,495 B2
`
`530
`
`CONSTRAINTS
`
`ORDER
`SCHEDULER
`
`SCHEDULER
`(CORE)
`
`DB
`INTERFACE
`
`CONFIGURATION
`&
`
`FIG. 5B
`
`PROVI-1019 - Page 8
`
`PROVI-1019 - Page 8
`
`

`

`U.S. Patent
`
`Aug. 28, 2007
`
`Sheet 8 of 14
`
`US 7,263,495 B2
`
`a,
`™_
`——
`
`O. ©L
`
`L.
`
`PROVI-1019 - Page 9
`
`£OW
`
`w
`OG
`LL
`
`Q
`O
`Lo
`O
`LL
`
`&
`O
`LO
`oO
`LL
`
`PROVI-1019 - Page 9
`
`

`

`U.S. Patent
`
`Aug. 28, 2007
`
`Sheet 9 of 14
`
`US 7,263,495 B2
`
`g
`
`(Wd)GIYaqGHO
`(44)GMasn
`
`
`
`1Y¥30uO
`
`
`
`
`
`(44)aauvo_LigaY4o
`
`ZOUVHOWLOL
`
`(Hd)QILNAWAVd
`
`LNAWAVd
`
`0SNLVLSYAQHO
`
`NOLdidoSa0BOO
`
`3009ONITHEANV
`w000°ONITHIg
`
`OOALWONOILVHIdX’
`
`(Y)D4OLALIBOIdONIiddiHS
`
`(posaivd_Gaivayd
`
`
`3000LIdSYoNVA
`
`3009LInsadSAV
`
`
`
`3000LIGaHD
`
`(os‘O14ONS
`
`
`
`IWaLlryaquoYaTdsins
`
`
`
`(4d)QFYaGHOYaTNIINAQld)GFYaqHO
`
`
`
`
`
`SNLWiS"H30NOYSTHSINS
`
`(M4)GIYaTI-ISINSB
`
`
`
`
`
`alYysquNOY3STHSINSWNYSLXe
`
`
`
`3ivd_dalsiqow
`
`
`
`Alvddalsiaow
`
`BlvdLida
`
`
`
`18007ONIddIHS
`
`XL
`
`
`
`(¥)9S‘Did©.
`
`Lb
`
`
`
`(id)dMyaquoYaTHs1N4
`
`ivaG3ala1dwod
`
`
`
`ALVdGaLvayo
`
`
`
`3LvdG3lsIGOW
`
`
`
`AlvaLNAS
`
`SNLVLS
`
`
`
`
`
`(Hd)GIWSL!YaqHYOY3aTHAINA
`
`
`
`
`
`LWallysaquoYaT141N4
`
`
`
`ssv1dYATHAING
`
`
`
`(z)9s‘S14
`
`4)alssauaavONIddIHs
`
`(M4)CILNSWAVd
`
`
`3q09NOWVZINOHLNYMUNYA
`AODNOLLVZINOHLAY
`
`ssauydayvONITHA
`
`
`
`ONILVYLISD
`
`
`
`alvdd3alvauo
`
`
`
`ALVGG3IsIGOW
`
`
`
`AdALauvo
`
`3WYNaud
`
`AdALNOILVZINOH.LNY
`
`Q4a9YvHOLNNOWV
`
`(4d)GrauvoLidayo
`
`
`
`(44)aYasn
`
`
`
`iLayvoLidsyo
`
`(id)alssayaayOnna
`
`
`
`issaydavONITHB
`
`
`
`LLa3yulsssayqav
`
`€1A5uLSssayaav@1a3uLS
`
`SSayaov
`
`
`
`ALIO¢LASSssaycav
`
`(4)aY¥asn
`SWYNSuid
`
`SWYN'1sv1
`
`ALVOGalvayo
`
`
`
`aLVdG3IsIQOW
`
`
`
`Aq0oW.Lsod
`
`SNOHdAWOH
`
`
`
`3NOHdXYOM
`
`waq09039
`
`ALNNOS
`
`NOID3Y
`
`SLVLS
`
`AYLNNOD
`
`(Ma)OFWAL!YaauOB
`
`(4)GIYSaTUIINS
`
`
`MASWNANWAYALNIYaqNO
`
`
`
`AYOLOAUICSNLWLS
`
`(9)
`
`
`
`(e)0S“S14OL
`
`PROVI-1019 - Page 10
`
`sssydavYOAWVNLSOH
`
`_SWYNYaSsN
`
`
`
`AYOLOZYICdowd
`
`CYyOmMssWd
`
`
`
`aLvddaLv34o
`
`3.LV0_GalJIGOW
`
`
`
`SNOHdLOVLNOO
`
`
`
`IWWaLOVLNOO
`
`A009W1SOd_LOVLINOO
`
`O14)Old)OFYATHIINA
`
`_ONDINVY
`
`(44)Old)aIMLONdOwd
`
`Iyatians
`
`
`(id)GMYaTHNAINS
`
`SWVNLOVLINOO
`
`J¥aTisingLondeud
`
`PROVI-1019 - Page 10
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug.28, 2007
`
`Sheet 10 of 14
`
`US 7,263,495 B2
`
`‘OldOL
`
`(pos
`
`
`
`LSinaWALIYaauo
`
`_ 3WVN
`
`(44)Old)OIWALIYaaHOF
`
`(M4)Old)GVSALAMLLY
`
` Old)GISALNGINLLYJSLngiuiiv”Londoud
`ANTWA_SLNSISLLY
`3WVNALNEINLLY
`
`(a4)arLondodd
`
`INNOOSaysWILINI
`
`
`
`alvddalvayd
`
`alvd_dalsiqow
`
`NOlLdINOS3Ad
`
`AYXOOSALVD
`
`a9ldd
`
`(4d)GILonaoudJi1ondoud
`
`
`LYVDONIiddOHS_(44)aI-Yasn(Md)QMWALI
`
`
`WALILYVOONIddOHS
`
`
`
`ALOG3aLVayd
`
`
`
`ONIddlHs|YASWNNONINOVYL|(Ad)GIGOHLEW
`
`
`
`
`
`3LVdGaddIHS
`
`
`
`
`
`(Md)GI-OANTNOlddlHS
`
`
`
` (p)o¢©)‘O14OL
`
`
`
`LOSNIONIddIHs
`
`_30rd
`
`
`
`ALvidWalWYN
`
`
`
`3WVNGOHLAW
`
`
`
`3LvdG3SLVayo
`
`
`
`31vdGalsiqdow
`
`1809daxi4
`
`_ALIdOIdd
`
`3LVC_GalsIGOW
`
`
`(3d)GI-GOHLAWONiddIH$
`L-GOHL3WONIddIHs
`
`
`3WVNANWdINOD
`
`(44)GFGOHLAW_ONIddIHS
`
`
`(4d)GFLSO9ONIddIHS
`(414)dI1ondoud
`
`
`Nt
`
`
`
`LLSO0OSNIddIHS
`
`ALILLNWNDXVI
`
`ALLLNYNO”NIN
`
`301d
`
`
`
`(4d)aI”Londodd
`
`
`
`AdAL_SAONAYaAaY
`
`arSONau34344
`
`ALLLNYNOW3LI
`
`
`
`BLVdG3LVayd9
`
`aLVd_dalsiIGow
`
`
`
`
`
`LLNNODLONdoOYd3344
`
`
`
`(44)GFLONGOUd(yd)aruasn
`
`ONINIVAISY
`
`(€)9S“SIs
`
`PROVI-1019 - Page 11
`
`WOYd
`
`
`
`(2)0¢‘Sl4
`
`PROVI-1019 - Page 11
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Aug. 28, 2007
`
`Sheet 11 of 14
`
`US 7,263,495 B2
`
`SHIPPING_ADDRESS_T
`
`
`
`
` FROM
`
`FIG. 5C(2)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SHIPPING_ADDRESS_ID (PK)
`USER_ID (Fk)
`FIRST_NAME
`
`LAST_NAME
`ADDRESS_STREET_1
`ADDRESS_STREET_2
`ADDRESS_STREET_3
`ADDRESS_STREET_4
`CITY
`COUNTY
`STATE
`REGION
`COUNTRY
`POSTAL CODE
`CREATED_DATE
`MODIFIED_DATE
`
`HOME_PHONE
`
`WORK_PHONE
`GEOCODE
`
`
`
`
`
`
`
` “ ORDER_ITEM_T
`FROM
`FIG. 5C(2)
`
` ORDER_ITEN_ID (PK)
`
`
`ITEM_STATUS
`DESCRIPTION
`PRODUCT_ID (FK)
`ORDER_ID (FK)
`
`SHIPPING_INFO_ID (Fk)
`
`SHIPPING_ADDRESS_ID (Fk)
`
`4 ITEM_PRICE
`
`
`
`FREE_ITEM_QUANTITY
`
`FROM
`
`ITEM_QUANTITY
`
`
`
`FIG. 5C(3)
`ITEM_TOTAL
`REFERENCE_ID
`
`
`REFERENCE_TYPE
`
`
`CREATED_DATE
`FROM
`MODIFIED_DATE
`
`
`FIG. 5c(3)
`(FY
`
`
`
`ORDER_ITEM_T_POST_INS_TRIG
`
`
`
`
`
`GEOCODE_STATE_REF_T
`
`
`
` STATE_CODE (PK) (FK)
`
`EXCEPTION_CODE
`GEOCODE
`DEFAULT_TAX_RATE
`CLOTHING_TAX_RATE
`
`
`
` STATE_REF_T
`
`
`
` oe
`
`STATE_CODE(PK)
`STATE_DESCRIPTION
`
`GEOCODE_EXQ
`STATE_CODE (Fk)
`
`CITY
`COUNTY
`
`GEOCODE
`DEFAULT_TAX_RATE
`CLOTHING_TAX_RATE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ORDERATEM_TAX_T
`
`
`ORDER_ITEM_ID (PK)(FK)
`FROM
`
`DISTRICT_TAX
`
`
`FIG. 5C(3)
`
`COUNTY_TAX
`STATE_TAX
`CITY_TAX
`
`TOTAL_TAX
`
`
`FIG. 5C(4)
`
`PROVI-1019 - Page 12
`
`PROVI-1019 - Page 12
`
`

`

`U.S. Patent
`
`Aug. 28, 2007
`
`Sheet 12 of 14
`
`US 7,263,495 B2
`
`BEGIN
`
`600
`
`ROUTINELY UPDATE FULFILLER BIT VECTORS
`
`610
`
`620
`
`630
`
`640
`
`650
`
`660
`
`670
`
`DETERMINE SELECTION CRITERIA FOR
`FULFILLER PRECEDENCE
`
`ORDER ENGINE GETS AN XML ORDER
`FULFILLMENT REQUEST
`
`CREATE ORDER AND ORDER ITEM BIT
`VECTORS
`
`DETERMINE IF SINGLE FULFILLER CAN FILL
`THIS ORDER
`
`SPLIT ORDER PLACES ORDER ITEMS WITH
`SORTED FULFILLERS
`
`DISPATCH SUB-ORDERS FROM N-DIMENSIONAL
`FULFILLMENT DATA
`
`OPTIONALLY MODIFY FULFILLER SORT-ORDER
`BEFORE NEXT FULFILLMENT ORDER
`
`FIG. 6
`
`PROVI-1019 - Page 13
`
`PROVI-1019 - Page 13
`
`

`

`U.S. Patent
`
`Aug. 28, 2007
`
`Sheet 13 of 14
`
`US 7,263,495 B2
`
`BEGIN
`
`700
`
`GET NUMBER OF PLACABLE PRODUCTS FOR
`EACH FULFILLER
`
`720
`
`SORT-ORDER THE VECTOR OF FULFILLER BIT
`VECTORS BY NUMBER OF PLACABLE PRODUCTS
`
`DETERMINE IF SINGLE FULFILLER CAN FILL THIS
`
`650
`
`SPLIT ORDER PLACES ORDER ITEMS WITH
`SORTED FULFILLERS
`
`DONE
`
`FIG. 7
`
`PROVI-1019 - Page 14
`
`PROVI-1019 - Page 14
`
`

`

`U.S. Patent
`
`Aug. 28, 2007
`
`Sheet 14 of 14
`
`US 7,263,495 B2
`
`BEGIN
`
`800
`
`GET VALUE FOR PROXIMITY BETWEEN EACH FULFILLER
`AND DELIVERY ADDRESS
`
`820
`
`SORT-ORDER THE VECTOR OF FULFILLER BIT VECTORS
`BY GREATEST PROXIMITY TO DELIVERY ADDRESS
`
`640
`
`DETERMINE IF SINGLE FULFILLER CAN FILL THIS ORDER
`
`650
`
`SPLIT ORDER PLACES ORDER ITEMS WITH SORTED
`FULFILLERS
`
`DONE
`
`FIG. 8
`
`PROVI-1019 - Page 15
`
`PROVI-1019 - Page 15
`
`

`

`US 7,263,495 B2
`
`1
`ORDER SCHEDULING SYSTEM AND
`METHODOLOGY
`
`A computer program listing appendix has been included
`on a single compact disc, with a file named LS0026-
`comptuer-program-listing-appendix.doc with a size of 76
`KB anda creation date of Jul. 18, 2005. The file and its
`content have been incorporated by reference.
`
`COPYRIGHT NOTICE
`
`A portion of the disclosure of this patent document
`contains material which is subject to copyright protection.
`The copyright owner has no objection to the facsimile
`reproduction by anyone of the patent documentor the patent
`disclosure as it appears in the Patent and Trademark Office
`patent file or records, but otherwise reserves all copyright
`rights whatsoever.
`
`BACKGROUND OF THE INVENTION
`
`1. Field of the Invention
`
`The present invention relates to the field of order fulfill-
`ment and, moreparticularly, to system and methodology for
`efficiently managing order fulfillment.
`2. Description of the Background Art
`Despite advances afforded by e-commerce,a fundamental
`problem still exists today in terms of howto efficiently fulfill
`an order that has been placed by a customer. This problem
`typically faces those who take customer orders, that is, the
`“middlemen” (which is used herein to broadly refer to
`retailers, distributors, or the like). Often, a middleman will
`have to send a customer order to a “fulfiller,” that is, an
`organization that will fulfill the order by actually shipping
`ordered goods back to the customer. The considerations
`involved in choosing a particular fulfiller are numerous, but
`typically a middleman choosesa fulfiller with the primary
`goal of minimizing costs, thus maximizing profits. Different
`cost-related constraints may comeinto play, whenstriving to
`maximize profit. For example,
`in addition to the cost
`incurred as a result of the price charged by a given fulfiller,
`other cost considerations include what shipping charges are
`incurred when shipping from a given fulfiller. One fulfiller
`may have a better price, but that price advantage may be
`negated by unfavorable shipping charges. Further, cost is not
`the only factor to consider. Instead, at least some consider-
`ation must be given to the ability of a particular fulfiller to
`timely fulfill an order. There is no point in choosing a
`fulfiller who offers the best price,
`if that fulfiller lacks
`sufficient
`inventory to successfully fulfill
`the order in a
`reasonable period of time.
`Often an order cannot be completely fulfilled, or supplied,
`by a single fulfiller; therefore, the fulfillment of such an
`order is spread across multiple fulfillers. The determination
`of the distribution of sub-orders, or product orders within an
`order, to multiple fulfillers is the scheduling of order ship-
`ments for that order. Order shipment scheduling attempts to
`optimize the fulfiller distribution to minimize the shipping
`costs to either the customer or to the middleman processing
`the order. Minimizing the shipping costs almost invariably
`indicates minimizing the numberoffulfillers satisfying an
`order. Optimized scheduling also minimizes delivery time,
`and satisfies any arbitrary business logic, such as favoring
`specified fulfillers (when more than onefulfiller can deliver
`the sameorder item in an order). The middleman needs to
`efficiently optimize the order
`shipment(s)
`scheduling
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`2
`according to whatever constraints he or she uses as criteria
`for assigning order items to fulfillers.
`Previous attempts to automate (by computer program-
`ming) the optimization of order shipment scheduling have
`not been satisfactory. Current methods involve considerable
`time for programming development/updating, and require
`costly compute time. The prevailing approach uses the
`simplex method for solving the linear programs comprising
`multiple simultaneous linear equations; see, e.g., Anderson,
`David Ray, An Introduction to Management Science: Quan-
`titative Approaches to Decision Making, Seventh Edition,
`Chapter 5 (particularly at pp. 190-192), West Publishing
`Company, 1994, the disclosure of which is hereby incorpo-
`rated by reference. This approach develops a linear pro-
`gramming model comprising a set of linear equations: each
`linear equation describes a constraint (e.g., proximity of
`shipper-to-shipping recipient) to be applied to all potential
`fulfillers.
`A linear equation solves for a single variable, and takes
`the form: ax+b=0, where x is the unknownvariable, and both
`a and b are constant numerical values. In linear equations,
`the variable, x, always has its exponential value set to 1;
`exponential or logarithmic variable types are not employed
`as operandsin linear equations. Each linear equation can be
`graphedas a straight line in a two-dimensional XY-coordi-
`nate plane. The coefficient for the variable (the constant
`numerical value of a, in the generic form) determines the
`slope of the straight line for that equation. This equation is
`processed for every fulfiller considered. If the scheduling
`method implements multiple constraints,
`then a separate
`linear equation is processed against each constraint simul-
`taneously. Multiple linear equations can be mapped onto a
`two-dimensional graph. The set of possible solutions (that
`minimizes for these constraints)
`is bound by the area
`beneath the intersections of the straight line on the graph.
`FIG. 1 is an XY two-dimensional coordinate graph show-
`ing the slopes for three separate linear equations represent-
`ing three constraints in a problem for scheduling types of
`personal computers (e.g., DeskPro™): warehouse capacity,
`display units, and assembly time. FIG. 1 includes the slope
`100 for the equation constraining warehouse capacity, the
`slope 110 for the equation constraining display units, the
`slope 120 for the equation constraining assembly time, the
`area-bounding intersection 130 of the X and Y axesat value
`(0,0), the area-bounding intersection 140 of the warehouse
`capacity slope 100 and the X-axis, the area-bounding inter-
`section 150 of the assembly time slope 120 and the ware-
`house capacity slope 100, the area-bounding intersection
`160 of the display units slope 110 and the assembly time
`slope 120, and the area-bounding intersection 170 of the
`Y-axis and the display units slope 110. The area bound by the
`intersections in FIG. 1, 130, 140, 150, 160, and 170, contains
`the set of feasible solutions for this problem. A discrete
`solution for any variable (constraint) can be determined by
`holding all the other variables’ values at a constant (within
`the feasible set).
`Current systems using linear programming with multiple
`simultaneous equations leave much to be desired. A well-
`known problem with linear solutions is that the simplex
`method requires intensive iteration. Computerized solutions
`for multiple simultaneous equations are therefore time-
`consuming. Another deficiency with linear programmingis
`the programmatic difficulty in setting-up the equations.
`Because the constraints can be described in linear equations
`with inequalities,
`it
`is challenging to program a general
`solution that applies to every scenario. Full appreciation of
`all the factors defining the constraints cannot be completely
`PROVI-1019 - Page 16
`
`PROVI-1019 - Page 16
`
`

`

`US 7,263,495 B2
`
`4
`XML: Short for Extensible Markup Language, a specifica-
`tion developed by the W3C. XML is a pared-down
`version of SGML, designed especially for Web docu-
`ments. It allows designers to create their own customized
`tags, enabling the definition, transmission, validation, and
`interpretation of data between applications and between
`organizations. For further description of XML,see, e.g.,
`Extensible Markup Language (XML) 1.0 specification
`whichis available from the World Wide Web Consortium
`
`the disclosure of which is hereby incorporated by refer-
`ence.
`
`10
`
`SUMMARY OF THE INVENTION
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`An order scheduling system providing a method for
`distributing product orders to multiple fulfillers is described.
`This method solves the commonbusiness problem of sched-
`uling order shipments. The method is both optimal and fair
`(among multiple otherwise-equal fulfillers). It
`is optimal
`because it minimizes the numberoforders across fulfillers,
`thus minimizing shipping costs. It is fair because orders are
`1 and 0)
`bit vector: A one-dimensional array of bit (e.g.,
`distributed equally across fulfillers if that fulfiller has the
`values, which is useful for specifying a sequence of
`product available.
`Boolean (true/false) values.
`To schedule orders, a data structure is defined whose rows
`fulfiller: Fulfiller, as used herein, broadly refers to any entity
`are represented by a hashtable of Fulfillers (HF), where each
`capable of fulfilling an orderor portions(i.e., order items)
`column is a hash table of Products (HP) and where each
`thereof, which may include a distributor, supplier, vendor,
`index of HP is itself a bit vector (VP,). This gives a
`manufacturer, service bureau, or the like. Typically, the
`three-dimensional data structure. Here, the term “hash” is
`fulfiller receives orders from a middleman (e.g., retailer,
`used to indicate that for a given fulfiller/product pair, the
`or the like). The fulfiller may fulfill an order by shipping
`approach may “hash” (i.e., index on) that pair for indexing
`directly to the end customer, or by shipping to the
`into a particular cell
`in the table. This fulfiller/product
`middleman (whoin turn ships to the end customer).
`correspondence may also be represented by a two-dimen-
`HTTP: Short for HyperText Transfer Protocol, the underly-
`sional array (e.g., accessible via numeric indexes). Although
`ing protocol used by the World Wide Web. HTTP defines
`the information represented in the hash table may be derived
`how messages are formatted and transmitted, and what
`from SQL queries submitted to a product/supplier database,
`actions Web servers and browsers should take in response
`
`to various commands. For example, when a user enters a it is more efficient to maintain this information inarelatively
`URL in his or her browser, this actually sends an HTTP
`terse in-memory data structure, as the information will be
`command to the Web server directing it to fetch and
`repeatedly accessed.
`transmit the requested Web page. Further description of
`In contrast to using linear equations for representing this
`information, the hash table itself is extensible. If additional
`HTTP is available in REC 2616: Hypertext Transfer
`Protocol—HTTP/1.1, the disclosure of which is hereby
`fulfillers or suppliers becomeavailable, the numberof rows
`incorporated by reference. RFC 2616 is available from the
`in the hash table is simply increased (or simply decreased to
`World Wide Web Consortium (W3).
`represent less). In a corresponding manner, the number of
`rows in the hash table may be increased or decreased to
`Java: A general purpose programming language developed
`accommodate changes in the current product offerings.
`by Sun Microsystems. Java is an object-oriented language
`Thus, when changesoccur, as they invariably will, the hash
`similar to C++, but simplified to eliminate language
`table may readily accommodate those changes. There is no
`features that cause common programming errors. Java
`requirement that the underlying program code be modified.
`source codefiles (files with a java extension) are com-
`piled into a format called bytecode (files with a .class
`Whethera particular fulfiller has a product available does
`extension), which can then be executed by a Java inter-
`not necessarily depend on that fulfiller’s inventory. Cer-
`preter. Compiled Java code can run on most computers
`tainly, limited inventory poses a problem to product avail-
`because Java interpreters and runtime environments,
`ability by a fulfiller. However, some products have effec-
`known as Java Virtual Machines (JVMs), exist for most
`tively unlimited inventory. For example, the ability of a
`operating systems, including UNIX, the Macintosh OS,
`photofinisher to provide an almost unlimited number of
`and Windows. Bytecode can also be converted directly
`reprints for a customer photograph is one such example.
`into machine languageinstructionsbya just-in-time com-
`Here, the photofinisher (fulfiller) has effectively unlimited
`piler (JIT).
`supply of photo-finishing paper available for completing the
`customer order (of reprinting a photograph). Therefore,
`Servlet: An applet that runs on a server. The term usually
`often the issue of whether a particular product is available
`refers to a Java applet that runs within a Web server
`from a given fulfiller depends on whether that fulfiller
`environment. This is analogous to a Java applet that runs
`within a Web browser environment. Java servlets are
`actually even offers that product to begin with.
`An orderitself may be viewed as one or more order items
`(typically, corresponding to a particular product). In certain
`cases, it may be necessary to split a customer order among
`the multiple fulfillers, based on order items. For example, an
`order may besplit into two order items, OI, and OL, in
`effect, two suborders. The order may be split by having one
`PROVI-1019 - Page 17
`
`3
`knowna priori. For example, if the program implements a
`policy towards minimizing shipping costs,
`the program
`would need to knowall of the distances between the location
`
`of the middlemanor the customer andthe location of every
`fulfiller:
`that
`information would have to be put
`into a
`database, and extracted-out and placed into a coefficient for
`each iteration of each equation. The approach has a degree
`of fuzziness that stems from the implicit effects of other
`incidental variables, such as slack time (which is the con-
`sequence of having determined the best solution, there is
`always a remainderleft over).
`The simplex method of solving linear equations is not the
`only method; however, the other methods are even more
`difficult
`to implement. Because of the ever-increasing
`demandsof the marketplace (and e-commerce marketplace)
`for timely, cost-effective fulfillment of customer orders,
`muchinterest exists in finding a solution to these problems.
`
`GLOSSARY
`
`becoming increasingly popular as an alternative to CGI
`programs. The biggest difference between the twois that
`a Java applet is persistent. Onceit is started, a servlet stays
`in memory and can fulfill multiple requests. In contrast, a
`CGI program disappears once it has fulfilled a request.
`Thepersistence of Java applets tends to make them faster.
`
`PROVI-1019 - Page 17
`
`

`

`US 7,263,495 B2
`
`5
`fulfiller, F,, fulfill OI,, while a second fulfiller, F,, fulfills
`OL. A VP, vector, which extends into the third dimension (z
`axis) of the abovehashtable, is potentially employed in such
`instances. The VP, vector allows tracking of what part of an
`order—specifically, what order item—was split and to
`which fulfiller.
`Using the above-described bit vectors, the method may
`perform bitwise ANDing (&) operations of the bit vectors.
`This generates an Order bit vector representing the opti-
`mized fulfillment (per system configuration/constraints) for
`a particular received order.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1 is a graph illustrating the simplex method for
`scheduling order fulfillment.
`FIG.2 is a block diagram of a computer system in which
`software-implemented processes of the present invention
`may be embodied.
`FIG. 3 is a block diagram of a software system for
`controlling the operation of the computer system of FIG.2.
`FIG. 4A is a diagram illustrating a hash table data
`structure employed in the system of the present invention.
`FIG. 4B is a diagram illustrating simple order splitting.
`FIG. 4C is a diagram illustrating more-complex order
`splitting.
`FIG. 5A is a high-level block diagram illustrating a
`server-based order scheduling system of the present inven-
`tion.
`
`FIG.5B is a block diagram illustrating an order scheduler
`module of the order scheduling system.
`FIG. 5C(1) is a block diagram illustrating the arrangement
`of detailed views for a database schema employed by the
`order scheduling system.
`FIG. 6 is a flowchart illustrating overall operation of the
`order scheduling system of the present invention.
`FIG.7 is a flowchart illustrating a coarse-grained optimi-
`zation method for fulfilling an order with a relatively low
`numberoffulfillers.
`
`FIG.8 is a flowchart illustrating a method for minimizing
`shipping costs by placing order items with fulfillers geo-
`graphically nearest to the delivery address.
`
`DETAILED DESCRIPTION OF A PREFERRED
`EMBODIMENT
`
`The following description will focus on the presently-
`preferred embodiment of the present invention, which is
`implemented in an Internet-connected server environment
`running under a server operating system, such as the
`Microsoft® Windows XP running on an IBM-compatible
`PC. The present invention, however, is not limited to any
`particular one application or any particular environment.
`Instead, those skilled in the art will find that the system and
`methods of the present invention may be advantageously
`embodied on a variety of different platforms,
`including
`Macintosh, Linux, BeOS, Solaris, UNIX, NextStep,
`FreeBSD, and the like. Therefore, the description of the
`exemplary embodiments that follows is for purposes of
`illustration and notlimitation.
`
`I. Computer-Based Implementation
`A. Basic System Hardware (e.g., for Desktop and Server
`Computers)
`The present invention may be implemented on a conven-
`tional or general-purpose computer system, such as an
`IBM-compatible personal computer (PC) or server com-
`
`40
`
`45
`
`60
`
`6
`puter. FIG. 2 is a very general block diagram of an IBM-
`compatible system 200. As shown, system 200 comprises a
`central processing unit(s)
`(CPU) or processor
`(s) 201
`coupled to a random-access memory (RAM) 202, a read-
`only memory (ROM) 203, a keyboard 206, a pointing device
`208, a display or video adapter 204 connected to a display
`device 205, a removable (mass) storage device 215 (e.g.,
`floppy disk, CD-ROM, CD-R, CD-RW,or the like), a fixed
`(mass) storage device 216 (e.g., hard disk), a communication
`port(s) or interface(s) 210, a modem 212, and a network
`interface card (NIC) or controller 211 (e.g., Ethernet).
`Although not shownseparately, a real-time system clock is
`included with the system 200, in a conventional manner.
`CPU 201 comprises a processor of the Intel Pentium®
`family of microprocessors. However, any other suitable
`microprocessor or microcomputer maybeutilized for imple-
`menting the present invention. The CPU 201 communicates
`with other components of the system via a bi-directional
`system bus (including any necessary input/output
`(I/O)
`controller circuitry and other “glue” logic). The bus, which
`includes address lines for addressing system memory, pro-
`vides data transfer between and among the various compo-
`nents. Description of Pentium-class microprocessors and
`their instruction set, bus architecture, and control lines is
`available from Intel Corporation of Santa Clara, Calif.
`Random-access memory 202 serves as the working memory
`for the CPU 201. In a typical configuration, RAM ofsixteen
`megabytes or more is employed. More or less memory may
`be used without departing from the scope of the present
`invention. The read-only memory (ROM) 203 contains the
`basic input output system code (BIOS)—aset of low-level
`routines in the ROM that application programs and the
`operating systems can use to interact with the hardware,
`including reading characters from the keyboard, outputting
`characters to printers, and so forth.
`Mass storage devices 215, 216 provide persistent storage
`on fixed and removable media, such as magnetic, optical or
`magnetic-optical storage systems,
`flash memory, or any
`other available mass storage technology. The mass storage
`may be shared on a network, or it may be a dedicated mass
`storage. As shownin FIG.2, fixed storage 216 stores a body
`of program anddata for directing operation of the computer
`system,
`including an operating system, user application
`programs, driver and other support files, as well as other data
`files of all sorts. Typically, the fixed storage 216 serves as the
`main hard disk for the system.
`In basic operation, program logic (including that which
`implements methodology ofthe present invention described
`below)is loaded from the storage device or mass storage 216
`into the main (RAM) memory 202, for execution by the
`CPU 201. During operation of the program logic, the system
`200 accepts user input from a keyboard 206 and pointing
`device 208, as well as speech-based input from a voice
`recognition system (not shown). The keyboard 206 permits
`selection of application programs, entry of keyboard-based
`input or data, and selection and manipulation of individual
`data objects displayed on the display screen 205. Likewise,
`the pointing device 208, such as a mouse, track ball, pen
`device, or the like, permits selection and manipulation of
`objects on the display screen. In this manner, these input
`devices support manual user input for any process running
`on the system.
`The computer system 200 displays text and/or graphic
`images and other data on the display device 205. The video
`adapter 204, which is interposed between the display 205
`and the system, drives the display device 205. The video
`adapter 204, which includes video memory accessible to the
`PROVI-1019 - Page 18
`
`PROVI-1019 - Page 18
`
`

`

`US 7,263,495 B2
`
`7
`CPU 201, provides circuitry that converts pixel data stored
`in the video memory to a raster signal suitable for use by a
`cathode ray tube (CRT) raster or liquid crystal display
`(LCD) monitor. A hard copyof the displayed information, or
`other information within the system 200, may be obtained
`from the printer 207, or other output device. Printer 207 may
`include, for instance, an HP LaserJet® printer (available
`from Hewlett-Packard of Palo Alto, Calif.), for creating hard
`copy images of output of the system.
`The system itself communicates with other devices (e.g.,
`other computers) via the network interface card (NIC) 211
`connected to a network (e.g., Ethernet network), and/or
`modem 212 (e.g., 56K baud, ISDN, DSL, or cable modem),
`examples of which are available from 3Com of Santa Clara,
`Calif. The system 20