𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Minimization of the makespan in a two-machine problem under given resource constraints

✍ Scribed by Adam Janiak

Publisher
Elsevier Science
Year
1998
Tongue
English
Weight
163 KB
Volume
107
Category
Article
ISSN
0377-2217

No coin nor oath required. For personal study only.

✦ Synopsis

In the paper the classical two-machine ¯ow-shop problem was generalized to the case when job processing times may be reduced linearly by the application of a limited, continuously divisible resource, e.g. ®nancial outlay, energy, fuel, catalyzer etc. It is proved that the decision form of this problem is NP-complete even for the ®xed job processing times on one of the machines and identical job reduction rates on another. Some polynomially solvable cases of the problem are identi®ed. Four simple and modi®ed approximate algorithms are presented together with their worst case and experimental analysis. Also, a fast exact algorithm of the branch and bound type based on the shown elimination properties of the problem considered is presented. Some computational results and generalizations (e.g. bicriterial approach) are included as well.

📜 SIMILAR VOLUMES

Makespan minimization in the two-machine
Makespan minimization in the two-machine flowshop batch scheduling problem
✍ T.C.E. Cheng; B.M.T. Lin; A. Toker 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 2 views

In this paper we consider a practical scheduling problem commonly arising from batch production in a flexible manufacturing environment. Different part-types are to be produced in a flexible manufacturing cell organized into a two-stage production line. The jobs are processed in batches on the first

A heuristic approach to allocating the c
A heuristic approach to allocating the continuous resource in discrete–continuous scheduling problems to minimize the makespan
✍ Joanna Józefowska; Marek Mika; Rafał Różycki; Grzegorz Waligóra; Jan Węglarz 📂 Article 📅 2002 🏛 Springer US 🌐 English ⚖ 98 KB

A problem of scheduling jobs on parallel, identical machines under an additional continuous resource to minimize the makespan is considered. Jobs are non-preemtable and independent and all are available at the start of the process. The total amount of the continuous resource available at a time is l

First integrals in the problem ofthe mot
First integrals in the problem ofthe motion of a heavy rigid body about a fixed point under unilateral constraint
✍ A.A. Burov 📂 Article 📅 2005 🏛 Elsevier Science 🌐 English ⚖ 221 KB

The problem of the existence of integrable cases of the Euler and Lagrange types, and also particular integrals of the Hess and Appel'rot type without additional assumptions on the value of the area integral, is considered for the problem of the motion of a heavy rigid body about a fixed point with