Minimizing the weighted sum of maximum earliness and maximum tardiness costs on a single machine with periodic preventive maintenance

We consider the problem of scheduling a set of jobs on a single machine against a common and restrictive due date. In particular, we are interested in the problem of minimizing the weighted sum of maximum earliness and maximum tardiness costs. This kind of objective function is related to the just-i...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2014-07, Vol.47, p.106-113
Main Authors: Benmansour, Rachid, Allaoui, Hamid, Artiba, Abdelhakim, Hanafi, Saïd
Format: Article
Language:English
Subjects:
Applied sciences
Availability
Computer Science
Costs
Due date
Earliness
Exact sciences and technology
Flow control
Industrial metrology. Testing
Integer programming
Inventory control, production control. Distribution
Job shops
Just in time
Maintenance
Mathematical analysis
Mathematical models
Mathematical programming
Mechanical engineering. Machine design
Mixed integer
Operational research and scientific management
Operational research. Management science
Operations research
Optimization
Packing problem
Preventive maintenance
Scheduling
Scheduling algorithms
Scheduling, sequencing
Studies
Tardiness
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:We consider the problem of scheduling a set of jobs on a single machine against a common and restrictive due date. In particular, we are interested in the problem of minimizing the weighted sum of maximum earliness and maximum tardiness costs. This kind of objective function is related to the just-in-time environment where penalties, such as storage cost and additional charges for late delivery, should be avoided. First we present a mixed integer linear model for the problem without availability constraints and we prove that this model can be reduced to a polynomial-time model. Secondly, we suppose that the machine undergoes a periodic preventive maintenance. We present then a second mixed integer linear model to solve the problem to optimality. Although the latter problem can be solved to optimality for small instances, we show that the problem reduces to the one-dimensional bin packing problem. Computational results show that the proposed algorithm best fit decreasing performs well.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2014.02.004