New Direction to the Scheduling Problem: A Pre-Processing Integer Formulation Approach

New Direction to the Scheduling Problem: A Pre-Processing Integer Formulation Approach

Elias Munapo, Olusegun Sunday Ewemooje
Copyright: © 2021 |Pages: 16
DOI: 10.4018/978-1-7998-3970-5.ch004
OnDemand:
(Individual Chapters)
Available
$37.50
Current Special Offers
No Current Special Offers
TOTAL SAVINGS: $37.50

Abstract

This chapter presents a new direction to the scheduling problem by exploring the Moore-Hodgson algorithm. This algorithm is used within the context of integer programming to come up with complementarity conditions, more biding constraints, and a strong lower bound for the scheduling problem. With Moore-Hodgson Algorithm, the alternate optimal solutions cannot be easily generated from one optimal solution; however, with integer formulation, this is not a problem. Unfortunately, integer formulations are sometimes very difficult to handle as the number jobs increases. Therefore, the integer formulation presented in this chapter uses infeasibility to verify optimality with branch and bound related algorithms. Thus, the lower bound was obtained using pre-processing and shown to be highly accurate and on its own can be used in those situations where quick scheduling decisions are required.
Chapter Preview
Top

Statement Of The Problem

Problem: Using EDD, how can the jobs 1,2,3,…,n be sequenced so that tardiness is minimized? Suppose the scheduling problem is given as Table 1.

Table 1.
Scheduling problem based on n jobs
Job (Ji)123…N
Processing time (Pi)p1p2p3…pn
Due Date (Di)d1d2d3…dn

Key Terms in this Chapter

Earliest Due Date: A rule where jobs are scheduled according to the earliest due date given and to minimize the total tardiness of the whole jobs.

Tardiness: A quality or fact of being late in completing a job or project.

Optimal Solution: A feasible solution at the point where the objective function reaches its maximum/minimum value.

Complementarity Conditions: A way to model a constraint that has a combinatorial nature e.g. it implies that either A or B must be 0 or both may be 0 as well.

Iteration: A repetition of a process in order to generate a sequence of outcomes as a means of obtaining successively closer approximations to the solution of a problem.

Algorithm: A procedure or set of rules to be followed in problem-solving operations, specifically by a computer.

Branch and Bound Method: This is a solution method which partitions the feasible solution space into smaller subsets of solutions.

Complete Chapter List

Search this Book:
Reset