Complexity results and algorithms for an integrated single machine scheduling and outbound delivery problem with fixed sequence

Abstract : In this paper, we consider an integrated production and outbound delivery scheduling problem. In particular, we address the situation in which the scheduling sequence and the delivery sequence are the same and predefined. A set of jobs are processed on a single machine and finished jobs are delivered to the customers by a single capacitated vehicle. Each job has a processing time and transportation times between customers are taken into account. Since the sequence is given, the problem consists to form batches of jobs and our objective is to minimize the sum of the delivery times or general functions of the delivery times. The NP-hardness of the general problem is established and a pseudopolynomial time dynamic programming algorithm is given. Some particular cases are treated, for which NP-hardness proofs and polynomial time algorithms are given. Finally, a fixed-parameter tractability result is given.
Complete list of metadatas

Cited literature [24 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-01529299
Contributor : Azeddine Cheref <>
Submitted on : Tuesday, May 30, 2017 - 2:57:55 PM
Last modification on : Friday, January 10, 2020 - 9:10:16 PM
Long-term archiving on: Wednesday, September 6, 2017 - 1:52:35 PM

File

abc_revised_v11 (soumis_rappor...
Files produced by the author(s)

Identifiers

Citation

Azeddine Cheref, Alessandro Agnetis, Christian Artigues, Jean-Charles Billaut. Complexity results and algorithms for an integrated single machine scheduling and outbound delivery problem with fixed sequence. Journal of Scheduling, Springer Verlag, 2017, 20 (6), pp.681-693. ⟨10.1007/s10951-017-0540-2, 2017⟩. ⟨hal-01529299⟩

Share

Metrics

Record views

227

Files downloads

187