Sequence Generator from previous max sequence based on certain conditions
Dim unique_string1, unique_string2, unique_string3 As String



Variables declared without the As keyword are declared as a variant.  In the line above unique_string3 is declared as a String, unique_string1 an unique_string2 are variants.

The original posted code use Range("J2:J20000" &amp; jr).  jr was being concatenated to the end of "J2:J20000".  The post has been edited and corrected.

W is missing from the formula


INT(w2:20000))


getAddress = .Cells(i, 23).Address
Range(getAddress).Value = nextn



Use .Cells(i, 23).Value = nextn instead.  This will qualify the ranges to the worksheet instead of the ActiveSheet,


Sheets("Docs").Evaluate("MAX(IF((J2:J20000=""" &amp; x &amp; """)*(K2:K20000=""" &amp; y &amp; """)*(O2:O20000=""" &amp; z &amp; """),INT(w2:20000)))")



It is better to change the worksheets codenames for easy reference. 
VBA Codenames:
Sheet (document) modules have a property called CodeName, which is how the object is know internally to VBA. Indeed, if this feature is used by the developer, VBA code can always refer to a sheet (worksheet or chart), even if the sheet is renamed from Excel by a user. For example:


A worksheet is named 'Sales-2012'
Sheet CodeName is 'Sales'
User renames the worksheet to 'Sales-2013'


Use the Worksheet's Evaluate method instead of the Application's.

Refactored Code

Here is a rough rewrite of the OP's code:

Option Explicit

Sub NewSequence()
    Dim JobIds As Variant
    JobIds = GetUniqueValues("J")

    Dim Deps As Variant
    Deps = GetUniqueValues("K")

    Dim Job_Nos As Variant
    Job_Nos = GetUniqueValues("O")


    With wsDoc
        Dim LastRow As Long
        Rem Make sure that this refers to the longest used column
        LastRow = .Cells(.Rows.Count, 1).End(xlUp).Row

        Const BaseFormula As String = "MAX(IF((J2:J@LastRow=""@jobid"")*(K2:K@LastRow=""@dep"")*(O2:O@LastRow=""@job_no""),INT(w2:w@LastRow)))"

        Dim Formula As String
        Dim Id As Long
        Dim Department As Long
        Dim JobNumber As Long
        Dim i As Long

        For Id = 0 To UBound(JobIds)
            For Department = 0 To UBound(Deps)
                For JobNumber = 0 To UBound(Job_Nos)
                    For i = 2 To LastRow
                        Formula = Replace(BaseFormula, "@LastRow", LastRow)
                        Formula = Replace(Formula, "@jobid", JobIds(Id))
                        Formula = Replace(Formula, "@dep", Deps(Department))
                        Formula = Replace(Formula, "@job_no", Job_Nos(JobNumber))
                        .Cells(i, 23) = 1 + .Evaluate(Formula)
                    Next
                Next
            Next
        Next

    End With
End Sub

Private Function GetUniqueValues(ColumnName As Variant) As Variant
    Dim Target As Range
    With wsDoc
        Set Target = .Range(.Cells(2, ColumnName), .Cells(.Rows.Count, ColumnName).End(xlUp))
    End With

    Rem If there are no values then exit the function
    Rem The calling method should test if the return value is an array using isArray()
    If Target.Row = 1 Then Exit Function

    Rem Range.Value will return an 1 based range of values it the Range contains multiple cells
    Rem A Range that contains a single cell then it will return a single scalar value
    If Target.Count = 1 Then
        Rem Return the single value wrapped in a zero based array
        GetUniqueValues = Array(Target.Value)
        Exit Function
    End If

    Rem Typically a Scripting.Dictionary is used to return an unique lists
    Dim list As Object
    Set list = CreateObject("Scripting.Dictionary")


    Rem assign an 1 based array of values from the Target range to an array
    Dim Values As Variant
    Values = Target.Value

    Dim Item As Variant

    Rem Use For Each controls to iterate over the Values array
    For Each Item In Values
        Item = Trim(Item)
        If Not list.Exists(Item) And Len(Item) &gt; 0 Then list.Add Key:=Item, Item:=Item
    Next

    Rem Return a zero based array from the Dictionary
    GetUniqueValues = list.Keys
End Function


I changes the Doc tab codename to wsDocs for the code above.  Thanks Peter T!