This research paper is an attempt to study the conceptual and procedural encoding of a set of eight discourse markers "baahi" (yeah), "a tongue click with a head node" (yeah), "aywa"(yeah), "awkay"(okay), "mm-hmm", "aah"(yeah), "millaxir" (after all) and "mali" (sorry) in Libyan Arabic everyday utterance contexts, used in Tobruk-speech community. These discourse markers are assumed here to have various, yet interrelated, interactional procedural encoding functions in such contexts. The procedural encoding functions of all these markers, conceptualized as procedural particles or expressions, are contextually assigned to constrain and limit the context relevance of the speakers assumptions that make use of them. This assigned constraining has taken place by activating one of the contextual cognitive effects; 'contextual implication', 'strengthening' or 'contradiction', or by guiding the recipient to some specific paths, set up in the context, that lead to such effects that are necessary for the intended conceptual encoding / processing of the utterance context. To that end, these discourse markers with reference to their conceptual and procedural encoding are going to be analyzed and explained, in this paper, within a revised model, based on the general theorizations of Relevance Theory, developed by Sperber and Wilson (1995); notably, the concept of procedural expressions constraints on relevance. Within this analytical framework, data examples collected from everyday conversations have been examined, yielding some significant concluding remarks. Chief among these remarks is that the use of these discourse markers in this speech community is contextually and cognitively motivated with regard to their procedural and conceptual encoding functions and uses. These remarks have launched the overall conclusion, in this paper, that the interactional relation between the procedural encoding functions of these markers and the conceptual encoding representation of the relevant utterance context has to be recognized, understood and applied by interlocutors, whenever they make use of such markers in their everyday speech.